(어려움) 문제 투척

게시글 주소: https://dev.orbi.kr/0005366224

어느 교도소에 죄수 23명이 있고

어느 한 방에(어떤 변화도 알수 없는 즉 그 용도를 모르는)

스위치 ⓐ와 ⓑ 두개가 있습니다.

그 스위치의 처음 상태는 교도소장만 알고 있습니다.

둘다 오프일수도 둘다 온일수도 하나만 온일수도...있다는 겁니다.

죄수 23명은 오늘 하루만 서로 회의를 할 기회가 있으며

내일부턴 각자 격리 수용될 것입니다.

====================================================

내일부터 있을 일에 대해 설명 드립니다.

간수가 임의로 한명을 독방에서 꺼내어 그 스위치가 있는 방에 데려갑니다.

그 한명은 두개의 스위치중 "반드시" 한개를 변화시켜야 합니다.

반드시 ⓐ ⓑ 둘 중 하나를 온 혹은 오프로 바꿔야 합니다.

그리고 어떤 표시도 할수 없습니다. 그가 들어오기 전과 후의 변화는

스위치 하나의 on/off 일 뿐입니다.

이런식으로 하루에 몇번이 되든 한명씩 그 방에 드나듭니다.

한 명만 계속 들여 보낼수도 있습니다.

꼭 23명 모두룰 순서대로 들여보내란 법이 없다는 뜻입니다.

=====================================================================

여기서 문제가 문제가 나갑니다.

23명이 전부 한번 이상 들어갔음이 확실하다고 생각되면

누구라도 선언을 할 수 있다고 합니다.

"23명이 전부 들어왔다!!" 라고 선언을 하고나서

그 선언이 진실이면 전부 사면되고

그선언이 거짓이면 즉 한명이라도 그 방에 들어가지 못한사람이

있다면 모두의 사면 기회는 박탈됩니다.

오늘은 하루뿐인 대화의 시간입니다.

23명 모두 머리를 짜내어 사면의 기회를 잡아야 합니다.

어떻게 하면 될까요?

아래글은 헝가리 수학모임에서 나온 실제 원문 입니다.

======================================================================

This puzzle has been making the rounds of Hungarian mathematicians' parties.

The warden meets with the 23 prisoners when they arrive.

He tells them:

You may meet together today and plan a strategy,
but after today you will be in isolated cells and have no communication with one another.

There is in this prison a "switch room" which contains two light switches, labeled "A" and "B", each of which can be in the "on" or "off" position.
I am not telling you their present positions.
The switches are not connected to any appliance.
After today, from time to time, whenever I feel so inclined, I will select one prisoner at random and escort him to the "switch room", and this prisoner will select one of the two switches and reverse its position (e.g. if it was "on", he will turn it "off"); the prisoner will then be led back to his cell.
Nobody else will ever enter the "switch room".

Each prisoner will visit the switch room arbitrarily often.
That is, for any N it is true that eventually each of you will visit the switch room at least N times.)

At any time, any of you may declare to me: "We have all visited the switch room."
If it is true (each of the 23 prisoners has visited the switch room at least once), then you will all be set free.
If it is false (someone has not yet visited the switch room), you will all remain here forever, with no chance of parole.

Devise for the prisoners a strategy which will guarantee their release.

팔로우 3

0 XDK (+0)

유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.

지뢰찾기 [515915]

쪽지 보내기

알림
스크랩
신고

현실현실 · 450201 · 14/12/27 03:40 · MS 2013

그러니까 죄수입장에서 푸는건가요?
다른 죄수가 그 방을 들어간지 안간지는 모르고?

좋아요 0 답글 달기 신고
지뢰찾기 · 515915 · 14/12/27 03:41 · MS 2014

네
저는 답을 봐버렸음..어렵더라고요 ㅋㅋ

좋아요 0 답글 달기 신고
플루토늄 · 451090 · 14/12/27 03:43 · MS 2013

스위치가 바뀌어도 뭐 다른 외부적 변화는 없는거죠?
둘다 on이면 불이 켜진다거나 ㅋㅋㅋ

좋아요 0 답글 달기 신고
지뢰찾기 · 515915 · 14/12/27 03:44 · MS 2014

그런거 없습니다
스위치를 눈으로 보고 판단하는 방법밖에

좋아요 0 답글 달기 신고
현실현실 · 450201 · 14/12/27 03:46 · MS 2013

죄수들은 그 스위치를 보더라도 on off인지 모르는 상태 맞죠?

좋아요 0 답글 달기 신고
지뢰찾기 · 515915 · 14/12/27 03:47 · MS 2014

스위치를 보면 알 수 있습니다
초기상태가 공개되지 않을 뿐
그냥 우리가 쓰는 평범한 그런 스위치로 보시면 돼요

좋아요 0 답글 달기 신고
플루토늄 · 451090 · 14/12/27 03:48 · MS 2013

궁금해서 답 봐버렸는데 어렵네요 ㄷㄷㄷ

좋아요 0 답글 달기 신고
지뢰찾기 · 515915 · 14/12/27 03:49 · MS 2014

푼사람 천재인듯ㅋㅋ

