이 문제는 1년차 때 룸메이트를 통해 들은 문제였는데, 만 24시간의 고민 끝에 겨우 답을 찾을 수 있었던, 내 평생 가장 어려웠던 확률(?) 문제다.

10 명의 죄수에게 무작위로 1 부터 10까지의 정수가 적힌 카드를 이마에 붙여준다. 숫자는 반복 추첨한다(10명 모두 다른 숫자가 부여 될 수도 있지만, 모두 똑같은 숫자가 부여 될 수도 있다). 각 죄수는 자신에게 부여된 숫자는 볼 수 없지만, 나머지 9명의 죄수에게 부여된 숫자는 볼 수 있다. 번호를 부여 받기 전까지 죄수 간에 전략을 얼마든지 계획 할 수는 있지만, 번호를 부여 받은 후에는 일절 죄수 간 의사소통이 금지 된다. 10명의 죄수 모두 번호를 부여 받은 후, 단 한 사람이라도 본인이 부여 받은 번호를 맞출 수 있으면 10명 모두 풀려난다.

위 상황에서, 번호를 부여 받기 전 죄수들이 풀려날 확률을 최대화하는 전략은?

아래 힌트를 보기 전에 스스로 고민해 볼 것

힌트 1

죄수가 2명일 때는 다음과 같이 100% 풀려나는 전략을 구상할 수 있다:

• 한 명의 죄수는 상대방 이마에 붙어 있는 번호를 자신의 번호로 추측하고, 나머지 한 명은 상대방 이마에 붙어 있는 번호의 반대로 자시나의 번호를 추측한다.

위 전략 경우, 총 4 가지 가능한 상황마다 적어도 한 명은 자신의 번호를 바르게 맞춘다:

힌트 2

위 2명의 죄수의 경우, 두 죄수 모두가 자신의 번호를 맞추는 상황은 발생하지 않는다.

힌트 3

10명의 죄수가 번호를 부여 받는 모든 경우의 수(\(10 \times 10 = 100\))를, 각 10명의 죄수 중 정확히 한 명만 자신의 번호를 바르게 맞출 수 있는 10가지 상황으로 분류할 수 있는 방법이 있는지 고민해보자.

해답을 알고나면 퍼즐은 더이상 의미/재미가 없으므로, 아래 해답을 보기 전에 반드시 혼자서 풀어 볼 것!

혹시 아래 해법에 동의하지 않거나, 다른 (더 재미있는) 해법이 있다면 댓글 혹은 메일 주세요!^^

해법 1

10명의 죄수 중 임의의 한 죄수가 부여 받은 번호를 \(x\)라 하자. 나머지 9명의 죄수가 부여 받은 번호의 합을 \(N\)이라 하면, 각 죄수는 \(N\)을 정확하게 계산할 수 있다. 즉, 자신의 번호를 제외한 나머지 죄수 9명의 번호의 합은 구할 수 있다. 반면, \(N+x\), 즉 모든 죄수가 부여 받은 번호를 10으로 나눈 나머지는 0과 9 사이의 정수 중 하나여야 함을 감안 했을 때, 다음의 전략을 사용한다면, 모든 경우의 수에 적어도 한 명(그리고 정확히 한 명)의 죄수는 본인에게 부여받은 숫자를 정확하게 맞출 수 있다.

• 번호를 부여 받기 전, 이마에 부여 받는 번호와는 별도로, 10명의 죄수가 0 부터 9까지 고유의 숫자를 정한다. 이 번호를 \(i\)라 하자.
• 모든 죄수가 이마에 번호를 부여 받은 후, 각 \(i\)번째 죄수는 다른 9명의 죄수의 이마에 붙은 숫자를 더 한 후, \((N+x\))를 10으로 나눈 나머지가 \(i\)가 되도록 \(x\)를 추측한다.

이는 굳이 10명의 죄수 뿐만 아니라 임의의 \(M\) 명의 경우에 모두 해당 되며, 힌트1번의 경우도 이 전략을 도입한 한 예로 볼 수 있다.