모자 문제 [1편]
유수의 수학 만화와 방송 프로그램에서 나온 속칭 '모자 문제'에서 약간 변형된, '원탁에서의 모자문제' 원문은 아래와 같다.
A group of N prisoners is allowed to play a game for their freedom. The prisoners are donned with either a block hat or a white hat, and, they cannot see their own hat. They can only see the remaining hats. The two colors are equally likely. The prisoners play as a team and win when at least one prisoner guesses the color of his/her own hat without any incorrect guesses being made. The prisoners may strategize before the game, but cannot communicate in any fashion once the game begins. What is the best strategy?
쉽게 말하면, 수감자 머리 위에는 검은색(이하 B)과 흰색 모자(이하 W)가 씌여져 있다. 그들은 (마치 원탁에 앉았다고 생각해보자) 서로의 모자색을 확인할 수 있지만 자신의 모자색을 확인할 수는 없다. 모자색을 맞출지, 말지는 죄수 본인이 결정할 수 있다. 대신 죄수가 게임에서 승리하기 위해서는 incorrect guess는 없어야 하고, 대신 최소 한 명은 자신의 모자색을 정확히 맞춰야 한다. 어떤 전략을 써야 죄수가 이길 확률을 극대화할 수 있을까?
상당히 조합적인 사고를 요하는 문제로 보인다. 이러한 스타일의 문제를 접해본 곳은 국제적인 권위의 수학대회 기출문제 이외에는 거의 없었던 것 같은데, 그러나 그때마다 이런 문제들은 조합과는 거리가 먼, 전혀 다른 분야의 도움을 받아 해결해야만 했다.
이 문제를 두 편에 걸쳐 서술하려 한다. (이후 수정. 네 편으로 늘어났다. 생각보다 풀이의 전략을 완벽히 이해하고 설명하는데 많은 시간이 필요하였다.) 첫 번쨰 편은 직관적인 몇 개의 숫자를 대입한 가벼운 문제를 제공하며, 이를 통해 문제에 대한 독자 (및 저자)의 이해도를 높이고, 추후 일반화에 대한 감을 잡게 하는 과정을 만들고자 한다. 두 번째 편은 전혀 다른 수학의 세부 분야가 결부되어 하나의 친근한 문제를 해결하는 아름다운 과정을 집중적으로 다루고자 한다. 이 결부는 수학에서 내가 가장 큰 매력을 느끼는 부분이기도 하다. (3blue1brown의 유튜브 영상이 주로 이러한 극적 상봉에 초점을 맞춘 영상을 종종 다룬다.) 고등학생, 중학생도 경우에 따라 충분히 이해가능한 내용이니 이러한 컨텐츠에 목말라 있었던 과거 학창시절의 나와 같은 이들이 이 글(들)을 읽고 많은 것을 생각해봤으면 좋겠다. 더 이상 3blue1brown의 번역되지 않은 유튜브 영상을 보느라 어려움을 겪지 않았으면 한다.
일단 $N=2$ 때 생각해보자. 각 참가자의 판단은 독립적이다.
(i) 만약, 각 참가자는 서로의 모자색을 무시하고 B와 W 중 랜덤하게 자신의 모자색을 말한다고 하자. 이 경우, 사전에 한 명만 랜덤으로 말하기로 작당모의를 하고 들어간다면 50%의 확률로 승리할 수 있다.
(ii) 만약, 각 참가자는 서로의 모자색을 보고 그것과 같은 색으로 말하기로 사전에 모의한다고 하자. 이 경우 몇 명이 외치든 두 모자가 (B, B), (W, W)일 때 승리할 수 있다. 마찬가지, 승리 확률은 50%.
(iii) 만약, 각 참가자는 서로의 모자색을 보고 그것과 반대 색으로 말하기로 사전에 모의한다고 하자. 이 경우 몇 명이 외치든 (B, W), (W, B)일 때 승리할 수 있다. 마찬가지, 승리 확률은 50%.
생각할 수 있는 전략은 위 세 가지가 전부이다. 모두 죄수의 승리 확률은 50%이다.
$N=3$ 일 때 최선의 전략은 아래와 같이 밝혀졌다. 증명은 전략을 적은 뒤 적겠다.
* If a prisoner sees two hats of the same color (s)he guesses the opposite color.
(This is valid strategy becuase there must be two hats of the same color, by pigeonhole principle)
이 경우 (B, B, B)와 (W, W, W)를 제외한 나머지 상황에서 죄수는 승리할 수 있다. 승리 확률은 75%.
위 전략이 최선의 전략임을 밝혀내기 위해서 아래와 같은 정리를 대체하여 증명할 수 있다.
The upper bound on the probability of victory in this game with $N=n$ is : $\frac{n}{n+1}$
Proof) 각자의 선택을 다른 관점에서 보자. 남의 모자가 어떤 색이고를 떠나서, 내가 내 모자의 색을 외쳐서 맞출 확률은 언제나 50%이다. 그러므로 가능한 모든 case에 대하여 각자의 guess는 절반은 항상 맞고, 절반은 항상 틀려야 한다. 남의 모자색이 어떻다고 하더라도, 내가 외치는 순간 내 모자를 맞출 확률은 언제나 50%이다. 그 균등함이 전체 case에 반영되어 있을 것이다. 말하고 싶은 것은, 외친 사람이 자기 모자를 맞출 확률은 언제나 50%이므로, 모든 case의 guess 목록에 대해 절반은 맞고, 절반은 틀린 상황이 항상 나올 것이라는 얘기다.
$N=3$일 때 아까의 전략을 대입해 보자.
[1] (B, B, B)이면 모두 W를 외치고 모두 incorrect guess가 된다.
[2] (B, W, W)이면 첫 번째 사람만 B를 외치고, 이건 correct guess가 된다.
[3] (B, B, W)이면 세 번째 사람만 W를 외치고, 이건 correct guess가 된다.
[4] (W, W, W)이면 모두 B를 외치고 모두 incorrect guess가 된다.
[5] (W, B, W)이면 가운데 사람만 B를 외치고, 이건 correct guess가 된다.
[6] (B, W, B)이면 가운데 사람만 W를 외치고, 이건 correct guess가 된다.
[7] (W, W, B)이면 세 번째 사람만 B를 외치고, 이건 correct guess가 된다.
[8] (W, B, B)이면 첫 번째 사람만 W를 외치고, 이건 correct guess가 된다.
결론적으로, 전체 guess 목록 중에서 6개는 correct guess였고, 6개는 incorrect guess이다. 개별 guess가 맞을 확률은 언제나 50%라는 것이다. (전체 중 하나가 맞을 확률은 다르겠지만)
그러면 이 사실을 이해했다면 증명의 길이 보인다. 전체 $2^{N}$가지의 case 중 어떤 전략을 쓰면 $X$개의 case를 win case로 만들 수 있다고 가정하자. $2^{N}-X$개의 case는 lose case이다. lose case는 최대 $N$개의 incorrect guess를 내포할 수 있고, win case는 최소 1개의 correct guess를 내포해야 한다.
그러므로 Win case $\leq $ correct guess $=$ incorrrect guess $\leq $ lose case $\times N$의 부등식이 성립한다.
부등식의 처음과 끝만 보면, $X\leq N\times (2^{N}-X)$이다. 이 식을 정리하여 $\frac{X}{2^{N}}$에 대한 부등식으로 정리하면 위와 같은 Upper bound를 얻어낼 수 있다. 그러므로, 죄수가 3명일 때 위 전략의 승리 확률은 Upper bound와 같기에 최적의 전략이라 할 수 있을 것이다.