좋아요 1 답글 달기 신고
현실현실 · 450201 · 14/12/27 03:50 · MS 2013

난이도가 잠들기 딱좋은듯 갈피도 못잡겠어요 ㅋㅋㅋ

좋아요 0 답글 달기 신고
지뢰찾기 · 515915 · 14/12/27 03:50 · MS 2014

그렇다면 긍정적 효과로군요ㅋㅋ
자고 일어나서 푸세요
네시임

좋아요 0 답글 달기 신고
한스 · 521684 · 14/12/27 09:15 · MS 2014

지금일어나서 보는데 이거보니 또 졸리네요ㄷㄷ

좋아요 0 답글 달기 신고
엽록체 · 519205 · 14/12/27 03:51 · MS 2014

죄수1,2,3…23이 있을 때 한 사람이 여러번 중복해서 입장 가능한가요? 예를들어 1이 입장한 뒤 2가 입장하고 다시 1이 입장한다던가요

좋아요 0 답글 달기 신고
지뢰찾기 · 515915 · 14/12/27 03:55 · MS 2014

네
간수 맘대롭니다
1번 넣고 12번 넣고 7번은 왕따시키면서 10년간 입장 안시키고..다 가능

좋아요 0 답글 달기 신고
현실현실 · 450201 · 14/12/27 03:53 · MS 2013

방에 들어가기전에 큰소리로 통성명하고 들어감ㅋ

좋아요 3 답글 달기 신고
재필 · 526541 · 14/12/27 03:56 · MS 2014

3번!!! 입장합니다!!!?

좋아요 1 답글 달기 신고
독립시행 · 483248 · 14/12/27 03:57 · MS 2013

(a b),(0,0)은 (a,0) or(b,0)으로(a,0), (b,0)은 (a,b),(0,0)로 바꿀 수 있음

전자든 후자든 처음 나오면 전자(a,0),후자(a,b)로 바꾸고 그 다음부터는 (0,b),(0,0)으로 바꿈 (a,0)을 본 개수+(a,b)를 본 개수가 처음으로 24번쨰 되는사람이 외치면됨

이러면 안되나요?

좋아요 0 답글 달기 신고
지뢰찾기 · 515915 · 14/12/27 03:59 · MS 2014

???뇌가 딸립니다..설명좀

좋아요 0 답글 달기 신고
독립시행 · 483248 · 14/12/27 04:03 · MS 2013

0이 안켜진거라고 하면
1. (a b),(0,0)은 (a,0) or(b,0)
2. (a,0), (b,0)은 (a,b),(0,0)로 바꿀 수 있음 자기가 방에 처음 들어가면 1의 경우에는 (a,0)으로 2의 경우에는 (a,b)로만 바꾸고 그 다음부터는 1의 경우에는 (b,0)으로 2의 경우에는 (0,0)의 경우로 하면 (a,0)+(a,b)의 개수<=47이 되지 않나요? 24번 47로..(연속으로 가도 그 다음에는 반대경우로 바꿀 수있으니까..)

좋아요 0 답글 달기 신고
현실현실 · 450201 · 14/12/27 03:58 · MS 2013

하하 궁금해서 답 봐버렸는데 궁금증이 더커짐 이해못함ㅋ

좋아요 0 답글 달기 신고
커피는레릿비 · 532214 · 14/12/27 03:59 · MS 2014

에이나 비중에 하나를선택하고(에이라고할게요) 한사람은 키는 역할을 합니다 그리고 나머지 사람들은 방에 들어갔을때 에이가 켜져있으면 끄면됩니다 키는역할을하는 사람은 수시로 왔다갔다하면서 에이스위치를 켜줍니다! 그리고 에이스위치를 적어도 23번째(처음에꺼져있을수도있으니까) 킬때 모두들어왔었음을 선언하면될듯하네요

좋아요 0 답글 달기 신고
커피는레릿비 · 532214 · 14/12/27 03:59 · MS 2014

자신없네요..ㅠㅠ

좋아요 0 답글 달기 신고
지뢰찾기 · 515915 · 14/12/27 04:01 · MS 2014

일단 답에 근접했습니다
1. 한사람이 여러번 들어올 수 있다
2. 초기상태를 알 수 없다
이것만 보완하면 완벽한 답일듯

좋아요 0 답글 달기 신고
커피는레릿비 · 532214 · 14/12/27 04:01 · MS 2014

저도사실그부분에서 자신이없어요 ㅜ어엋우느니 일단오늘은 잘래요 ㅋㅋㅋㅋㅋ

좋아요 0 답글 달기 신고
커피는레릿비 · 532214 · 14/12/27 04:02 · MS 2014

아아침에알바가야하는데 ㅠㅠㅠㅠㅠㅜ아여저ㅏ타렂어ㅓ찹 문제좀그만ㅋㅋㅋㅋ

좋아요 0 답글 달기 신고
독립시행 · 483248 · 14/12/27 04:06 · MS 2013

처음에만 a를 끄고 나머지는 b만 껐다켰다하고

초기상태를 알 수 없는거는 23번 스위치를 키는게 아니라 24번 스위치를 켜면 될 것 같네요

