[펌]죄수와 달력 (죄수와 카드 업그레이드 버젼) - 꾀 어렵습니다
작성자 l 김우찬 [dncks0218] 등록일 l 13-01-31 13:29 조회 l 367
몇년전에 올렸던 죄수와 카드 기억하는 분 계실런지 모르계는데요
원문의 카드마술을 제가 죄수와 카드로 각색한 내용이었습니다
이번에는 한층 어렵게 업그레이된 버젼입니다
 
맨 뒤에 있는 죄수가 자기 모자뒤에 붙은 달력이 몇월 몇일인지 맞추면 모두 석방입니다. 틀리면 끔찍한 일이...

교도관이 1년치 365장의 달력 중 1,3,5,7월의 달력 124장중 5장을 골라 맨 앞의 죄수에게 줍니다.
맨 앞의 죄수는 자신을 포함한 다섯명의 모자 뒤에 달력 한장씩 끼웁니다.
물론 이때 맨 뒤의 죄수는 자신의 카드를 볼 수 없을 뿐만 아니라 달력이 다 꽂힐 때까지 눈을 가립니다.
죄수들은 서로 어떤 신호도 보낼 수 없습니다.
맨 앞의 죄수가 카드를 받기전에 전략회의를 가질 수는 있습니다.

어떻게 하면 모두 석방 될 수 있을까요? 

 
Source:     The best card trick, in Mathematical Intelligencer
게시글을 facebook으로 보내기 게시글을 twitter로 보내기
황미경 [binghwa] 13-02-01 11:21
 
혼자 풀기엔 벅차서 의견을 나누면서 같이 풀어야 할 것같은데요???
5명의 죄수 4가지 월이므로 중복되는 월이 생겨 첫째죄수와 마지막 죄수는 중복된 월의 카드를 가지면 월은 알 수 있고...
첫째 죄수가 같은 달의 하루를 가져가니까 마지막 죄수의 경우수는 30가지....

30을 어찌 나눌까요???
2~4번째 죄수를 제일 큰수, 큰수, 작은 수로 세울 수 있는 경우의 수는 6가지
그럼 1~5, 6~10, 11~15, 16~20, 21~25, 26~30 6가지 구간안으로 좁혀 구할 수 까지는 있는데.....
1~5를 어찌 나눠 구할까요?????흐음 흐음....
김우찬 [dncks0218] 13-02-01 14:06
 
맨 뒤의 죄수 눈에 보이지 않는 120가지 경우의 수를 나타내려면 5개가 보여야하는데 4개 밖에 안보이므로
이 4개의 순열(4!) 말고도 5가지 경우의 수를 나타내는 신호가 필요한데요.
그 방법으로 같은 월을 사용하여 이것의 위치를 고정 시키면 3! 밖에 못 쓰니까. 다른 방법이 필요합니다.
황미경 [binghwa] 13-02-01 16:52
 
120가지면 5!네요...근데 4명만 보이니 4!
5!이 되기 위해 5가지 경우수를 늘리는 방법....
흐음 흐음...머리가 녹슬었나봐요 ㅜㅜ
우찬님~오랜만에 왔는데 문제가 너~무 어려워요 ㅜㅜ
박준연 [3735943886] 13-02-03 21:49
 
124C5 = 124P4 (∵5!=120)임을 이용한 문제이므로, 문제에 등장한 월/일 등은 큰 의미없다 (아마도 124라는 갯수를 맞추기 위함으로 생각된다)

문제의 핵심은 124C5를 124P4에 1:1 대응시키는 방법을 알아내는 것이다

달력을 일련번호 순으로 0-123라고 가정할때, 임의의 5개를 선택

크기순으로 n0, n1, n2, n3, n4라고 하자

5번째 달력을 nx (x = n0+n1+n2+n3+n4 mod 5)로 선택하면

그외 선택되지 않은 4개의 수를 이용하여 각 구간별로 nx의 5로 나눈 나머지를 알 수 있다

전체 구간은 124에서 4개를 제외한 120개이며 5로 나눈 나머지를 알 수 있으므로 가능한 숫자는 24개

앞의 4숫자를 나열하는 방법은 4!이므로 5번째 숫자를 예측 가능하다
황미경 [binghwa] 13-02-03 22:15
 
