JHB의 프로그래밍 삽질기

퀴즈9 사형수 모자색 맞추기 3 본문

PROGRAMMING/Algorithm

퀴즈9 사형수 모자색 맞추기 3

roter 2011.08.05 14:41


퀴즈8에 대한 연속 문제임.
퀴즈8 : http://roter.pe.kr/244



퀴즈8과 조건은 같다.
퀴즈8을 다시 내보면

2명의 사형수가 있다.
사형 집행인은 요즘 심심해서 두명에게 재밌는 퀴즈를 내었다.(목숨을 건 퀴즈인데 재밌으려나?)
둘에게는 검정색 모자와 흰색 모자를 임의로 씌우는데, 자기가 쓴 모자의 색은 절대로 알 수가 없다.
서로 상대의 모자색만을 볼 수 있고, 이들이 살기 위해선 자신의 쓴 색의 모자를 맞춰야 한다.
단, 사형 집행인은 착하기 때문에, 둘 중 한명만이라도 자신이 쓴 모자의 색을 맞춘다면 둘 다 살려주겠다고 약속했다.
조건은 다음과 같다.
절대로 자신의 모자 색을 알 수 없다.
상대방의 모자 색은 알 수 있다.
둘 사이에는 어떠한 의사소통도 불가능하다. 행동(눈 깜빡임 등)으로도 알릴 수 없다.
둘 중 한명만 자기가 쓴 모자 색을 맞추면, 둘다 살 수 있다.
모자 색을 말하는건 동시에 말한다. 따라서 남이 말한것을 듣고 말하는 것은 안된다. 동시에 말해야 한다.

사형 집행인은 게임을 시작하기전에 둘이 협의할 시간을 잠시 주었고, 둘은 살아 남고 싶다.
두 사형수가 살아 남기 위해선 어떤 협의를 해야할까? 둘은 살아 남을 수 있을까?


인데, 여기서 2명을 7명으로 늘린다.
그리고 색도 7색으로 한다. 생각하기 쉽게, 빨주노초파남보의 7가지 색으로 한다.
임의로 씌우는 것이기 때문에 7명 모두 같은 색을 쓸 수도 있고, 빨빨빨노노초초 이렇게 쓸 수도 있다.
여하튼, 7명이 동시에 색을 말하고, 7명 중 한명이라도 자신의 머리에 쓴 모자의 색을 맞춘다면 7명 모두 살 수 있다.
7명 모두 사는 방법이 있을까?







답은 아래에
















답)
정수론의 모듈러로 접근해야 한다.
모자에 빨주노초파남보 순서대로 각각 0,1,2,3,4,5,6 이라는 번호를 붙인다.
그리고 사형수에게도 각각 0,1,2,3,4,5,6으로 번호를 붙인다.
사형수 들은 게임이 시작되고 모자가 씌어지면, 자신의 모자는 알 수 없지만 다른 사람의 모자는 볼 수 있다. 이제 다른 사람의 모자색을 숫자로 치환한 값을 모두 더한다. 그리고 그 값에 x를 더한 후 7로 나눈 나머지가 자신에게 부여된 번호와 같도록 하는 x를 말하면 된다. 그렇게 하면 7명 중 적어도 한명은 정확하게 자신이 쓴 모자의 색을 말하게 된다.
0번 죄수는 자신의 색을 제외한 나머지 모자의 숫자를 모두 더한 값을 7로 나눈 나머지가 0이 되도록 하는 x를
1번 죄수는 자신의 색을 제외한 나머지 모자의 숫자를 모두 더한 값을 7로 나눈 나머지가 1이 되도록 하는 x를
2번 죄수는 자신의 색을 제외한 나머지 모자의 숫자를 모두 더한 값을 7로 나눈 나머지가 2이 되도록 하는 x를
3번 죄수는 자신의 색을 제외한 나머지 모자의 숫자를 모두 더한 값을 7로 나눈 나머지가 3이 되도록 하는 x를
...
6번 죄수는 자신의 색을 제외한 나머지 모자의 숫자를 모두 더한 값을 7로 나눈 나머지가 6이 되도록 하는 x를
말한다.

그러면 7명중의 한명은, 자기가 계산할 때 사용한 나머지와, 실제 나머지가 같다. 적어도 한명은 같다. 그러니 걔는 정확하게 계산했을 테니 무조건 자기 색깔을 맞추게 된다.
실제로 전체 모자 합을 7로 나눈 나머지는 0부터 6까지 중에 하나기 때문에 한명은 맞추게 된다.

예를 들어 실제로 7명이 쓴 모자가 빨 주 주 주 노 노 초 라고 해보자
각각 0 1 1 1 2 2 3 이다.
0번 죄수가 나머지 모자 애들 합을 다 더했을 때 10이 나온다. 여기에 x를 더한 후 7로 나눈 나머지가 0이 되게 하기 위해선 4를 더하면 된다. 즉 0번 죄수는 4번 색(파란색)을 말한다.
1번 죄수가 나머지 모자 애들 합을 다 더했을 때 9가 나온다. 여기에 x를 더한 후 7로 나눈 나머지가 1이 되게 하기 위해선 6을 더하면 된다. 즉 1번 죄수는 6번 색(보라색)을 말한다.
2번 죄수가 나머지 모자 애들 합을 다 더했을 때 9가 나온다. 여기에 x를 더한 후 7로 나눈 나머지가 2가 되게 하기 위해선 0을 더하면 된다. 즉 2번 죄수는 0번 색(빨간색)을 말한다.
3번 죄수가 나머지 모자 애들 합을 다 더했을 때 9가 나온다. 여기에 x를 더한 후 7로 나눈 나머지가 3이 되게 하기 위해선 1을 더하면 된다. 즉 2번 죄수는 1번 색(주황색)을 말한다.
4번도 이런식으로 계산해서 말한다. 5번도. 6번도.

실제로 7개의 모자 숫자를 다 더하면 10이 나오고, 이를 7로 나누면 나머지는 3이 나온다. 7명의 죄수 그 누구도 7개 모자 숫자의 합을 진짜로 다 알 수 없기 때문에 6개만 더한 후 임의의 x를 넣어서 나머지를 0부터 6이 되도록 만들면 위처럼 적어도 한 명은 맞게 되는 것이다.

이해 하기 좀 힘들텐데 계속 보면 이해가 간다......
설명 능력이 부족해서 죄송 ㅠ
Tag
,
0 Comments
댓글쓰기 폼