권성오 [vien] 04-10-25 23:09

 

  이 문제를 풀기 위해 머리를 짜내실 22분을 모집합니다. ^-^

김경환 [회의주의] 04-10-26 12:57

 

  제가 생각해본 방식입니다.

죄수들을 1번부터 23번까지 번호를 정합니다.
그리고 46일을 1주기로 합니다.

먼저 1주기(=46일)의 홀수날은 누구든지 a 스위치를 내려놓습니다. 즉 자기가 들어왔을 때 a 스위치가 올려져 있으면 내려놓고 내려져 있으면 b 스위치만 작동시킵니다.
이렇게 되면 a 스위치는 첫째날 내려져 있게 됩니다.
다음 두번째날 1번이 그방에 들어오게 되면 a 스위치를 올립니다.
만약 2번이 a 스위치가 올려져 있다는 걸 보았다면 2번은 4번째날 a 스위치를 올립니다.
만약 2번이 a 스위치가 올려져 있는걸 못 보았다면 1번은 안들어 온것이므로 2번은 4째날 a 스위치를 올리지 않습니다. 이때는 마찬가지로  3번이 자기차례인 6번째날 a 스위치를 올리지 않게 됩니다. 결국 23번은 44번째날 a 스위치가 올려지지 않은 것을 보고 누군가 안들어 온사람이 있다는걸 알게 됩니다.

그러면 다시 46일이 똑같이 진행됩니다.
만약 1번이 2번째날 들어와서 a 스위치를 올리고, 이를 2번이 확인햇다면 2번이 4번째날 a 스위치를 올리고, 마찬가지로 3번이 이를 확인했다면 6번째날 a 스위치를 올리고…… 이런식으로 진행되어 23번이 44번째날 a 스위치가 올라간게 확인된다면 23명 전부 들어왔었다고 선언합니다.

김진수 [stvalentine] 04-10-26 16:10

 

  2번이 4번째날 들어올지 안들어올지가 확실치 않죠. 1번이 이틀, 2번이 하루, 3번이 4일째 들어와버리는 수도 있습니다. 또, 중간에 15번쯤에서 갑자기 7번이 다시 들어가게 되는 경우라던가 하는 것도 생각 할 수 있겠군요.

권성오 [vien] 04-10-26 17:12

 

  몇번이 되든 한명씩 드나드니깐
아무나 자신이 한 3번정도 들어갔을 경우에.. "23명이 전부 들어왔다!!"
3번이나 들어갔는데 한 번도 안들어온 사람이 있다면
그건 간수가 죽일넘이죠 ㅋㅋ 사면 안시켜줄라고 ㅡ.ㅡ;;;;

자자 이 문제에 대해 같이 회의 하길 22명의 죄수를 모집합니다.

김경환 [회의주의] 04-10-26 22:55

 

  2번인 둘째날 안들어 온다면 2번은 1번이 들어왔다는 것을 확신할 수가 없게 되고, 따라서 자기 차례인 4번째날에 스위치를 올리지 않게 되고, 결국 3번도 역시 자기 차례인 6째날에 방에 들어 오게 된다면,  2번이 들어왔다는 것을 알 수 없었으므로 스위치를 못올리게 됩니다.
이런 식으로 하여 23번이 44번째 날에 들어왔을때 스위치가 올려져 있지 않게 되므로 모두 들어왔다는 선언을 할 수 없습니다.(물론 이날에 23번이 안들어 올 수도 있지만 이때도 결국 모두 들어왔다는 선언을 할 수 있는 23 번이 안들어 왔기때문에, 선언이 나오지 않게 됩니다)
따라서 죄수들은 선언이 나오지 않았으므로 미리 정해진 약속에 따라 47번째 날을 1번째 날로 하여 다시 2주기를 진행되게 됩니다.

하루에 한명만 들어가는 것이 아니라, 하루에 들어가는 사람 숫자는 제한이 없으니 간수 맘대로 임의적으로 들어가게 될것입니다.

따라서
둘째날 1번이 들어가서 올리고, 이걸 2번이 보고, 이후4번째날 스위치를 올리고,
4번째날 2번이 들어가서 올리고, 이걸 3번이 보고, 이후 6번째날 스위치를 올리고,
6번째날 3번이 들어가서 올리고, 이걸 4번이 보고, 이후 8번째날 스위치를 올리고,
.
.
.
42번째날 21번이 들어가서 올리고, 이걸 22번이 보고, 이후 44번째날 스위치를 올리고,
44번째날 23번이 들어가서 스위치가 올려져 있는걸 보게되는 경우가 생길 수 있으며,

이때 23번은 '스위치가 올려져 있는걸 보니 22번은 21번이 들어왔다는걸 확인했겠구나,
또 21번은 20번이 들어왔었다는걸 확인했었느니 올렸을테구,
또 20번은 19번이 들어왔었다는걸 확인했었으니 올렸을테구,
......
결국 2번도 1번이 들어왔었다는 걸 확인했었으니 올렷을 테니까 모두 들어왔었구
나" 라구 생각하고 선언을 할 수 있을 것입니다.



