음슴체로 쓰는게 저한테도 읽는사람한테도 편할거같아서 그냥 그렇게 쓰겠습니다 ㅋㅋㅋ (문제는 여기에 있습니다.) 우선 문제를 다시한번 요약하자면 다음과 같음 ① 100명의 죄수들이 한줄로 서있는데, 앞쪽을 보고있어서 자신의 앞에 서있는 모두의 모자를 볼 수 있도록 되어이씀 (예를 들어 맨 뒤에서 두번째 죄수는 98명의 모자를 볼 수 있는거임) ② 그 후 100명의 죄수들에게 검은색 또는 흰색의 모자를 씌우고, 교도관은 맨 뒷 죄수부터 자신의 모자가 무슨 색인지를 물음 (즉, 교도관은 처음에, 다른 모든 죄수들의 모자를 볼 수 있는 죄수에게 묻는거임) ③ 이 때, 다른 죄수들은 앞의 죄수들이 한 말들을 들을 수 있음 ④ 그래서 맞추면 풀어주고, 틀리면 ㅈㅅ ⑤ 대신 죄수들은 어떤 전략을 사전에 세울 수 있다! 그러면 무엇이 최상의 전략일까? 문제를 처음보시는 분들을 위해 우선 생각나는 두가지 방법을 적어보면 다음과 같음 1. 전략같은소리하네 아몰라 귀찮아 하면서 그냥 닥치고 찍는다고 하자. 그러면 모자 색깔이 두개니까, 확률 1/2 해서 한 50명 정도 풀려날 것이라고 합리적으로 예측할 수 있ㅋ음ㅋ 2. 조금 더 돌머리를 써서 전략을 짜보면,,, 우선 맨 뒷사람이 바로 앞사람의 모자를 말하는 것임. 그러면 그 앞사람은 자신의 모자를 반드시 맞출 수 있게되고, 98명이 남게되는데, 그 중 또 맨 뒷사람이 바로 앞사람의 모자를 말하고 뭐 이딴식으로 하면 50명은 석방을 보장받고, 나머지 50명은 찍는거나 똑같으니 절반 25명쯤 살겟지 해서 한 75명쯤 석방될 것이라고 추측할 수 있음 그러나 이것도 궁극의 전략이 있으니, 문제 글에서 보도블럭님이 말씀해주셨듯, 읊자면 다음과 같다. 일단 맨 뒷사람이 찍어야 하는 건 어쩔 수 없지만, 엄청난 정보를 흘리면서 찍는 것임 맨 뒷사람이 앞의 99명 모자 중 흰색의 개수를 세어서, 홀수면 흰색이라 말하고 짝수면 검은색이라 말함 뭐 예를들어 흰색이 홀수개였다고 치자. 그러면 작전대로 맨 뒷사람은 흰색이라고 말할 것이고, 그 앞사람의 차례에서, 자기 앞의 98명의 모자를 보고 흰색 모자의 개수를 세었을 때 흰색이 짝수개인 것을 확인하였다... 면?!!?!!! 자신의 모자가 흰색이라는 말이 된다! 반대로 흰색이 그대로 홀수개인 경우에는, 자신의 모자가 검은색인 것을 확신하는 것임! 예를 들어 두번째 사람도 흰색을 불렀다고 해보겠음. 석방자들은 도미노처럼 줄줄이 이어짐. 그 앞사람, 그러니까 맨 뒤에서 세번째 사람의 경우를 살펴보게씀 우선 맨 뒷사람이 전체의 흰색이 홀수개라고 알려준 셈이고, 그 앞사람이 흰색을 불렀으니 자신의 모자를 포함한 98개의 모자 중 흰색 모자의 개수는 짝수개라는 것임! 이제 자신의 앞에 보이는 97개의 모자 중 흰색 모자를 다시 세어서, 그대로 짝수이면 자신의 모자가 검은색이라는 것이고 홀수로 바뀌어 있으면 자신의 모자가 바로 흰색이라는 것이 되는거임... 이런 퀴즈를 보아도 계속 문제를 확장시켜나가는게 수학에서 도움이됨 ㅋㅋㅋ 한번 색깔을 빨노초 3개로 늘려보게씀. 이 문제를 쉽게 풀기 위해 우선 검은색흰색 문제를 조금 다른 각도에서 해석해보게씀 짝수 홀수 성질로 풀긴 했지만 결국 이거는, 흰색을 1, 검은색을 0으로 보고 푸는게 쉬움 이제부터 색깔이랑 숫자랑 용어를 같은 맥락에서 사용하겠음 우선 맨 뒷사람은 보이는 숫자을 다 더하고 2로 나눔. 그래서 1이 남으면 흰색이라 외치고, 0이 남으면 검은색이라 외치는거임... 그러면 그 다음사람은, 뒷사람이 외친 숫자(?)에서 자신이 보이는 숫자들을 다 더해 2로 나눈걸 뺌. 그걸 부르면 되는거임. 행여나 0에서 1를 빼야하는 상황이 올 수 있는데, 우선 강제로 빼서 -1 만들고 2로 나눠서 나머지 1이니까 1로 보면 되는거임. (-1를 2로 나누면 몫이 -1이고 나머지가 1임. 그냥 검산식 -1 = 2×(-1) + 1를 생각하면됨. 　　　　　　　　　 　↑몫 ↑나머지 나머지는 0보다 크거나 같고 2보다 작은 수, 그러니까 0,1 둘중에 하나만 나와야되니까...) 다시 생각해서, 애초에 모든 더하고 빼는 과정에서 계속 2로 나눈 나머지만 생각하기로 하면 됨. 1+1=0, 0-1=1, 이렇게... 어쨌건 뒤에서 두번째 사람은 (맨 뒷사람이 부른거) - (내가 앞에서 본거)를 부르면 자기 모자 색깔이 되는거임. 뒤에서 세번째 사람도 마찬가지임. (맨 뒷사람이 부른거) - (그 앞사람이 부른거) - (내가 앞에서 본거)를 부르면 됨. 그러니까 결국 맨 뒷사람이 전체 다 더한 정보를 주고, 그 앞사람이 부른걸 차례차례 빼가면서 내 바로 뒷사람이 본거에서 내가 본거의 차이를 구해내기만 하면 됨. 이정도 이해됐으면 이제 슬슬 색깔 3개짜리를 해보겠음. 색깔 3개 빨노초가 있으면, 각각 숫자 0,1,2를 부여하고 위에서 했던것처럼 더하기 빼기 하면 됨. 단 여기서는 3으로 나눈 나머지를 생각함 예를들어 2+2=1로 생각하자는 이야기임. 이렇게 하면 모든 자연수 n에 대해 n개의 색깔 모자가 씌워져 있어도 죄수들은 간단하게 자기 색깔을 '풀어낼 수'가 있음. 쉽게 n으로 나눈 나머지를 생각하면 되지만, 사실 0,1,2,...,n-1 끼리 돌고 돌게 더하기 빼기 법칙만 잘 세워주면 어떻게든 상관없음. 이제 색깔을 더 키워볼꺼임. 무한히 많은 색깔. 자연수만큼 많은 색깔이나 실수만큼 많은 색깔의 경우는 어떨지? 그런데 위의 내용을 제대로 이해했다면 이제와봤자 별다를게 없다는게 느껴질거임. 우리는 무한히 많아봤자 그 안에서 덧셈뺄셈만 잘 할수 있으면 됨. 그런데 수학자들이 증명해낸것 중에, 공집합이 아닌 임의의 집합에 대해 그 안에 더하기 빼기 연산을 잘 줄 수 있다는 정리(자세한 내용은 지루할까봐 생략하도록 하게씀)가 있음. 따라서 색깔이 실수만큼이든 그보다 훨씬 더 많든 간에 죄수들은 더하기 빼기를 통해 맨 뒷사람 빼고 다 맞출 수 있음. (단, 색깔이 무한히 많으면 맨 뒷사람은 찍어도 확률상 절대 못맞추므로 100%로 다시 깜빵행임...ㅠㅠ) 사실 원래 이 문제를 언급한건 다음과 같은 문제 때문이었음. ① 자연수 만큼 무한히 많은 죄수들이 한줄로 서있는데, 앞쪽을 보고있어서 자신의 앞에 서있는 모두의 모자를 볼 수 있도록 되어있음 ② 그 후 그 무한히 많은 죄수들에게 검은색 또는 흰색의 모자를 씌우고, 교도관은 맨 뒷 죄수부터 자신의 모자가 무슨 색인지를 물음.. (그러니까 맨 뒷 죄수가 있고, 그 죄수를 1번 죄수라 하면 그 앞으로 2번 죄수, 3번 죄수, ... 해서 자연수 만큼 무한히 많은거임.) ③ 이 때, 다른 죄수들은 앞의 죄수들이 한 말들을 들을 수 없다. ④ 그래서 맞추면 풀어주고, 틀리면 안풀어줌 ⑤ 죄수들은 어떤 전략을 사전에 세울 수 있다. 아니, 앞사람 말을 못들으면 전략 짜봤자 뭔소용?? 그 이전에, 도대체 어떤 전략을 짜란소리? 아무리 생각해도 그냥 찍는것 이상은 아닐 듯 한데, 어쨌든 석방 되는사람도 무한히 많고 사형당하는 사람도 무한히 많을듯 함... 이것이 우리의 직관임. 그런데 일전에 소개했던 선택공리를 통해 희안하게 우리는 성공적인 전략을 짤 수 있음. 결론부터 말해 이제부터 생각해보는 전략은 유한명 빼고 다 탈출 시키는걸 목적으로 함. 우선, 예를 들어, 우선 우리는 다음과 같은 모자 '배열'을 생각할 수 있음. 　A = (흰, 검, 검, 흰, 검, 검, 흰, 검, 검, 검, 검, 검, 흰, 흰, ... ) 　　　 ↑맨 뒷자리 이것은 수많은 모자 배열 중 하나임. 그러면 이제 모~~~든 모자 배열이라는 것을 생각해 보겠음. 이것들을 한데 모아놓고, 다음과 같은 rule에 의해 '분류'해보겠음 : 처음 유한개 타이밍 이후 전부 모자배열이 일치하는 것들끼리 한 '묶음'으로 둔다. 예를들어 다음과 같은 모자 배열 B는 A와 같은 분류에 들어감. 　B = (검, 검, 흰, 검, 흰, 검, 흰, 검, 검, 검, 검, 검, 흰, 흰, ... ) 　　　　　　　　　　　　　↑여기 이후로 전~부 A와 똑같음. 이런 법칙으로 전부 분류를 시켜놓고, 선택공리를 이용하여 그 수많은 분류들에서 각각 대표 모자열 하나씩만 뽑겠음. 그러니까 저번 글의 표현을 빌리자면, '분류'란 '학급'이고, '대표'란 '반장'이 되는거임. 그렇게 전부 뽑아서 모아놓고, 그 모아놓은 것을 죄수들이 기억하게 하는거임. 준비가 마무리 되었으니 이제 실전에 들어가보기로 하겠음. 각 죄수들은 자기 앞에 있는 무한개의 모자들을 보고 ⓐ자신이 속한 모자배열이 어떤 분류에 들어있는지 알아챈 후, ⓑ앞서 기억했던 모자 배열 중 이 분류에 해당하는 배열대로 찍음. 그러니까 모든 죄수들이 전부 같은 모자 배열을 부르게 되는거임. 그런데 실제 배열과 죄수들이 부르는 배열이 어느 유한개 타이밍 이후 전부 같을것이기 때문에 결국 유한개 타이밍 이후 전부 풀려나게 되어 프리즌 뷁이 완성 되는거임! How amazing!! 적당히 이해가 되셨다면 결과를 약간 음미해보도록 하겠음. 일단 이 난감한 문제를 두고 모자 색의 개수에 관해 말하자면, 풀이가 모자 색이 X나 많아도 상관 없다는걸 알수 있을거임. 그러니까 모자가 검흰이건 빨노초건 실수만큼 많건 간에 유한명 제외 모든 죄수는 석방됨. 이게 얼마나 황당한 얘기인지 들어보셈. 색깔이 2개인 경우, 무식한 교도관이 죄수들 모자 색깔 말하는거 보면서, '얘네들 어차피 단순히 찍는 수 밖에 없을텐데, 50%확률로 어느정도는 석방 되겠지...' 라고 생각할 거임. 물론 점점 이 완벽한 전략에 의해 나아갈수록 100%에 가까운 확률로 석방될 테지만;; 아~무리 계속 석방되더라도 결국 큰수의 법칙(!)에 의해 무한한 녀석들을 사형시키리라는 일말의 희망은 놓지 않을 수 있을 거임.(그러니까, 주사위를 굴려서 1이 100억번 연속으로 나와도 우린 주사위가 완벽하다는 가정 아래 언젠가 2가 나올것이라는 희망을 버리지 않을 수 있음. 수학적으로...) 그런데 만약 색깔이 실수만큼 많다면, 죄수 각각은 자신의 모자 색깔을 맞출 확률이 직관적으로 0임. 고로 교도관은 죄수 전원이 탈출하지 못할것이라고 확신할거임. 그런데 위의 전략에 의해 모자 색깔을 맞추는 녀석이 언젠가 나올 것이고, 교도관은 헑퀴! 게다가 어느 타이밍 이후로 줄줄이 사탕으로 죄수가 석방되는걸 보고 가히 뒤집어질만한 일 아니겠음?!???!? 실제로는 무한히 많은 사람들도 없고, 무한히 많은 기억용량을 가진 사람도 없으므로 위와 같은 일은 일어나지 않겠으나 어쨌든 직관에 위배된다는 사실에는 변함이 없는듯함 ㅇㅇ 선택공리의 신비... 자연수 집합 , 공집합이 아닌 임의의 집합 에 대해, 다음과 같은 성질을 만족하는 함수 가 존재한다 : 임의의 에 대해, 유한개를 제외한 모든 에 대하여 이다. ================================================= 읽어주셔서 감사합니다(__) 수학글로 베오베 가는 그날을 향해!!ㅋㅋ