History of the Muddy Children Puzzle

한스 판 디트마르슈(Hans van Ditmarsch)의 논문 "진흙 묻은 아이들 퍼즐의 역사(History of the Muddy Children Puzzle)"에 대한 설명입니다. 이 글은 일상적인 언어와 창의적인 비유를 사용하여 쉽게 번역되었습니다.

핵심 아이디어: "타인이 무엇을 아는지 아는 것"에 관한 퍼즐

친구들이 게임을 하고 있다고 상상해 보세요. 친구들은 서로의 얼굴은 볼 수 있지만, 자신의 모습은 보여주지 않는 마법 거울을 가지고 있습니다. 이 퍼즐의 질문은 이것입니다: 그들은 다른 사람들을 관찰함으로써 어떻게 자신의 얼굴에 무엇이 있는지 알아낼 수 있을까요?

이 논문은 하나의 역사적인 탐정 소설입니다. 저자인 한스 판 디트마르슈는 아주 단순한 질문에 답하고자 합니다: 이 퍼즐을 처음 만든 사람은 누구인가?

그는 그 답이 단 한 명의 인물이 아니라, 200년 넘게 이어져 온 이야기, 게임, 그리고 수학 책들이 얽히고설킨 긴 자취라는 것을 발견합니다.

---

파트 1: 퍼즐 그 자체 ("진흙 묻은 아이들")

다음은 고전적인 버전의 게임입니다:

• 설정: 아버지는 $k$명의 자녀를 두고 있습니다. 어떤 아이들은 얼굴에 진흙이 묻어 있고($m$명의 아이들), 어떤 아이들은 깨끗합니다.
• 규칙: 아이들은 자신의 얼굴을 제외한 나머지 모든 사람의 얼굴을 볼 수 있습니다. 아이들은 모두 완벽한 논리주의자입니다 (생각하는 데 있어 절대 실수를 하지 않습니다).
• 계기: 아버지가 말합니다. "너희 중 적어도 한 명은 얼굴에 진흙이 묻어 있다."
• 행동: 매 분마다 아버지는 묻습니다. "자신이 진흙이 묻었는지 아는 사람이 있느냐? 그렇다면 앞으로 나오거라."
• 결과: 만약 진흙이 묻은 아이가 1명이면, 그 즉시 앞으로 나옵니다. 만약 2명이면, 1분을 기다린 후 둘 다 앞으로 나옵니다. 만약 $m$명의 진흙 묻은 아이가 있다면, 그들은 정확히 $m$번째 분에 모두 앞으로 나옵니다.

비유: 이것은 정보라는 이름의 '뜨거운 감자'를 주고받는 게임과 같습니다. 아버지는 정보(누군가 진흙이 묻어 있다는 사실)라는 감자를 떨어뜨립니다. 아이들은 앞으로 나서지 않음으로써 정보를 전달합니다. 집단의 침묵은 그들에게 이렇게 말해줍니다. "오, 만약 아직 아무도 앞으로 나서지 않았다면, 내가 생각했던 것보다 진흙이 묻은 아이가 더 많다는 뜻이구나!" 결국 논리가 딱 맞아떨어지면, 그들은 모두 깨닫게 됩니다. "헤이, 내가 바로 진흙이 묻은 사람이구나!"

---

파트 2: 역사적 탐정 작업

저자는 이 퍼즐의 "조상"을 찾기 위해 추적을 시작합니다. 그가 발견한 내용은 다음과 같습니다.

1. 고대의 뿌리 ("웃음 없이 꼬집기" 게임)

저자는 이 아이디어를 16세기 프랑스의 거인 가르강튀아(Gargantua)에 관한 책까지 거슬러 올라가 추적합니다. 1823년판 이 책의 각주에는 Pince-sans-Rire ("웃음 없이 꼬집기")라고 불리는 게임이 설명되어 있습니다.

• 게임: 두 사람이 서로의 코를 꼬집습니다. 만약 웃으면 집니다.
• 반전: 두 플레이어는 몰래 손가락에 숯가루를 묻히고 있습니다. 그들은 서로의 코를 꼬집으며 얼굴에 검은 숯가루를 묻힙니다.
• 연결 고리: 만약 당신이 친구가 당신의 검게 변한 코를 보고 웃는 것을 본다면, 당신은 깨닫게 됩니다. "잠깐, 저 친구가 웃고 있다면, 내 얼굴에 뭔가 웃긴 게 묻어 있다는 뜻이겠구나!"
• 판결: 이것이 "진흙 묻은 아이들" 퍼즐의 "고조할아버지"입니다. 이것은 같은 논리(타인의 더러움을 보고 자신의 상태를 깨닫는 것)를 가지고 있지만, 수학 문제가 아닌 파티 게임입니다.

2. 사라진 세기 (1830년대–1930년대)

저자는 1800년대 서적에서 이 퍼즐을 찾아보았지만 공백을 발견했습니다. 이 아이디어는 사라진 것처럼 보였습니다. 그는 루이스 캐럴(Lewis Carroll)의 수수께끼나 당시의 표준 퍼즐 책에서도 이를 찾을 수 없었습니다. 이 아이디어는 마치 수학으로 기록되기를 기다리며 구전 역사나 파티 게임 속에 머물러 있었던 것 같습니다.

3. 재발견 (1920년대–1940년대)

이 퍼즐은 20세기에 몇몇 장소에서 다시 등장했습니다.

