[퀴즈] 아주 어려운 문제-죄수들을 전원 석방시켜라

[이기가byte]

1번부터 30번까지 번호가 부여된 독방에 30명의 죄수들이 수용되어 있다. 어느 날 왕이 30명 모두에게 석방될 기회를 줄 테니 죄수들은 각자의 이름과 방 번호를 써내라고 하면서 백지를 한 장씩 주었다. 중앙 로비에 1에서 30까지 번호가 붙은 상자 30개를 놓고 죄수들이 써낸 종이를 무작위로 상자마다 하나씩 넣을 테니 죄수 한명씩 로비로 나와서 자기 이름이 들어 있는 상자를 찾아내면 석방인데 각자에게 15번의 기회를 주겠다고 한다. 각자 15개 상자 뚜껑을 열어보는 동안 자기 이름을 찾아내야 한다. 왕은 나에게 죄수들을 도와주라고 하면서 전원 석방에 성공하면 내게는 큰 상을 내리겠다고 한다. 내가 그들을 도울 수 있는 방법은 게임이 시작되기 전에 죄수들과 작전회의를 할 수 있다는 것, 회의 후에 상자 안을 미리 살펴본 후 필요하면 왕이 넣은 이름이 적힌 종이를 맘대로 두개 맞바꾸어 놓을 수 있다는 것이었다. 작전회의 후에는 나와 죄수들은 어느 누구도 서로 의사소통을 할 수 없다. 어떤 작전으로 성공할 수 있을까?

[aksiz]

뭔가 조건이 더 필요할거 같은데요. 일단 두개를 맞바꾼다는건 결국 한쌍을 바꾼다는 이야기죠? (즉 상자 하나만 확정적으로 알려줄 수 있음)
그리고 죄수들이 상자를 찾아내는 순서가 정해져 있나요?
죄수가 자신의 턴에 상자의 내용물을 바꿔치기 할 수 있나요? (물론 이경우 바꿔치는것도 당연히 상자를 연거라고 포함해야 하겠지만)
죄수는 자신의 번호의 상자를 찾는 순간 바로 나가야 하나요?

[이기가byte]

이 문제는 답을 아는 사람이 아니라면 풀기 어려울 거라고 생각합니다.

<뭔가 조건이 더 필요할거 같은데요> - 더 이상의 조건은 필요치 않음
<일단 두개를 맞바꾼다는건....> - 두 개의 상자 내용물을 바꿔놓는다는 뜻
<죄수들이 상자를 찾아내는 순서> - 일정한 순서 없이 진행자가 무작위로 부르는 순서대로
<죄수가 상자의 내용물을 바꿔치기 할 수 있나요?> - 상자의 내용물 바꿔치기 불가
<죄수는 자신의 번호의 상자를 찾는 순간 바로 나가야 하나요?> - 즉시 자기방으로...

[구명랑]

자신의 번호의 상자를 찾는 순간이라는 건 15회를 다 열지 않더라도 중간에 자기 상자를 발견하면 즉시 끝난다는 이야기 인가요?

[루루시에]

우선 조건을 명확히 하기 위해 질문하겠습니다.

1. 15번 상자를 여는데 열었던 상자에서 자신의 번호를 찾아야 하나요?
ex) 1번죄수가 1~15번 상자를 열었지만 자신의 이름이 30번 상자에 있다고 말해도 되는가?
1-1. 1번이 가능하다면 15개를 다 열어본뒤 다른 죄수들이 상자를 다 열어본후 답해도 되는가?

2. 상자여는 횟수를 나눠도 되는가? 각 죄수가 처음에는 10번 다음에는 5번 등

3. 상자 안 종이를 1:1 교환하는데 조건은 없는가?
ex) 한 상자당 1번, 죄수당 1번 등
3-1. 만약 3번이 가능하다면 간단한 대수 비교로 1:1 교환이 가능한가?
ex) 15개 종이중 가장 큰 숫자를 열었던 상자 중 가장 뒷 번호 상자종이와 교환한다.