만약 중간에, 예를 들어 15번까지 이런 식으로 진행된후, 16번 부터 22번까지 안들어 오게되고, 23번이 44번째 날에 들어왔다면 23번은 스위치가 안올려 졌으므로 선언을 안하게되고, 사람들은 44번째날 선언이 안나왔으므로 다시 2주기를 진행하게 됩니다

이때에는 1번 부터 15번까지는 진행되었으므로 2번 부터 14번은 앞 번호 사람이 스위치를 올렸건 말건 상관없이 자기 차례에 스위치를 올리면 됩니다.(이미 한번 들어왔었다는 것이 확인되었으므로)

2주기에도 16번 이하의 확인이 이루어지지 않는다면 3주기로 진행하게 되고,
결국 언젠가는 선언을 할 수 있게되지 않을까 하는게 제 생각입니다.

권성오 [vien] 04-10-27 01:42

 

  결국엔 하루에 한명만 a스위치를 작동한다는 말이네요...
하지만 그렇게 한다면... 4번째날에 3번 죄수가 먼저 들어가구
2번 죄수가 나중에 들어가서 a스위치를 작동 했습니다.
그리고 5번째날로 넘어가서 5번 죄수가 먼저 들어가서 a스위치를 내려 놓습니다.
홀수날은 아무나 내려놓으신다고 했잖아요...
그럼 3번 죄수는 아직도 2번 죄수가 안들어온거로 알고 있잖아요...

여기서 다음 번 죄수가 a스위치를 내려논다고 하더래두....
전번 죄수가 a스위치를 올리구 다음 번 죄수가 2일간 그 방에 들어가지 않게 된다면
다 뒷번호의 죄수는 언제가 자기 차례인지를 잃어버리게 됩니다.

흠냐;;; 제가 이해를 못한건지 아직은 설명이 부족한건지.....

김경환 [회의주의] 04-10-27 09:22

 

  4번째날 3번 죄수가 먼저 들어가구 2번 죄수가 나중에 들어 가서 ,a 스위치를 작동한다면
3번 죄수는 2번 죄수가 들어왔다는 걸 확인하지 못한 상태가 됩니다.
5번째 날은 누구나 방에 들어왔을때 a 스위치가 올려져 있다면 내려놓기로 약속된 홀수날이고, 따라서 이날 5번 죄수가 들어왔다면 님께서 말씀하신대로 a 스위치를 내려놓게 됩니다.

다음날인 6번째날 , 3번 죄수는 님이 말씀하신대로 2번죄수가 들어왔다는 걸 모르는 상태이고, 따라서 a 스위치를 안올리게 됩니다.

3번이 안올렷으므로 4번도 안올리고,...5번도 안올리고........결국 22번도 안올리고...
이렇게 해서 23번은 선언을 안하게 됩니다.

제가 말씀드리고자 한건, 예를 들어 둘쨋날 2번이 들어와서 a 스위치를 올리고, 3번이 그 이후에 들어와서 a 스위치가 올려진걸 봤을 때만 3번이 자신의 차례인 6번째날에 a 스위치를 올린다는 것입니다.
이러한 조건들이 충족되지 않는다면, 47일째 (엄밀히 말하자면 46일부터도 가능하겠지만 계산의 편의를 위해서 47일로 생각) 를 다시 1일째로 보고 새로운 주기가 진행됩니다.

이번 주기에도 조건을 만족하지 못한다면 다음주기로 다시 넘어가게 됩니다.
2n 번째날 n번 죄수가 먼저 들어오고 n+1번 죄수가 다음에 들어오게만 된다면
23번 죄수는 모두가 들어왔다는걸 확실히 선언할 수 있게될것입니다.


간수가 어떻게 들여보내는가에 따라, 오래걸리긴 하겠지만, 결국 모두가 들어왔었는지 안 왔었는지를 확실히 알 수는 있을 거라고 생각되서 답변을 올렸습니다.

류민호 [hyundong] 04-10-27 10:38

 

  안녕하세요 회의주의님. 항상초보입니다.

답변에 조금 문제가 있어 보이는군요.

만약, 처음 a스위치가 올려져 있는 상태에서 시작하고
첫째날, 간수가 아무도 방에 들어보내지 않는다면 a 스위치는 그냥 올려져 있겠지요.
둘째날 2번을 들여보내면, 1번이 들어왔었다고 잘못 알겠네요.

김경환 [회의주의] 04-10-27 12:32

 

  안녕하세요 항상초보님...^^
오랜만에 뵙습니다.
안보이시길레 떠나신줄 알았는데..
예전 항상초보님이 멋지게 풀이하시던 모습을  다시볼 수 있을 것 같아 기쁘군요...

