퀴즈7 20명의 사형수

20명의 사형수

내일 아침에 너희를 일렬로 세워놓고 파란모자나 빨간모자를 임의로 씌울 것이다.

임의로 씌우기 때문에 모두다 같은 색 모자를 쓸 수도 있고 한명만 빨강색 나머지는 파랑색을 쓸 수도 있다.

여하튼 간에, 아무도 자기가 쓴 모자 색을 볼 수 없다.

너희들이 볼 수 있는건 너희 앞에 있는 사람들이 쓴 모자색 뿐이다.

맨 뒤에 있는 사람은 19명의 모자색을 볼 수 있고

맨 앞사람은 누구의 모자색도 볼 수 없다.

뒤를 돌아봐서도 안되고 어떤 의사소통을 해서도 안된다.

맨 뒤에 있는 놈부터 차례로 자기가 쓴 모자의 색을 말해야 한다.

말할 수 있는 말은 "빨강" 혹은 "파랑" 뿐이며, 뒤 죄수가 말하는 소리는 들을 수 있다.

틀렸다고 바로 죽이는 것이 아니고 20명이 다 말한 이후 틀린놈만 모아서 사형을 집행 할 것이다.

자기 차례에 모자 색을 이야기 하는 것 이외의 어떠한 의사소통도 할 수 가 없다.

나는 자비로운 왕이므로 오늘밤 작전 회의 할 시간을 주겠다.

당신은 20명 중 가장 똑똑한 사형수다.

최대한 많은 사람을 구해낼 방법을 생각해내라.

모든 사형수는 당신의 방법을 따르며, 배반할 확률은 없다.

답은 아래로 내리면 있음.














답)
19명을 100% 살리고 1명은 50% 확률로 살 수 있음.
일단 제일 뒷 사람은 힌트고 뭐고 없기 때문에 제일 뒷 사형수는 살거나 죽거나 딱 50%이다.
그리고 제일 뒷 놈의 말이 중요하다. 앞에 있는 19명의 죄수가 쓴 모자 색을 센다. 19명이므로 둘 중에 한 색은 홀수개, 나머지 색은 짝수개 일 것이다. 예를 들어 빨강 모자가 홀수개면 파랑 모자는 반드시 짝수개 이다.
제일 뒤에 선 사형수는 자기 앞에 있는 모자의 색을 세서 홀수개가 있는 모자의 색을 말한다.
그렇다면 19번째 서있는 사형수역시 자신의 앞에 있는 모자 색을 셀 수 있기 때문에, 그것을 세본다. 만약 20번째 사형수가 "빨강!"이라고 외쳤고, 19번째 사형수가 봤을 때 자기 앞에 빨강모자가 짝수개가 있다면, 자신은 분명히 빨강 모자를 쓰고 있는 것이다. 왜냐면 20번째 사형수가 외친 색은 홀수개를 갖고 있는 모자의 색일텐데, 자기 앞에 있는 사형수들이 쓰고 있는 빨간모자는 짝수개 이기 때문이다. 그러므로 20번째 사형수가 빨강을 외쳤다면 19번째 사형수 역시 빨강을 외치면 살 수 있다.

이제 뒤에서 앞으로 자기 모자 색을 하나하나씩 외칠 때마다 남은 모자 갯수는 홀->짝->홀->짝 계속 변해 간다. 남은 사형수 들은 뒷 사형수가 외친 모자색으로 남은 모자색의 홀 짝을 유추해 가면서 답을 자기 모자 색을 알아내면 된다.

20명은 너무 많으니 6명으로 예를 들어 보겠다. ○은 흰색 모자 ●는 검정색 모자.(그냥 흰색, 검정으로 설명하겠음)
●●●○○● (왼쪽이 제일 앞)

제일 뒤에 있는 녀석은 불쌍하지만 희생해야 한다. 여튼 앞에 검정색이 홀수개 있고 하얀색이 짝수개 있으므로 미리 약속한 대로 "검정"이라고 외친다.
6번째 죄수 : "검정!"
그럼 5번째 죄수는 즉시 자기 앞에 있는 죄수들의 모자수를 센다. 검정이 홀수개. 흰색도 홀수개 이다.
근데 6번째 죄수가 홀수개가 있는 색은 검정이라고 알려줬기 때문에, 이미 자신의 시야에 홀수개가 있는 검정 모자를 자신이 쓰고있을 리가 없다. 그러므로 5번째 죄수는 흰색을 외친다.
5번째 죄수 : "흰색!"
4번째 죄수는 생각한다. 맨처음에 검정색이 홀수개 흰색이 짝수개였다. 하지만 5번째 죄수가 흰색을 외침으로써 검정색도 홀수개, 흰색도 홀수개가 되었다. 그리고 자신 앞에는 검정색이 홀수개 있다. 그렇다면 자신이 검정색일 리는 없다. 따라서 흰색을 외친다.
4번째 죄수 : "흰색!"
3번째 죄수도 즉각 계산한다. 검정색은 홀수개, 흰색은 짝수개가 남았다. 근데 자기 앞에 검정색이 짝수개 있다. 3번째 죄수에게 검정색은 2개 뿐이 안보인다. 그러므로 필연적으로 자신은 검정 모자를 쓰고 있을 것이다.
3번째 죄수 : "검정!"
2번째 죄수도 생각한다. 이제 검정색은 짝수개, 흰색도 짝수개가 남았을텐데, 자기 앞에는 검정모자 하나 뿐이다. 그러므로 자신도 검정색이다.
2번째 죄수 : "검정!"
마지막 남은 죄수는 위와 같은 추리 끝에 당연히 자신의 색을 알 수 있다.
이걸 20명으로 늘려도 원리는 똑같다.
이와 같은 방법으로 19명을 살리고 1명은 50%확률로 살릴 수 있다. 제일 뒷 죄수 지못미.