좋아요 0 답글 달기 신고
커피는레릿비 · 532214 · 14/12/27 04:08 · MS 2014

키는 사람 숫자빼야하니까 23아닌가여 ㅠㅠ

좋아요 0 답글 달기 신고
독립시행 · 483248 · 14/12/27 04:04 · MS 2013

우와 굿..

좋아요 0 답글 달기 신고
으어아으아으어으아 · 498562 · 14/12/27 04:26 · MS 2014

와ㅋㅋ나머지 22명은 두번째들어올때 부터 b만 건드린다 추가하면 답아님?

좋아요 0 답글 달기 신고
커피는레릿비 · 532214 · 14/12/27 04:29 · MS 2014

아하

좋아요 0 답글 달기 신고
커피는레릿비 · 532214 · 14/12/27 04:09 · MS 2014

그래서 답이뭔가여 ㅠㅠㅠㅠ잠이안오뮤ㅠ

좋아요 0 답글 달기 신고
시발점 · 418219 · 14/12/27 04:09 · MS 2012

처음 스위치 방에 들어가는 날을 1일로 설정
죄수마다 숫자를 정함. 1번부터 23번까지.
1일에는 (0, 1) 혹은 (0, 0)으로 만들기로 함.
그리고 2일에는 1번이 들어오면 (1, 0)이나 (1, 1)을 만듦. 이때, 1번이 안 들어왔으면 (0, 1) 혹은 (0, 0) ㅈ뺑이치기. 만약 1번 아닌 놈이 들어왔는데 (1, 0)이나 (1, 1)인 상태면 그 두개에서 ㅈ뺑이치기.
3일은 아무나 (0, 1)이나 (0, 0)을 만들어서 뺑이치기...
4일에는 2번이 들어온다면 (1, 0)이나 (1, 1)을 만듦...

이거 수첩에 기록해서 드래곤볼마냥 다 모은 사람이 외치면 됨.

ㅇ이거 석방될 수 있으려나

좋아요 0 답글 달기 신고
현실현실 · 450201 · 14/12/27 04:11 · MS 2013

그냥 감옥에서 삽시다ㅋ

좋아요 1 답글 달기 신고
knox · 510797 · 14/12/27 06:03 · MS 2014

회원에 의해 삭제된 댓글입니다.

좋아요 0
덕도날드 · 501475 · 14/12/27 08:09 · MS 2014

잉 근데 스위치의 변화를 카운트할 수 있단 근거가 어디있죠?
아 이해갔다

좋아요 0 답글 달기 신고
오르가즘 · 543130 · 14/12/27 09:09 · MS 2014

첫번째 죄수가 모두 들어왔다라는 선언을 하기로 가정, 첫번째 죄수를 제외한 나머지 22명의 죄수는 무조건 한 종류의(a) 스위치만 작동하도록 한다.
첫번째 입장하는 죄수는 초기 스위치의 on/off를 알 수 있으므로 1 2 1 3 1 4 1 5 ... 1 22 1 23 1 순서로 입장하며 1은 재입장할 때마다 a 스위치를 초기상태로 바꿔준다.

좋아요 0 답글 달기 신고
커피는레릿비 · 532214 · 14/12/27 09:49 · MS 2014

순서는 간수 맘대로에요 ㅋㅋ

좋아요 0 답글 달기 신고
YEEE · 486552 · 14/12/27 10:48 · MS 2013

답은 어디서 보나요??

좋아요 0 답글 달기 신고
SNU ECON · 487503 · 14/12/27 13:39 · MS 2014

한 사람이 A를 끄는 역할을 담당하고요. 나머지는 A를 켜거나 B를 켜고 끄는 역할을 해요. 그리고 이 나머지 사람들은 특정 조건 하에서만 A를 켜고 그렇지 않다면 B를 on/off하죠. 그 조건은 A가 꺼진 것을 처음 본 상황입니다. 즉, 방에 처음 들어와서 A가 꺼져있으면 이를 켜고, 켜져있으면 B의 상태를 변화시키고 다음번에 꺼져있을 때 켜는 겁니다. 그러면 A를 끄는 역할을 담당하는 사람이 23번을 끄면(자신을 제외한 22명이 A를 켜고 처음에 켜져있을 수 있으므로) 그 사람이 다 들어왔다고 외치면 되죠.
맞나요?

좋아요 0 답글 달기 신고
지뢰찾기 · 515915 · 14/12/27 19:27 · MS 2014

일단은 맞습니다
그런데, 초기상태가 켜진지 꺼진지 모르니, 모든 죄수들이 한번이 아니라 두 번씩 왔다 갔다는 사실이 보장되어야 하겠죠
고로 22가 아니라 44입니다

좋아요 0 답글 달기 신고
SNU ECON · 487503 · 14/12/27 19:51 · MS 2014

음...제 풀이에서 한명을 제외하곤 1인당 한번씩만 A를 켤 수 있기(끌 수는 없고요) 때문에 초기에 켜진 경우를 포함해서 23번 끄면 될거 같습니다. 굳이 두번 들어가야 한다고 하신 이유를 모르겠습니다

좋아요 0 답글 달기 신고