죄수의 구슬

인터넷에서 본 유사 문제를 제 맘대로 각색했습니다.

 

100명의 죄수가 감옥에 있습니다. 죄수들은 독방에 있고 서로 의사소통하지 못합니다. 왕이 생일을 맞아 죄수들을 풀어주려고 불렀습니다. 왕이 내는 문제를 맞추면 모두 자유의 몸이 되는 것이지요. 왕이 말합니다.

 

"지금 간수들이 너희의 방에 구슬이 들어 있는 자루를 하나 씩 넣고 있다. 방으로 돌아가면 자루 속에 구슬이 몇 개 들어 있는지 확인할 수 있지.  구슬 수는 random이다. 아예 구슬이 없는 자루도 있을 수 있고 아주 많은 자루 적은 자루 제각각이지. 이제부터 너희는 자기 방의 구슬 수를 너희 중 누구에게도 알게 해서는 안 된다. 너희 중 누구든 전체 구슬 수를 정확히 맞추면 모두를 풀어 주마.

 

너희는 방에 가서 구슬 수를 확인한 후 여기 다시 모이게 된다. 그 때 부터 원하는 이 누구나 내키는대로 한 명 씩 저기 간수실로 들어가서 칠판에 (자기 구슬 수는 제외하고) 무엇이든 적고 나올 수 있는데, 간수는 그 다음에 들어온 이가 칠판을 보는 즉시 지울 것이다. 한 명이 몇 번을 들어가도 좋고 아예 안 들어가도 상관 없지만, 더 이상 들어갈 사람이 없으면 누군가가 전체 구슬 수를 맞춰야 한다. 이제부터 너희는 작전 회의를 해도 좋다."

 

작전 회의가 끝나고 나면 게임이 시작되고 죄수들이 서로 의사소통할 기회는 없습니다. 어떤 전략을 짜서 행하면 문제를 충족할 수 있을까요? 단, 간수를 속일 수는 없으며 누구든 자기 구슬 수를 다른 이가 (말하든 보여 주든 몸짓이나 추론으로써든) 알게 해선 안됩니다.