재미난 논리 퍼즐. ( 사형수 )

사형수 n 명이 있는 막장교도소가 있어요.

근데 어느 날 교도관장이 심심해서 게임을 하나 해보기로 했어요.
그래서 사형수를 모두 모아두고 얘기했어요.

여기 거실에 스위치가 하나 있다. (ON or OFF)
몇 시간 뒤 너희들을 전부 각자의 독방에 가둘 것이다.
그리고 너희를 random하게 뽑아 한 사람씩 만 교대로 거실에 다녀갈 수 있게 해주마. 그 동안 스위치를 마음대로 해도 좋다.
만약 너희 모두가 한 번 이상 거실을 다녀갔다고 생각된다면 언제라도 보고해라. 만약 그 때 정말 모두 거실을 다녀갔다면 너희 모두를 풀어주마.
하지만 아니라면 모두 즉시 사형에 처한다.

문제의 명확성을 위한 전제조건.

1. 독방으로 가기 전 작전모의시간이 있다.
2. 거실 스위치의 처음 상태( 한 명의 ㅅ ㅏ형수도 거실에 가기 전의 상태 ) 는 교도관장이 알려주었다. 그 상태가 off 였다고 하자.
3. 시행 횟수가 굉장히 많아서 한 사람 당 꽤 많은 횟수( 모두가 거실을 다녀갈 수 있을 ) 만큼 거실을 들락날락 한다.

(다녀갈 때 마다 손톱 한 조각씩 흘리고 이런 거 안된대요.)
(저 스위치 그냥 모양만 스위치에요. 불 켜지거나 그러지 않아요.)




나의 답은.    드레그.

 
한 사형수를 정한다. ( 이 사람이 보고를 올릴 것이고 이 사람을 편의상 1번 사형수라 하자 )
 
1번 사형수는 거실에 갔는데 스위치가 off 이면  on 으로 바꾼다.
on 일 때는 바꾸지 않는다.
 
1번 사형수를 제외한 그 외의 n-1 명의 사형수는 거실에 갔을 때 스위치가 off 이면 그대로 두고,  on 이라면 off 로 바꾼다.
단, 스위치가 on 상태이더라도 한 번이라도 내가 on 을 off 로 바꾼 적이 있다면 그대로 둔다.
 
 
사형수는 처음 거실에서 off 인 것을 처음으로 on 으로 바꾼 뒤 부터 
자신이 거실을 갈 때 스위치가 off 인 횟수를       기억해 n-1 번 째 off 를 보게 되면
1번 사형수는 외친다.
" 우리 살려주셈 이제 다 거실갔다옴ㅋ "
 
살아난다.
 
 
이 방법을 조금 바꾸면 꼭 1번 사형수가 아니더라도  n명의 사형수 중 누구 하나라도 n명 모두가 거실을 들렸다는 것을 확신 할 수 있는 경우가 생길 수도 있습니다.
(즉, 보고를 하는 사람이 1~n 번 사형수 중 한 명이 될 수 있지요)