4. 15개의 상자를 선택 후 전부 한번에 열어 놓고 작업해도 되는가? (1:1교환을 위해)

[루루시에]

5. "상자 안을 미리 살펴본 후 필요하면 왕이 넣은 이름이 적힌 종이를 맘대로 두개 맞바꾸어 놓을 수 있다는 것이었다."
이 말은 죄수가 상자 선택하지 않아도 미리 바꿔도 된다는 건가요?

[루루시에]

5+ 이 역시 된다면 1:1교환에 횟수 제한은 없는가?

[구명랑]

답을 구했는데 원리는 아직 잘 모르겠네요. 우선 답을 씁니다.

요령은 간단합니다. 자기의 번호의 상자를 고른다음에 그 안에 들어있는 상자의 번호를 또 고르면 됩니다. 이건 죄수가 해야할 일입니다.

중요한 건 내가 할 일입니다.

상자 30개의 배치에서 최악의 경우는 죄수가 저 방식대로 했을 때 30번을 해서야 자기의 번호가 나오는 경우입니다. 그러면 아무 번호나 임의로 골라서 시험적으로 해본다음에 15번만에 자기의 번호가 나오도록 두개의 번호를 바꿔줍니다. 예를 들어서 1번 죄수가 15번째로 30번 상자를 열었는데 3번이 나왔다면 그 3번과 어딘가 있을 1번을 바꿔주면 됩니다. 그러면 신기하게도 모든 죄수번호가 다 15회 만에 자기 번호가 있는 상자를 열 수 있게 됩니다.

원리는 좀 더 생각해 보구요.

[구명랑]

원리를 알았습니다.

만약 1-2, 2-1 이라면 두 죄수번호는 둘다 2회만에 자기 번호를 찾습니다.
1-3, 3-2, 2-1 이라면 세 죄수번호는 셋다 3회만에 자기 번호를 찾습니다.
즉, 어떤 회수로 엮여 있는 번호들은 똑같이 그 회수만에 자기 번호를 찾을 수 있습니다.

만약 내가 봤을 때 15회보다 적은 회수로 연결되어 있는 숫자 그룹은 생각할 것도 없습니다. 15회보다 더 많은 회수로 연결된 것을 찾아 중간을 적당히 연결시켜주면 됩니다.
그럴때 최악의 경우가 바로 제가 답으로 설정한 경우입니다.

[이기가byte]

어려운 문제라고 생각했는데 구명랑님 대단하십니다.

작전 회의에서 죄수들에게 명심하게 해야 할 것은 1) 15개의 상자를 열어볼 때 첫 번째로 열 상자의 번호는 자신의 방 번호와 같은 상자로 시작할 것. 2) 첫 상자의 번호를 열었을 때 나온 번호가 두 번째로 열어볼 상자의 번호이고, 두 번째 상자에서 나온 번호가 세 번째로 열어볼 상자..... 이렇게 차례로 열어 가면 늦어도 15번째 상자에서는 자신의 이름이 100% 나온다는 확신을 갖게 할 것. 이렇게 약속을 한 후 나의 역할은 위처럼 했을 때 100% 성공하도록 상자 안의 이름과 번호가 적힌 종이를 두 개 찾아서 맞바꾸어놓는 일이다. 임의로 어떤 번호를 정하고(예:17번으로 정했다고 치자.) 그 번호(17번) 상자를 열어보면 어떤 번호가 나올 것이다. 두 번째로 열 상자는 17번에서 나온 번호의 상자이다. 이렇게 15개의 상자를 여는 동안 17번이 나오지 않으면 나머지 15개의 상자에서 17번을 찾아 15번 상자의 종이와 맞바꾸어 놓으면 어떤 번호의 상자로 시작해도 100% 성공하게 된다.