• 일본 (1929년): 유명한 물리학자 폴 디랙(Paul Dirac)이 일본을 방문했을 때 이 이야기를 전했습니다. 이후 이 문제는 "디랙의 수수께끼"로 알려지게 되었습니다. 한 미스터리 작가는 1941년에 이 문제를 바탕으로 한 탐정 소설을 쓰기도 했습니다.
• 유럽 (1942년): 수학자 모리스 크라이칙(Maurice Kraitchik)이 퍼즐 책에 이를 실었습니다. 그는 이를 얼굴이 더러워진 세 명의 철학자에 관한 이야기로 설명했습니다.
• 영국 (1953년): 또 다른 수학자 리틀우드(Littlewood)가 세 명의 여성이 서로의 더러운 얼굴을 보고 웃는 버전을 발표했습니다. 그는 이를 "진정한 수학"이라고 불렀습니다.

4. 현대 시대 (1950년대–현재)

1950년대 이후, 이 퍼즐은 수학과 컴퓨터 과학의 필수 요소가 되었습니다.

• "불충실한 아내들" 버전: 1950년대에 이 퍼즐은 바람피우는 남편과 아내에 관한 내용으로 바뀌었습니다. 진흙 대신 "더러운 것"은 부정(infidelity)이 되었습니다. 이 버전은 컴퓨터 과학 분야에서 매우 유명해졌습니다.
• "모자" 버전: 나중에 사람들은 진흙 대신 색깔 있는 모자로 바꾸었습니다. 자신의 모자는 볼 수 없다는 점이 진흙을 볼 수 없는 것과 같기 때문에 시각화하기 더 쉽습니다.
• 컴퓨터 과학의 붐: 1980년대에 조 할퍼른(Joe Halpern)과 같은 컴퓨터 과학자들은 이 퍼즐이 **인공지능(AI)**을 가르치는 데 완벽하다는 것을 깨달았습니다. 이는 컴퓨터가 에이전트(로봇이나 프로그램)가 어떻게 정보를 공유하고 지식을 업데이트하는지 이해하는 데 도움을 줍니다.

---

파트 3: 새로운 퍼즐 ("자기 참조적 모자")

논문은 게르하르트 베거링거(Gerhard Woeginger)가 발명한 새로운 퍼즐인 **"Mützen" (모자)**로 끝을 맺습니다.

설정:

• 산타클로스가 126명의 똑똑한 난쟁이를 초대합니다.
• 각 난쟁이는 무작위 색상의 모자를 씁니다. 색상은 아주 다양합니다 (노란색, 초록색, 파란색 등).
• 조건: 산타는 말합니다. "당신들 모두가 자신의 모자 색깔을 알아낼 수 있도록 내가 색상을 신중하게 골랐습니다."
• 과정: 5분마다 종이 울립니다. 자신의 색깔을 알게 된 난쟁이는 떠납니다.

미스터리:
난쟁이들은 13번의 종소리에 걸쳐 그룹별로 떠납니다. 질문은 이것입니다: 모두가 떠나는 데 총 몇 번의 종소리가 걸립니까?

해결 논리:
저자는 산타의 약속("당신들 모두가 알아낼 수 있다")이 매우 강력한 정보라는 점을 설명합니다. 이것은 마치 자기 충족적 예언과 같습니다.

• 만약 어떤 난쟁이가 오직 한 사람만이 쓰고 있는 색깔을 보았다면, 그는 "만약 내가 그 색깔을 쓰고 있다면, 아무도 알아낼 수 없을 텐데(왜냐하면 나 혼자뿐이니까)"라고 생각할 것입니다.
• 하지만 산타가 모두가 알아낼 수 있다고 약속했으므로, 누구도 "유일한" 존재가 될 수 없습니다.
• 따라서 모든 색깔은 반드시 최소 두 번 이상 나타나야 합니다.
• 난쟁이들은 이 논리를 사용하여 각 색깔을 쓰고 있는 사람이 몇 명인지 계산하고 올바른 순서대로 떠납니다.

저자는 이 새로운 퍼즐을 통해 현대 논리학(고정점(fixpoints)과 복잡한 수학을 사용하는 방식)이 어떻게 이러한 수수께끼를 해결할 수 있는지 보여주며, 오래된 "진흙 묻은 아이들" 아이디어가 오늘날에도 여전히 진화하고 있음을 증명합니다.

---

요약: 이것이 왜 중요한가?

이 논문은 단순히 진흙이나 모자에 관한 것이 아닙니다. 이것은 우리가 서로로부터 어떻게 배우는가에 관한 것입니다.

• 은유: 방 안에 사람들이 가득 차 있다고 상상해 보세요. 만약 제가 여러분에게 "이 방 안에 빨간 셔츠를 입은 사람이 있다"라고 말한다면, 여러분는 누가 누구인지는 모릅니다. 하지만 주변을 둘러보았을 때 아무도 일어나지 않는 것을 보고, 제가 다시 말했는데도 여전히 아무도 일어나지 않는다면, 여러분은 무언가를 깨닫기 시작할 것입니다.
• 교훈: 논문은 때때로 가장 중요한 정보는 무엇이 '말해지는가'가 아니라, 무엇이 '말해지지 않는가'(침묵, 기다림)라는 점을 보여줍니다.
• 유산: 코를 꼬집는 프랑스의 게임에서부터 인공지능을 위한 컴퓨터 과학 도구에 이르기까지, 이 퍼즐은 옷(진흙, 먼지, 모자, 바람피우는 배우자)을 갈아입으면서도 뇌를 자극하는 핵심은 그대로 유지한 채 수 세기를 여행해 왔습니다.

저자는 독자들이 1920년대와 1930년대의 더 오래된 버전, 특히 이 퍼즐의 역사를 찾는 데 도움을 주기를 권하며, 이 수수께끼의 역사는 여전히 쓰여지고 있음을 시사하며 마무리합니다.