말씀해 주신대로 제 답변에는 그러한 경우에 문제가 있겠군요..
저는 당연히 하루에 한명이상은 들여보낸다고만 생각했었는데,
첫째날 아무도 들여보내지 않을 수도 있다는걸 간과했습니다.

지적 감사드리며, 다시한번 생각해보겠습니다.

류민호 [hyundong] 04-10-27 14:37

 

 
기록자 1명을 선정하고, 나머지 22명은 기록자에게 자신이 들어왔었다는 메세지를 보낸다.
메세지를 보내는 방법은, 기록자가 기록을 시작했다는 신호를 확인한 후에 오직 한 번 꺼진 B 스위치를 켜는 것이다.
메세지를 보내지 않을 때에는 A 스위치를 바꾸면 된다.

기록자가 기록을 시작했다는 신호는, 기록자에 의해서 B 스위치가 움직이는 것이 확인되는지의 여부이다.
기록자를 제외한 나머지 인원은, 기록자가 B 스위치를 움직였다는 것이 확인될 때까지는 B 스위치를 건드리지 않는다.

즉, 기록자를 제외한 나머지 인원은,
B 스위치가 꺼진 경우와 켜진 경우를 한 번씩 확인한 후에, 오직 한 번만 B 스위치를 켜서 메세지를 보낸다.
메세지를 보내지 않을 때에는 A 스위치를 바꾼다.

기록자는,
처음 들어갈 때 B 스위치를 끄고 (이미 꺼져 있으면 A 스위치를 바꾸고) 1에서 시작한다. (자기 자신)
다음부터는, B 스위치가 켜져 있으면 끄면서 기록에 1을 더하고, 꺼져 있으면 켜면서 기록에서 1을 뺀다.
기록이 23이 되면, 모두가 적어도 한 번씩은 들어왔다는 것을 알린다.

*** 켜져 있는 B 스위치를 보면, 1명에게서 메세지를 받았다는 사실을 알게 되므로 자신의 기록에 1을 더하고 B 스위치를 끈다.
*** 꺼져 있는 B 스위치를 보면, 자신이 기록을 하고 있다는 신호를 보내기 위해서 B 스위치를 켠다. 이 때 자신의 기록에서
*** 1을 빼 주어야 한다. 그래야 다음에 들어올 때 켜진 것(자신이 켠 것)을 끄면서 1을 다시 더해서 원래의 기록이 되니까.


위의 글은 제 풀이가 아니라, Mike Booth라는 사람의 풀이입니다. 이해하기 쉽도록 조금 바꾸어 설명해 보았습니다.

예전에 친구가 이 문제를 내서, 며칠을 이런저런 생각을 하면서 보냈던 적이 있었습니다.
결국 직접 풀이는 포기하고 인터넷에서 정답을 찾아서 알려준 생각이 납니다.
관심이 있으신 분들은 아래 site에 들러보시기 바랍니다. 링크된 곳들을 둘러보면 서로 다른 풀이들이 있습니다.

<a href=http://www.sunpig.com/martin/archives/2003/02/15/the_23_prisoner_problem_revisited/ target=_blank>http://www.sunpig.com/martin/archives/2003/02/15/the_23_prisoner_problem_revisited/</a>

권성오 [vien] 04-10-27 15:17

 

  헉 류민호씨한테 속았다.
들어가보니 온통 영어만 있었다는.... ㅜㅜ;;

권성오 [vien] 04-10-27 15:26

 

  기록자만이 b스위치를 내릴 수 있고 나머지 사람들은 b스위치를 올리거나  a스위치를 작동시킨다.
단 한 사람당 한 번씩만 b스위치가 내려와 있을 때 b스위치를 올린다. 그 외엔 b스위치를 손대면 안된다.
그리고 기록자가 b스위치를 22번 내지는 23번 내릴 경우에 "23명이 전부 들어왔다!!" 라고 선언!!
대략 이런 말 아닌가요? +_+

황선정 [woo7sun] 04-10-27 18:46

 

  만약 기록자를 한 번만 들여보내는 경우엔 어떻게 되는 거죠?-_-;;;;
간수가 지 맘대로 들여보낸다고 했으니-;;;

권성오 [vien] 04-10-27 19:00

 

  아무나 자신이 한 3번정도 들어갔을 경우에.. "23명이 전부 들어왔다!!"
3번이나 들어갔는데 한 번도 안들어온 사람이 있다면
그건 간수가 죽일넘이죠 ㅋㅋ 사면 안시켜줄라고 ㅡ.ㅡ;;;;

제가 전에 올린 글이에요.........

기록자는 기본적으로 23번 이상을 들어가야 되고
모든 사람이 기록자가 들어오길 기다렷다가 b스위치를 작동 시켜야 되니....
기본적으로 한달이상은 소유 될 듯 하네요...

김경환 [회의주의] 04-10-30 10:54

 

  그렇군요..
항상초보님 잘봤습니다..