|
:: 게시판
:: 이전 게시판
|
- PGR21 관련된 질문 및 건의는 [건의 게시판]을 이용바랍니다.
- (2013년 3월 이전) 오래된 질문글은 [이전 질문 게시판]에 있습니다. 통합 규정을 준수해 주십시오. (2015.12.25.)
통합규정 1.3 이용안내 인용"Pgr은 '명문화된 삭제규정'이 반드시 필요하지 않은 분을 환영합니다.법 없이도 사는 사람, 남에게 상처를 주지 않으면서 같이 이야기 나눌 수 있는 분이면 좋겠습니다."
21/07/07 18:36
에....? 보통 이런 경우 죄수는 일렬로 서있고 앞에 있는 모자색을 알 수 있다던가, 색깔은 흑백으로 정확히 5:5 분배되어있다던지 하는 조건들이 붙는데다 상의도 할 수 없는 문제가 있는데 이 문제는 조건이 너무 루즈하지 않나요?
21/07/07 18:39
아 제가 아까 못 본 조건이 있네요. 7색 중 어느 색이라도 중복 가능.. 전 중복이 안되는 줄 알고 '왜 이렇게 쉽지?' 생각했어요 흐흐..
21/07/07 18:49
동시에 답을 말하는게 아니라면 상의 시간에 2명씩 짝을 짓고 (한명은 깍두기 하고)
먼저 말하는 사람이 자신의 짝궁의 모자색을 말하면 되지 않나요? 그러면 자기 짝궁이 말한 색을 그대로 말하면 정답?!
21/07/07 18:52
(수정됨) 당연히 안되고요 상의는 모자를 쓰기 전에만 할 수 있습니다. 위에서 언급한 것처럼 서로에게 모종의 신호를 주는 것은 일체 불가능합니다. 단서는 무조건 자기를 제외한 나머지 사람들의 모자색밖에 없습니다.
21/07/07 19:05
색깔에 숫자를 부여하는게 맞는 것 같은데, 0, 1, 2, 3, 4, 5, 6
그래서 마지막 사람은 맞출 수 있을 것 같습니다?
21/07/07 19:09
모자가 골고루 배분되어있다는 가정하에 합 21;
사형수 A-G가 순서대로 있을 때, 21에서 자신에게 보이는 모자의 합계를 뺀 수에 해당하는 모자 색을 말함.
21/07/07 19:21
1. 모자가 골고루 배정되어있다고 가정하면 sum = 21;
2. 죄수는 한명씩 돌아가면서 21에서 자신이 보이는 모자 수의 합 s를 21에서 뺌 그리고 21-s 를 7로 나눈 나머지를 자신의 모자 색(예상 모자 값=exp)으로 호명하기로 정함 3. 마지막으로 말하게 되는 죄수는 앞의 6명에게서 얻은 exp 값과, 자신의 exp 값을 합하여 다시 7로 나누면 자신의 모자 색이 나옴. 모자 색 값을 R = 0 B = 1 이라고 했을 때 Ex) RRRRRRB 순번/21-s/exp 1. 21-1 % 7 = 6 2. 21-1 % 7 = 6 3. 21-1 % 7 = 6 4. 21-1 % 7 = 6 5. 21-1 % 7 = 6 6. 21-1 % 7 = 6 7. 21-0 % 7 = 0 6+6+6+6+6+6+0 = 36 36 % 7 = 1 1 -> B
21/07/07 19:15
모자를 쓰기 전, 죄수들은 다음과 같이 말하기로 정합니다.
1. 자기가 보기에 중복되는 색이 있음 -> 중복되는 색을 말한다. 2. 자기가 보기에 중복되는 색이 없음 -> 없는 색을 말한다. 3. 반복되서 말해진 색이 있다 -> 그 색을 이야기하기를 반복한다. 답을 설명하자면 이렇습니다. 중복색이 없는 경우와 있는 경우가 있습니다. 1. 중복색이 없음: ->첫번째 죄수는 없는 색을 이야기합니다. 첫번째 죄수는 정답을 맞춥니다. 2. 2개의 중복색이 있음: 2 가지 경우를 생각할 수 있습니다. 2-1. 중복되는 색의 모자가 2개가 있음. 죄수가 쓴 모자가 중복되는 색이기 때문에 죄수는 알지 못함. -> 첫번째 죄수는 없는 색을 이야기합니다. 정답이 아닙니다. -> 두번째 죄수는 중복색을 볼 수 있기 때문에 중복색을 이야기합니다. -> 세번째 죄수는 중복색을 볼 수 있거나 볼 수 없습니다. 2-1-1. 세번째 죄수가 중복색을 이야기하면 나머지 죄수는 같은 색깔을 이야기합니다. 최소 두 명은 정답을 찾아냅니다. 2-1-2. 세번째 죄수는 중복색을 보지 못하여서 다른 색깔을 이야기합니다. 이 경우 네 번째 죄수가 중복색을 이야기합니다. 나머지 죄수는 같은 색깔을 이야기합니다. 최소 두 명은 정답을 찾아냅니다. 2-2. 중복되는 색의 모자가 2개가 있음. 죄수가 쓴 모자는 중복색이 아님 -> 첫번째 죄수는 중복색을 이야기합니다. 2-2-1. 두 번째 죄수가 중복색을 볼 수 없습니다. 두 번째 죄수는 없는 색을 이야기합니다. -> 세 번째 죄수는 중복색을 볼 수 있습니다. 색이 반복되어서 이야기되었기 때문에 나머지 죄수는 같은 색깔을 이야기합니다. 최소 두 명은 정답을 찾아냅니다. 2-2-2. 두 번째 죄수가 중복색을 볼 수 있습니다. 두 번째 죄수는 색을 반복해서 이야기합니다. -> 나머지 죄수는 같은 색깔을 이야기합니다. 최소 두 명은 정답을 찾아냅니다. 3. 3개 이상의 중복색이 있음 -> 이 경우 역시 2.와 비슷한 알고리즘으로 결국 답을 찾아내게 됩니다.
21/07/07 19:29
생각해보니 2.의 경우에 중복색을 쓴 사람이 처음에 두 번 이야기해버리면 정답을 찾지 못하는 경우가 생기기 때문에 답에 미흡한 점이 있네요. 정답은 아닌 것 같습니다. 나중에 다시 한 번 생각해봐야겠군요.
21/07/07 19:26
보니까 죄수가 말한 색깔을 다른 죄수는 못듣는 제약이 있어야할것 같습니다
이것도 신호주기라서 안된다고 판단해야 하는건가 싶기도하고요
21/07/07 19:42
빨 주 노 초 파 남 보 를 각각 0 1 2 3 4 5 6 으로 생각한 다음,
7명의 모자 숫자의 합을 7로 나눈 나머지를 7명이 각각 0, 1, 2, 3, 4, 5, 6 으로 가정하여 각자 거기에 맞는 본인의 모자 색깔을 말합니다. 그럼 한 명은 맞추게 되어 있음
21/07/07 19:49
모자를 쓴 후에는 자기를 제외한 다른 이의 모자색을 제외한 그 어떤 정보 교환도 불가능하다가 문제에 제시된 조건이니, 내 모자 말고 다른 이의 모자색은 말해줄 수 있다는 건데..
다른 이의 모자색은 다른 이에게 말 할 수 있으면 그냥 너 빨간모자썼네? 한마디만 해 주면 되는 거 아닌가요..?
21/07/07 19:53
(수정됨) 모호한 점이 두가지 있습니다.
1. 색이 7가지 있다는 건 죄수들도 알고 있는 건가요? 똥색 같은 게 나올지도 모른다고 생각할 여지는 없는 거죠? 2. “모자를 쓴 후에는 자기를 제외한 다른 이의 모자색을 제외한 그 어떤 정보교환도 일체 불가능하다.” — 이 말은 모자를 쓴 후에는 의사소통이 일절 안되고 다른 죄수의 모자색을 보고 각자 혼자서 추리하는 것만 가능하단 말이죠? 다른 이의 모자색을 다른 죄수한테 전달할 수 있으면 문제가 성립이 안될 거 같은데요.
21/07/07 20:00
(수정됨) 7가지 색이라는 전제가 있으면 사전 논의 때 각자 색깔 하나씩 맡아서 그걸 그냥 답으로 쓰면 모자가 어떻게 나오든 무조건 해결이 될 것 같은데 문제가 이럴 리는 없을 것 같고 제가 뭔가 이해를 못하고 있는 거 같네요.
21/07/07 20:11
네 모자색은 7개중 랜덤으로 정해진다고 알고 있습니다. 각자의 추리를 다른 사람은 알 수 없습니다. 제가 문제를 좀 모호하게 냈네요.,
21/07/07 20:12
자신이 예측하는 색을 각각 다르게 부여.
1. 자신이 예측하는 색이 보이지 않는다면 자신이 예측한 색으로 답함 2. 자신이 예측하는 색이 보인다면 a. 가장 많이 보이는 색을 말함. b. 남은 모자들이 색별로 동수(초초초 파파파, 초초 파파 남남)라면 자신이 예측한 색을 말함.
21/07/07 20:24
모자를 쓴 후에는
자기를 제외한 다른 이의 모자색을 제외한 그 어떤 정보교환도 일체 불가능하다. 너 모자 이거이거이거야라고 애기하면 끝인데요???
21/07/07 20:40
음.. 제약사항이 이해가 안되는데 분배된 이후에는 서로 아무것도 보고 들을 수 없는 밀실된 방(각자 정답만 말하는)에 있다고 봐도 되는건가요?
아니면 각자는 생각한 정답만을 말하고 다른 사람들은 그 답과 실제 일치 여부를 들을 수 있는건가요? 후자인 규칙이면 모자 분배 전에 정답을 정할 로직을 미리 정해놓고 순서대로 계산한 모자 색을 말하고 마지막 사람이 모든 정보를 토대로 자기 모자를 맞출 수 있지 않을까.. 생각해봅니다.
21/07/07 21:06
문제 수정하셨네요. 음.. 그럼 해결방법이 생각나지 않네요
일단 단순 확률계산으로 사형당할 확률 = (6^7)/(7^7) 으오 0.34 정도 되니 대충해도 살 확률이 66% 정도 되네요. 66% 확률을 어떻게 100%로 만들거냐를 좀 더 고민해보면 될것 같은데.. 답은 다른분들이 맞춰주시는걸로..
21/07/07 20:43
엇 문제가 바뀌었네요.
혹시 현재 버전 문제 상에서는 죄수들끼리 사전에 논의하는게 어떤 의미가 있나요? 제 생각에는 별 의미가 없을 거 같은데요.
21/07/07 20:56
그럼 궁금한게 두가지 있는데요.
1. 모두 동시에 답을 적어서 내야 하는가? 2. 1번에서 동시에 내는게 아니라면 누군가가 맞았는지 혹은 틀렸는지에 대한 정보 정도는 알 수 있는가? 입니다.
21/07/07 21:13
색들에게 0~6까지의 숫자를 매기고
죄수들이 각각 0번부터 6번까지 번호를 정합니다. 그리고 각 죄수들은 모든 모자의 색 숫자의 합을 7로 나눈 나머지가 자기 번호와 똑같다고 가정한 상태에서의 답을 말합니다. 모든 모자의 색 숫자의 합을 7로 나눈 나머지는 0~6중 하나일수밖에 없기 때문에, 7명중에 한명은 무조건 답을 맞출 수 있습니다.
21/07/07 23:21
위에 정답이라는 방법대로라면 예를 들어 모자색의 번호가 0, 1, 1, 1, 3, 6, 6이라면, 첫 번째 죄수는 18을 7로 나눈 나머지 4라서 틀리고, 2~4번째 죄수는 17을 7로 나눈 나머지 3이라서 틀리고, 5 번째 죄수는 나머지 1이라서 틀리고, 6,7번째 죄수는 나머지 5가 나와서 다 틀리게 되는 것 같은데요. 제가 뭔가를 잘못 이해한 건가요?
21/07/07 23:29
(수정됨) 0번 죄수가 본 나머지는 4인데 자기의 고유번호가 0번이므로 3을 외칩니다.
1번 죄수가 본 나머지는 3인데 자기의 고유번호가 1번이므로 5를 외칩니다. 4번 죄수는 15를 보고 이는 나머지가 1인데, 자신의 고유번호가 4이므로 3을 외치고 이는 정답이 됩니다.
21/07/07 23:31
위에 정답이라고 하신 분들의 설명에는 그 고유번호에 대한 얘기가 없..다기 보단 좀 애매하게 설명된 것 같네요. 아래 설명해주신 거 보고 이해했습니다.
21/07/07 23:23
(수정됨) 정답 및 해설 올립니다. 처음에 문제의 조건들이 다소 부실했던 것 같습니다. 죄송합니다.
1. 빨,주,노,초,파,남,보 를 각각 0~6의 숫자로 생각한다. 2. 7인의 죄수또한 각각 0~6까지의 고유번호를 부여한다. 이를 a라 하자. 3. 자신을 제외한 모든 모자의 색을 1에서 정한 숫자로 치환하여 합한 뒤 7로 나눈 나머지를 구한다. 이를 b라 하자. 4. 7인의 죄수는 a-b를 구한뒤 1번의 색깔로 치환하여 정답으로 제출한다. 이 값이 음수일 경우 7을 더하여 계산하면 된다. ex> 고유번호가 3인 죄수가 자신을 제외한 모든 모자를 숫자로 치환하여 더했더니 30이었다면 7로 나눈 나머지는 2가 된다. 고유번호가 3이므로 3-2= 1 이므로 주황색을 답으로 낸다. 고유번호가 4인 죄수가 자신을 제외한 모든 모자를 숫자로 치환하여 더했더니 26이었다면 7로 나눈 나머지는 5가 된다. 고유번호가 4이므로 4-5 = -1인데 이때는 7을 더하면 6이므로 보라색을 답으로 낸다. 이런식으로 모든 죄수가 답을 말하면 반드시 한명은 맞게 된다. 여기까지 풀이인데... 솔직히 이해가 가지 않았습니다. 시뮬레이션해보면 반드시 7인의 죄수중 답을 말하는 이가 나오긴 하는데 왜 그런지, 또 어떤 죄수가 정답을 말하게 되는지 이해가 되지 않았습니다. 이렇게 생각해 보죠. 7인 전체의 모자색을 모두 더한 숫자를 7로 나누면 나머지가 0~6일수 밖에 없읍니다. 즉 전체합산수는 7m + k (k는 0에서 6의 자연수)입니다. 이 k를 전체나머지라 합시다. 이때 다른 사람은 다 때려치우고 고유넘버가 k인 사람만 주목해 봅니다. 이 사람을 A라 합시다. A는 전체합산수에서 자기의 모자숫자를 뺀 숫자만 알 수 있을 겁니다. 이를 7로 나눈 나머지를 개인나머지라 합시다. 만약 A가 쓴 모자가 0이라면 A의 개인 나머지 = 전체나머지 이므로 위의 4번식에서 계산한 숫자는 0이 됩니다. 만약 A가 쓴 모자가 1이라면 A의 개인 나머지는 전체나머지보다 1작으므로 위의 4번식에서 계산한 숫자는 1이 됩니다. 이런 식으로 A는 무조건 정답을 맞추게 됩니다. 간단히 하자면 전체 나머지가 k일때 고유번호가 k인 사람은 k에서 자신의 모자색숫자(n이라 합시다.)만큼 뺀 것을 관측하기 때문에 k - (k-n) = n 을 맞출 수 밖에 없습니다. 이와 같이 하면 x명의 사람과 x개의 서로다른 숫자 (색깔 -> 숫자로 바꾸면 되니까요) 를 가진 모자인 경우 모두 풀어 낼 수 있습니다.
21/07/07 23:35
https://www.youtube.com/watch?v=qOpx8V3gyjg
직접 시뮬레이션하는것도 나오는 영상입니다... 이해하기까지도 한참 걸리네요 흑..
21/07/08 11:15
순서대로 7을 나눈 나머지 숫자를 외친다고 하는데, 그거 자체가 정보 교환 아닌가요?
'어? 정보교환은 일제 금진데 숫자를 외쳐? 뭔가 합의된 뭔가기 있었겠지? 사형!' 문돌이라 그런지 풀이가 나왔는데도 납득을 못하겠어요. 크크.
21/07/08 11:37
나머지 숫자를 외친다..는 건 그냥 표현이고 나머지 숫자를 색으로 바꿔서 제출한다고 해도 마찬가지입니다. 남의 답은 중요한 게 아닙니다. 전체 나머지가 k일때 고유번호 k인 사람이 무조건 맞추게 되어 있습니다.
21/07/08 15:26
모자색의 범위가 빨주노초파남보 인것을 죄수들이 사전에 알고 있고, 모자를 쓰기 전에 상의할 수 있으면 7인이 각각 빨,주,노,초,파,남,보를 맡아서 적어내기로 하면 무조건 1명 이상은 맞출 수 있는 것 아닌가욤?
21/07/08 17:01
자기가 쓴 모자 색깔을 맞추는 것이 문제입니다. 색은 중복될 수 있고요. 문제를 다시 읽어 보세요. 님말씀대로 미리 정해 놓고 들어갔는데 정작 보, 남, 파, 초, 노, 주, 빨 순서로 썼다면 아무도 못 맞추겠죠.
21/07/08 20:03
음...일단 방법은
각자 자신의 모자 색을 각각 빨~보 -> 0~6 으로 치환하고 서로에게 배분 자신을 제외한 나머지 사람의 보이는 모자의 색을 더하고 자신의 값이 나올 X 를 더한 다음에 7 로 나눴을 때 자신의 값이 나오는 X 를 구한다. 그러면 7명중 최소 한명 이상은 본인의 모자 색을 맞출 수 있다는 거죠. 이걸 프로그램을 만들어서 돌려봤습니다. 랜덤값 : 3 , 5 , 0 , 6 , 4 , 5 , 0 에 대해서 죄수값 : 1 , 4 , 0 , 0 , 6 , 1 , 4 이 나옵니다. 그리고 일치하는 값이 1개 나오고요. 여러번 돌려봐도 1개씩만 나와서 여기서 (7+랜덤값 - 죄수값)%7 을 해봤습니다. 결과값 : 2 , 1 , 0 , 6 , 5 , 4 , 3 이 값이 나옵니다. 여러번 랜덤을 돌려봤지만 2 , 1 , 0 , 6 , 5 , 4 , 3 이 값이 순서만 바뀌고 동일하게 나옵니다. 즉, 저 공식을 사용하면 랜덤값과 죄수값이 6~0 만큼 차이나는 사람이 한명씩 있게 되고, 그중 차이가 0인 사람이 반드시 1명 있으므로 정답자가 1명 반드시 나온다고 할 수 있습니다. 왜 이런 결과가 나오는지는 조금 더 살펴봐야겠네요.
21/07/08 20:12
(수정됨) 그게.. 전체나머지가 k일때 고유값 k인 사람이 차이가 0이고 정답을 맞추게 되고, 나머지 사람들은 고유값이 k+1, k+2,,,,, k+6 이니까
1씩 증가 혹은 감소하게 될 수 밖에 없겠죠.
|
||||||||||