[문제적 남자] 흰색, 검은색 모자를 쓴 죄수를 최대한 많이 감형시키는 방법은?

1. Question

2. Approach

이전 포스트와 같이 난해한 문제이다. 구글 입사시험 문제였다고 한다.

둘씩 짝지어서 1명은 상대방의 모자 색깔을 부른다는 방법이 있다. 이 방법은 1명은 자신의 모자색깔을 불러줬기 때문에 감형받을 수 있지만, 상대방의 색깔을 불러준사람은 상대방과 자신의 색깔이 같은 때만 감형받을 수 있으므로, 기댓값은 75명이다.

이전 빨간 모자 파란 모자문제에 영향을 받아 흰색 모자에서 검은색 모자로 바뀌는 순간 어떻게 해보려고 했으나 역시 답이 안나와서 GG.

답은 뒷 사람의 대답을 기반으로 자기가 알고 있는 흰색 모자의 홀짝여부와 직접 확인한 모자의 홀짝여부가 같으면 검은색 다르면 흰색이라고 대답한다 이다.

6	5	4	3	2	1
B	B	W	W	B	W

먼저, 맨 뒷 사람은 앞 사람들의 흰색 모자의 개수를 세고 짝수면 흰색 홀수면 검은 색이라고 대답한다. 이는 자신의 모자 색깔과는 관련이 없으므로 맨 뒷 사람이 감형받을 확률은 50%이다.

5번째 사람부터는 자기 앞에 흰색 모자의 홀짝여부가 자신이 본 것과 같으면 검정 다르면 흰색이라고 대답한다. 5번째 사람은 자기 뒷 사람이 검은색 (자기 앞에 흰색 모자의 개수가 홀수개)이라고 대답했는데, 자기 앞에 흰색 모자의 개수도 홀수이므로, 자신이 검은 모자를 쓰고 있다는 것을 알게된다. 검정이라고 대답한다.

4번째 사람은 뒷 사람이 검은 색이라고 대답했기 때문에, 흰모자의 개수가 변하지 않았다는 것을 알 수 있다 (여전히 홀수개). 하지만 자신이 세어 보니, 흰모자의 개수가 2개로 짝수이다. 따라서 자신이 검은 모자를 쓰고 있다는 것을 알게된다. 흰색이라고 대답한다.

3번째 사람은 뒷 사람이 흰색이라고 대답했기 때문에, 흰모자의 개수가 변했다는 것을 알 수 있다 (흰모자의 개수가 짝 수개). 하지만 자신이 세어 보니, 흰모자의 개수가 1개로 홀수이다. 따라서 자신이 검은 모자를 쓰고 있다는 것을 알게된다. 흰색이라고 대답한다.

2번째 사람은 뒷 사람이 흰색이라고 대답했기 때문에, 흰모자의 개수가 변했다는 것을 알 수 있다 (흰모자의 개수가 홀 수개). 자기 앞에 흰색 모자의 개수도 홀수이므로, 자신이 검은 모자를 쓰고 있다는 것을 알게된다. 검정이라고 대답한다.

맨 앞 사람은 뒷 사람이 검정이라고 대답했기 때문에, 흰모자의 개수가 변하지 않았다는 것을 알 수 있다 (흰모자의 개수가 홀수개). 하지만 자신앞에 사람이 없어, 흰모자의 개수가 0개로 짝수이다. 따라서 자신이 흰 모자를 쓰고 있다는 것을 알게된다. 흰색이라고 대답한다.

이 경우, 감형받는 사람의 기댓값은 99.5이다.