문제 2명의 사형수가 있다. 둘에게는 검정색 모자와 흰색 모자를 임의로 씌우는데, 자기가 쓴 모자의 색은 절대로 알 수가 없다. 서로 상대의 모자색만을 볼 수 있고, 이들이 살기 위해선 자신의 쓴 색의 모자를 맞춰야 한다. 단, 둘 중 한명만이라도 자신이 쓴 모자의 색을 맞춘다면 둘 다 살려주겠다고 약속했다. 조건은 다음과 같다. 1. 절대로 자신의 모자 색을 알 수 없다. 2. 상대방의 모자 색은 알 수 있다. 3. 둘 사이에는 어떠한 의사소통도 불가능하다. 행동(눈 깜빡임 등)으로도 알릴 수 없다. 4. 둘 중 한명만 자기가 쓴 모자 색을 맞추면, 둘다 살 수 있다. 5. 모자 색을 말하는건 동시에 말한다. 따라서 남이 말한것을 듣고 말하는 것은 안된다. 동시에 말해야 한다. 사형 집행인은 게임을 시작하기전에 둘이 협의할 시간을 잠시 주었고 두 사형수가 살아 남기 위해선 어떤 협의를 해야할까?
SOLUTION 두 사형수를 임의로 각각 A와 B라고 하자 A는 B의 모자 색을 말하기로 하고 B는 A의 모자와 반대되는 색을 말하기로 하면 어떤 경우이든 둘 중 한명이 정답을 맞추게 된다. CASE1] 검정, 검정 혹은 흰색, 흰색 이때는 반드시 A가 맞춘다. CASE2] 서로 다른 색의 모자를 쓸 때, 이때는 반드시 B가 맞춘다.
응용 문제 만약 사형수가 7명이고 임의로 쓰게되는 모자의 색이 빨, 주, 노, 초, 파, 남, 보 일 때, 어떤 협의를 하면 최소한 한 명이 자신의 모자 색을 맞출 수 있을까? 조건은 처음 문제와 같다. 7개의 색깔 중 쓰이지 않는게 있을 수 있다.
SOLUTION 빨강부터 보라까지 각각 0에서 6까지 숫자를 매긴다. 그 후 사형수들에게도 각각 0에서 6까지 숫자를 매긴다. 각 사형수들은 나머지 사형수들의 모자 숫자를 다 더한 후 거기 에 임의이 숫자 X를 더하고 7로 나누었을 때의 나머지가 자기에게 부여된 숫자와 같게 되는 수 X를 색깔로 치환해 말한다. 그렇게 되면 7명중 1명이 자기의 모자 색을 맞추게 된다.