문제


7ced8076b5826af03ce798bf06d604032d69c737cfb4836a8da7






답변

7ced8076b5826af03def98bf06d6040396c46318d42e58fbad78


7ced8076b5826af03ded98bf06d60403004141ddde259576c7d3


7ced8076b5826af03deb98bf06d60403ee80a3c9d0725a93f774


7ced8076b5826af03de998bf06d604039f9f1aa48b8338234dfa


7ced8076b5826af03de798bf06d6040365431a87e34c342edad5


7ced8076b5826af03aef98bf06d60403dce597c3a2614c48ce38




2분 11초만에 풀음

난 부호 이론을 안 배워서 어떻게 풀지 ㅈㄴ 고민하고 있었는데 저런 이론이 있었네 o1 pro 답변 읽어보고 이해함


예시로 든 코드워드가


00000000

11111000

00011111

11100111


인데, 이건 8번의 질문 중 

1-3 번째 질문 : "당신이 생각하는 숫자는 2 또는 4입니까?", 

4-5 번째 질문 : "당신이 생각하는 숫자는 2 또는 3입니까?",

6-8 번째 질문 : "당신이 생각하는 숫자는 3 또는 4입니까?"


로 한다는 거임

이렇게 하면, 답변이 1100000 (0은 아니오, 1은 예) 로 나왔다면, 답이 1인 경우에 모두 참인 8번의 대답인 00000000 과만 2비트의 차이가 발생하게 되므로 답이 1이라는 걸 알 수 있음


답이 2라면 모두 참인 대답은 11111000 일 텐데, 이러면 답변자가 3번의 거짓말을 한 것이므로 답이 2일 수는 없다는 뜻


이를 바탕으로 설계해보면, 4개의 8비트짜리 수를 모두 5 (2+2+1)비트 이상씩 차이가 나게 설계해야 답변자가 어떻게 대답을 하더라도 간파할 수 있음


하지만 길이가 7인 경우에는 이러한 4개트 7비트짜리 수를 설계할 수 없는데, 기하적으로는 7차원짜리 2*2*2*2*2*2*2짜리 박스 안에 반경이 2인 구 4개를 겹치지 않게 배치한다고 생각할 수 있고(이 때 반경은 통상적인 유클리드 기하 반경이 아니라 0000000과 1100000 이 거리가 2라고 생각하는 반경 - 이걸 택시기하라고 함),


7차원 공간 상에서 반경 2인 구는 1+7+7C2 = 29 개의 점이나 포함하므로 반경이 2인 구 4개를 겹치지 않게 배치하면 116개의 점이 커버됨. 근데 박스에는 점이 총 128개 있으므로 여유 공간이 너무 부족하다는 뜻


이 박스 안에 반경 2인 구 4개를 배치하는 게 불가능하다는 걸 엄밀하게 증명할 수도 있지만 그냥 생략했다고 함


아무튼 나도 몰랐던 이론인데 ㅈㄴ 신기하네 


원래 좀 알려진 문제이긴 했을 텐데 그래도 깔끔하게 푼 듯