죄수가 이미 서 있는 상태서 카드를 받나요?
아님 마지막죄수외에 4명의 죄수의 순서를 바꿀 수 있나요?
달력을 일렬로 배열하지 않고 굳이 죄수....사람을 일렬로 세웠다는건
키, 몸무게, 나이 이런걸로 정해 놓고 세울 수 있다는 것 아닐까요?
그럼 죄수 세우는 경우의 수와 달력배열 경우의 수로 충분히 구할 수 있을 것 같은데....

아니라면 5가지 경우의 수를 가정하에 두고 푸는 방법이란건데....
김우찬 [dncks0218] 13-02-04 13:06
 
그냥 달력으로만 답을 구할 수 있습니다.
박준연님 설명대로하면 답을 구할 수 있습니다.
이전의 죄수와 카드를 2006년에 올렸더군요. 그때 이 업그레이 버젼도 올렸어야하는데. 왜 이제야 올리는지 기억 안납니다.
지금은 저도 이런 문제 못풉니다. 3,4년 년만에 왔는데도 복잡한 문제는 짜증이 나네요. 예전에는 재미 있었는데.
앞으로 좀 쉬운거 올릴께요. 그런데 문제 만드는 것도 힘들어서 ㅠ.ㅠ
김우찬 [dncks0218] 13-02-05 13:58
 
달력의 종류는 총 124가지 입니다. 여기에 박준연님의 위 설명처럼 1월1일부터 7월31일까지  0~123까지 부여합니다.
이중 깔려있는 4개의 달력으로 줄 수 있는 정보는 순열로 24가지  합을 5로 나눈 나머지 5가지 정보를 줄 수 있습니다
맨 뒤 줄에 있는 죄수는 눈에 보이는 4개와 앞에 4사람이 보여주는 24*5 로 120가지 경우의 수를 가려낼 수 있는데요

어떻게 작전(Logic)을 짜야 눈에 보이지 않는 120가지 경우의 수를 unique하게 가려낼 수 있느냐가 문제입니다.
김우찬 [dncks0218] 13-02-05 23:43
 
처음 다섯개의 달력중에서 맨 뒷 사람에게 붙일 달력을 고를 때 어떻게 고르느냐가 관건입니다.
그리고 이를 어떻게 알려주느냐는 4개의 달력으로 해결해야겠지요
김경호 [rlarudgh] 13-02-08 21:39
 
만든 문제인가요 ?
절묘하게 잘 만들어진 문제인듯ㅋ
     
김경호 [rlarudgh] 13-02-12 21:03
 
답을 알았다고 생각햇었는데 오류였네요.답이 뭡니까 ㅜㅜ
이런 어려운 문제는 처음이야 ㅜㅜ
김우찬 [dncks0218] 13-02-12 21:00
 
퍼온 문제입니다. 문제에 source 써 놓았습니다
김우찬 [dncks0218] 13-02-13 08:15
 
[힌트] 푸는 방법은 위에 박준연님 얘기대로 나머지와 순열을 이용합니다
달력 5장의 나머지의 합 = 맨 뒤 1 장의 나머지 + 나머지 4장의 나머지
순열로 주는 정보는 맨 뒤장이 몇번째의 수인지를 알려주고 나머지 4장은 눈에 보입니다

1페이지에서 이 문제가 안 보이면 답 올릴께요
김우찬 [dncks0218] 13-02-14 11:37
 
