[문제적 남자] 빨주노초파남보의 모자를 쓴 7명의 죄수의 모자색을 맞춰라

1. Question

2. Approach

악명 높은 모자 쓴 죄수 문제....

걍 첨 보자마자, 못 풀겠거니 하고 편하게 봤다.

이 문제가 한술 더 뜨는게, 이젠 아에 전에 사람이 한 대답을 알 방법이 없다ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

그리고 문제에는 안나와 있지만 죄수들이 대답을 하는 순서도 교도관이 정해주기 때문에 나가는 순서로 꼼수를 부릴 수 없다고 한다ㅋㅋㅋㅋㅋㅋㅋㅋㅋ

당연히 내가 풀 수는 없었고 답을 보기로 했다.

수학 올림피아드에서 수상 경력있는 천재분이 답을 맞추셨다.

답을 봐도 모르겠다ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

하지만 역시 수학 천재, 왜 이게 답이 되는지 말씀해 주신다.

그래도 이해 안 됨ㅋㅋㅋㅋㅋㅋㅋㅋ

풀이는 다음과 같다.

1. 빨주노초파남보 7가지 색을 7에 대한 나머지 0~6에 차례로 대입한다.
2. 7명의 죄수는 차례로 빨주노초파남보 중 하나의 색 (0~6)을 담당한다.
3. 자신을 뺀 나머지 사람들의 모자 색깔의 합을 구한다.
4. $(모자 색깔의 합 + x)  \bmod 7 = 자신이 담당한 색깔$이 되도록 하는 x를 찾는다.
5. 7명 중 한명은 x에 해당하는 색깔이 자기 모자 색깔이다.

여러분은 저 루틴을 돌면 무조건 자기 모자 색깔을 맞추는 1명이 나온다고 확신이 드는가?

난 그렇지 않다...

다행이도 유튜브 댓글에 해설을 주신 분이 있어서 이해했다.

색깔 분포	빨강(0)	주황(1)	노랑(2)	초록(3)	파랑(4)	남색(5)	보라(6)
죄수(맡은 색)	0	1	2	3	4	5	6
자기 색	파랑	빨강	주황	노랑	초록	노랑	파랑
색 번호	4	0	1	2	3	2	4
보이는 색 합	12	16	15	14	13	14	12

결국 요점은 정답과 자신의 차이(0~6까지 나올 수 있음)를 각자에게 배분하는 것이다.

• 실제로 0번 죄수의 경우 $x = 2$이기 때문에, 노랑을 대답한다. 이 값은 원래 자기 답에 -2 (7에 대해 5와 합동)이다.
• 1번 죄수의 경우 $x = 6$이기 때문에, 보라를 대답한다. 이 값은 원래 자기 답에 6이다.
• 2번 죄수의 경우 $x = 1$이기 때문에, 주황을 대답한다. 이 값은 원래 자기 답에 0이다.
• 3번 죄수의 경우 $x = 3$이기 때문에, 초록을 대답한다. 이 값은 원래 자기 답에 1이다.
• 4번 죄수의 경우 $x = 5$이기 때문에, 남색을 대답한다. 이 값은 원래 자기 답에 2이다.
• 5번 죄수의 경우 $x = 5$이기 때문에, 남색을 대답한다. 이 값은 원래 자기 답에 3이다.
• 6번 죄수의 경우 $x = 1$이기 때문에, 주황을 대답한다. 이 값은 원래 자기 답에 -3 (7에 대해 4와 합동)이다.