7인의 사형수 또는 죄수 문제

사내 게시판에 어떤 분이 올려놓으신 글을 보고 공유합니다.

2017년에 문제적 남자에서도 출제되었던 문제인데요.

 

봐도봐도 이해가 안가고 엑셀로 정리를 해봐도 이해가 안가네요.

 

문제는 이렇습니다.

어느 왕국에 왕이 있었다. 이 왕국의 왕은 그의 감옥에 있는 죄수들에 대해서 놀라운 소식을 듣는데,
감옥에 있는 죄수 중 7명이 너무 지혜롭다는 소문이었다.

왕은 그래서 이들을 시험하기로 하였고. 죄수 7명들을 불러들였다.
그리고는 말하였다.

내가 내일 너희들에게 안대를 씌운 후 모자를 씌울 것이다.
나에게 모자는 빨강색 7개, 주황색 7개, 노랑색 7개, 초록색 7개, 파랑색 7개, 남색 7개, 보라색 7개,
즉 7개의 색의 모자를 각각 7개씩 총 49개의 모자가 있다.
각자에게 다른 색깔의 모자를 씌울 수도 있고 전부 같은 색의 모자를 씌울 수도 있다.

안대를 벗은 후 상대방의 모자색은 볼 수 있지만 자신의 모자의 색은 볼 수 없다.
너희들은 아무 상의없이 서로 가르쳐주는 행위 없이 각가 자신의 모자의 색을 나에게 알려줄 것이고
단 한 명이라도 자신의 모자색을 맞추는 자가 있다면 너희 7명 모두를 풀어주겠다.
만약 한 명도 모자색을 맞추지 못한다면 너희 전부를 사형집행하겠다. 하겠느냐?

그 후 죄수 7명은 상의 후에 하겠다고 대답하였고, 다음 날 7명의 죄수들은 모두 석방되었다.

이 문제를 어떻게 풀어낼까요?

 

해법이 떠오르시나요?

 

 

모자 색깔별로 숫자를 대입해서 풀면 될 것 같다는 느낌은 드는데...

죄수들은 상의 후에 해법을 어떻게 찾아냈을까요?

 

여러분들은 해법이 떠오르시나요?

 

단계별로 하나씩 알아보겠습니다.

먼저 빨주노초파남보의 모자색을 0~6까지의 숫자로 지정을 합니다.

빨	주	노	초	파	남	보
0	1	2	3	4	5	6

죄수도 7명, 모자의 색도 7가지...

각 죄수별로 한가지의 색을 정해서 그 색을 자신의 색으로 할당해줍니다.

죄수A	죄수B	죄수C	죄수D	죄수E	죄수F	죄수G
0	1	2	3	4	5	6

아직 자신의 모자색은 모르고, 어떤 색이 될지도 모르지만 숫자를 하나씩 가지는 것이지요.

이 색깔이 자신의 색이라고 믿고 가는 것이 아니므로 헛갈리지 않도록 조심하세요.

 

자신의 모자색은 볼 수 없지만 다른 죄수들의 모자는 볼 수 있으므로

자신의 모자색을 제외한 나머지 죄수들의 색을 다 더해봅니다.

 

이즈음에서 이해를 돕기위해 각 죄수들의 모자색을 가정해보겠습니다. 

죄수	A	B	C	D	E	F	G
모자	3	3	0	1	4	2	6
합산	16	16	19	18	15	17	13

모든 모자의 합산수는 동일하고, 전체 모자색수의 합에서 자신의 모자수를 뺀 것이 바로 이 합산수입니다.

모자에 할당된 숫자중 가장 큰 수는 6이므로 이 합산수를 7로 나누어 보겠습니다.

7로 나누면 나머지는 0~6까지의 수가 나오겠지요.

 

바로 이 나머지가 앞에서 각자가 할당받은 숫자와 같도록 숫자를 더해서
그 숫자를 자신의 모자색으로 삼는 것이 해법입니다.

죄수	A	B	C	D	E	F	G
할당수	0	1	2	3	4	5	6
모자	3	3	0	1	4	2	6
합산	16	16	19	18	15	17	13
나머지	2	2	5	4	1	3	6
발표	5	6	4	6	3	2	0

표로 정리해보면 죄수 F가 정답을 맞추게 되었네요.

이로써 모두가 살아났습니다.

 

해법은 이렇게 나왔고 확인도 했습니다만

이게 이런 케이스에서 우연히 맞은 것인지 모든 케이스에서 맞는 것인지를 모르겠네요.

 

이해는 나중에 하기로 하고 일단은 엑셀에 함수로 정리해보았습니다.

모자색을 변경해가면서 확인해보았는데 일단 지금까지는 죄수들이 사형당하지 않고 살아있습니다.

 

제가 만든 엑셀 파일을 첨부해드리오니 모자색 열을 변경해서 확인 해보셔도 좋겠습니다.

7인의 죄수 문제.xlsx

0.01MB

해법에 대한 이해는 시간을 갖고 생각해보아야 할 것 같습니다.

생각이 정리가 되고 이해가 되면 다시 글 남기겠습니다.

 

주말이 다가오는 목요일... 즐거운 저녁시간 되세요.