[풀이]
우선 달력을 순서대로 0에서 123까지 순서를 정합니다.
골라낸 다섯장의 각각의 수를 5로 나눈 나머지를 구합니다
나머지들의 합을 구합니다 그리고 이 또한 0~4까지의 나머지로 표현합니다. 이를 ⑤라고 하겠습니다
5장의 달력을 순서대로 놓고 ⑤ 가 0이면 제일 작은 수 4면 제일 큰 수 이렇게 ⑤ 의 수에 따라 1장의 달력을 선택해서
맨 뒤의 죄수에게 붙힙니다. 그리고 그 수의 나머지를 ①이라 하겠습니다
이제 남은 4장의 합의 나머지는 ④라고 하겠습니다.
① = ⑤ - ④
4장빼고 나머지 120장을 다시 순서대로 번호를 매깁니다. 이때 맨뒤의 1장의 수는 항상 원래 수 - ⑤ 가 됩니다.
맨뒤의 죄수는 ⑤를 모르지만 ④는 알 수 있습니다. ① - ⑤ = - ④, 즉 나머지는 항상 -④ 가 됩니다
4장의 달력의 순서는 새로 부여한 수가 몇번째 -④ 인지를 나타냅니다.
예를들어 처음 다섯장이 12, 34, 56, 78, 91 이라면 ⑤ = 1 이므로 맨뒤는 두번째인 34, 이때 ① = 4, ④ = 2, -④ = 3
34는 4장을 빼고 120장중 33번째 나머지가 3인 수중 7번째 수
맨 앞의 죄수는 4장의 배열을 7을 나타내는 26, 12, 78, 91 순으로 배열합니다
맨 뒤의 죄수는 4장의 배열 7과 4장의 합의 나머지 2를 보고 자신의 달력 순서가 120장중 7 * 5 - 2 = 33 인 것을 압니다
33을 나머지 4장중에 끼워 넣으면 2번째입니다. 그러면 맨처음 ⑤ = 1 인 것을 알게 됩니다
맨 뒤의 죄수는 본인이 계산한 33에 4장중 33보다 작은 수의 개수 1을 더해 34가 자신의 수라는 것을 알게 됩니다
김경호 [rlarudgh] 13-02-14 13:39
 
노트에 쓰면서 해도 어렵네요 ㅎㅎ
포기 ㅋ
맞는 답인지도 모르겟다는 ㅎㅎ
김우찬 [dncks0218] 13-02-14 14:34
 
예, 어려운 문제였습니다

영문 원본 [풀이 20] 참조하세요

[문제 19] Five card trick
Two information theoreticians, A and B, perform a trick with a shuffled deck of cards, jokers removed.  A asks a member of the audience to select five cards at random from the deck.  The audience member passes the five cards to A, who examines them, and hands one back.  A then arranges the remaining four cards in some way and places them face down, in a neat pile.

B, who has not witnessed these proceedings, then enters the room, looks at the four cards, and determines the missing fifth card, held by the audience member.  How is this trick done?

Note: The only communication between A and B is via the arrangement of the four cards.  There is no encoded speech or hand signals or ESP, no bent or marked cards, no clue in the orientation of the pile of four cards...

[문제 20]
The two information theoreticians from puzzle 19 now attempt an even more ambitious trick.  It is in fact the same trick, but performed this time with a pack of 124 cards!  How does this trick work?

(Note: 124 cards is the maximum number of cards for which this trick can be performed.  The cards may be thought of as four suits with 31 cards each, or perhaps as days from a calendar, using the months January, March, May, and July.  Or they may be thought of as a double deck, with 20 extra cards from a third deck thrown in, bearing in mind that the magicians must be able to tell, perhaps from the design on the back of the cards, from which pack a given card is taken.  Or they may simply be numbered from 1 to 124.)

[풀이 20]
Number the cards in the deck 0 through 123: c0 < c1 < c2 < c3 < c4.  A selects card ci to hand back to the audience member, where i = c0 + c1 + c2 + c3 + c4 (mod 5.)
Now, suppose the four remaining cards sum to s (mod 5.)  Since all five cards sum to i (mod 5), ci , the hidden card, must be congruent to −s + i (mod 5.)  Therefore, if we renumber the cards from 0 to 119 by removing the four retained cards, the hidden card's new number is congruent to −s (mod 5.)
From here, there are exactly 24 possibilities remaining for the hidden card.  These can be conveyed by permutation of the four retained cards.

An example might help to clarify the method.  Suppose the audience member chooses card numbers 10, 34, 61, 78, and 93.
Encoding by A
We have i = (10 + 34 + 61 + 78 + 93) mod 5 = 1, so A hands card 1 (number 34) to the audience member.
After removing the other four cards and renumbering the cards, the hidden card's new number is 33 = 3 + 6×5, which is the 7th non-negative integer congruent to 3 (mod 5.)
Thus A uses the remaining four cards to encode the number 7, with the permutation: 61, 10, 78, 93.
Decoding by B
The remaining four cards sum to (10 + 61 + 78 + 93) mod 5 = 2, so the hidden card's new number (after removing the remaining four cards) must be congruent to −2 = 3 (mod 5.)
The permutation 61, 10, 78, 93 encodes 7, so the hidden card's renumbered number is the 7th non-negative integer congruent to 3 (mod 5); i.e., 33.
Precisely one of the four cards is less than 33, so the hidden card's original number was 34.
Source:    The best card trick, in Mathematical Intelligencer 24 #1
김경호 [rlarudgh] 13-02-14 14:35
 
겨우 뭔지 알것 같은데 머리에 쥐났네요.뭐 이런 경우가.
앗 원문 ..영어는 더 머리아픈 ㅜㅜ
김경호 [rlarudgh] 13-02-14 22:31
 
그림은 jul15 맞을까요
     
김경호 [rlarudgh] 13-02-18 05:24
 
수준 안맞아서 댓구도 하기 싫은건가요 ㅋ..
이정도는 간단하게 풀지도 못하는 인간과는 상대할수 없다는 뜻인가요 ㅋ..
좀처럼 댓구가 없는 이곳 ..
          
김경호 [rlarudgh] 13-02-18 05:25
 
아니면 밀어내기 한판 ? ㅜㅜ
너무 까다로운 곳 ㅜㅜ
               
김경호 [rlarudgh] 13-02-18 05:25
 
누군가 날 싫어하고 있는걸까 ㅜㅜ
                    
김우찬 [dncks0218] 13-02-18 16:50
 
죄송합니다. 못 봤습니다.
제가 계산하기에는 July.4 입니다
                         
김경호 [rlarudgh] 13-02-18 22:01
 
그런가요 ㅋ..
약간 실수가 있을것 같았지만 계산데이터를 지워버려서 ㅋ
                         
김경호 [rlarudgh] 13-02-19 03:29
 
심하게 헷갈립니다 ㅋ

해법을 보면서도 하루 지나면 이해가 안되는 ..
정말 고도의 지능을 요하는 문제인듯 합니다
                         
김경호 [rlarudgh] 13-02-19 07:42
 
불필요한 내용이지만 이런 오류를 범했네요.
답은 19번째 4인가 그럴겁니다
그걸 18 로 오인했고
4번째 18 로 해석
게다가 4번째 달의 18일로..
3을 더한것이 아니라 빼서 15로 ..
그렇게 계산 했던것 같네요.바보같죠
김우찬 [dncks0218] 13-02-19 08:53
 
저도 계산은 헷갈립니다
Jul.7 Jan.12 May.5 May.15 에 0~123까지 수를 부여하면 각각
99, 11, 66, 76 이고 이 4 수로 순열을 만들면 이순서는 크기 순으로 19번째입니다 그리고 4 수의 합의 나머지는 2 구요
19 * 5 - 2 = 93, 위 4 수중 93보다 작은 수는 3개, 93 + 6 = 96
96 = Jul.4
     
김경호 [rlarudgh] 13-02-19 14:37
 
실수를 하나 더했었네요..내가.
목록
번호 제목 작성자 날짜 조회
12416    [풀이] 저도 간단한? 특수연산기호 김우찬 13-02-15 64
12415 정신지체 장애자의 범위는 ? (7) 김경호 13-01-31 203
12414 [펌]죄수와 달력 (죄수와 카드 업그레이드 버젼) - 꾀 어렵습니다 (26) 김우찬 13-01-31 368
12413 멘사지식in] 몬티홀의 딜레마 문제 (17) 홍성준 13-01-30 312
12412 이것좀 해결해 주시기 바랍니다. 그림파일첨부 김동욱 13-01-26 178
12411 저울로 베어링 무게 분류하기 (3) 김우찬 13-01-25 133
12410 누군가 유에프오를 만들어서 타고 다닌다면 ? (13) 김경호 13-01-24 165
12409 도형추리 (12) 김우찬 13-01-22 319
12408    도형추리 (4) 김우찬 13-02-04 92
12407 고양이 이름맞추기 퀴즈 !! (4) 이용춘 13-01-21 142
12406 도형에 관심이 있다면 (2) 김경호 13-01-21 193
12405    도형에 관심이 있다면 (1) 김우찬 13-01-22 69
12404 탈출방법 (5) 김경호 13-01-17 229
12403 신기한 속도감 (3) 조현근 13-01-14 192
12402 특수연산기호 (5) 김경호 13-01-12 209
   11  12  13  14  15  16  17  18  19  20    

대표자 : 송필재
사업자번호 : 617-82-77792
06777  서울특별시 강남구 봉은사로 125 스파크플러스 B207 (논현동, 리스트빌딩)       TEL 02_6341_3177       FAX 02_3445_3177
copyright 2021    Mensa Korea.      All Rights Reserved.