문제적 남자에서 3시간 10분 동안 풀었던 역대 최장 답풀이 문제 (흰색, 검은색 죄수 모자 맞추기)

코드 비밀의 방에서 신재평과 라인을 형성했던 이용진이 게스트로 나왔던 문제적 남자 방송분, 논리수학 문제가 중간에 출제 되었는데 100명의 죄수들 모자 색깔을 알아 맞추는 문제였다. 이 문제는 좋은 문제로 평가 받아서 글로벌 회사인 "구글"의 입사 문제로도 출제되었고 논리수학적인 문제인 만큼 답을 안다고 해도 설명을 얼마나 논리적으로 하느냐도 중요한 문제라 보기 보다는 꽤 어렵다. 

문제적 남자 방송 이후 역대 최장시간 동안 이 단 하나의 문제를 풀지 못해 많은 시간을 소비했는데 자그마치 3시간 10분 가량을 이 한 문제 푸는데 소요 했으며 그 과정에서 식사와 간식, 음료수 등 여러차례 브레이크 타임을 가졌을 정도로 푸는 사람이나 보는 시청자나 질리기 만든 문제다. 기존에 문제 푸는데 오랜 시간이 걸렸던 최장 풀이 문제 기록을 모두 한번에 갈아치운 문제다. (문제 하나만을 가지고 3시간 푼다는 게 보통의 인내심이 아니다)

주어진 문제는 다음과 같다.

교도관이 100명의 죄수를 키 순서대로 세운 뒤 흰색, 검은색 모자를 무작위로 씌웠다. 

그리고 가장 키가 큰 맨 뒷사람부터 한명씩 자신의 모자 색을 맞히면 감형해주겠다고 말했다. 

최대한 많은 죄수가 감형 받는 방법은 무엇인지 알아내 야 한다. 

단 모자를 쓰기 전에는 다 같이 토의를 할 수는 있지만 모자를 쓰고 줄을 선 이후에는 흰색, 검은색 이라는 말만 할 수 있다. 그리고 줄을 선 이후에는 뒷사람을 본다는 식으로 움직일 수 없다. 줄 서면 모자색만 말해야 한다.

최대한 많은 죄수를 감형 시켜야 하는 문제

남이 내 모자 색을 이야기 해주면 나는 모자색을 알기 때문에 색을 맞춰 감형이 되지만 그 사람은 발언권이 사라지게 되므로 감형을 받지 못하게 된다. 말을 할 수 있는 기회는 단 한번 뿐이다.

모두 각자 자기 모자 색을 맞춰야 하는데 다른 사람 모자색을 알려주지 못한다면..뇌블릴 말처럼 내가 내 모자 색을 알 방법이 없다. 거울이 있지 않는 한...문제를 이해해도 답을 유추하기 정말 어려운 문제

이용진의 말처럼 50명은 감형이 가능하다. 짝꿍을 지어 한 사람이 상대방 모자를 알려주고 짝은 그 모자색을 말하면 절반은 감형이 가능하다. 문제는 최대한 감형 받을 수 있는 사람이 50명 보다 충분히 많다는 것이다

양세찬의 잔머리 풀이..100번째 가장 큰 사람이 99명 모자를 다 보고 난 이후 자기 모자색을 말하는 것처럼 하면서 흰...아니아니..검...아아..흰...아닌가...검...흰....검이 맞나..이런식으로 말꼬리를 잡으며 횡설수설. 그걸로 앞 사람들에게 모자 색을 알려준다는 답...듣고 보니 일리는 있다. ㅋㅋㅋㅋ 99명은 확실히 감형, 자신은 흰색과 검은색 50% 확률이니 99.5명을 살리는 방법이 될 수도 있다.

풀이에 정체가 오자 직접 행동으로 문제 풀이에 도전도 해본다.

시간 과다 소요로 1차 당 투입

참고로 주어진 문제에서 키 순서대로 줄을 선다라고 나온다. 맨 뒷사람의 가장 키가 큰 사람은 맨 앞사람의 모자색까지 전부 볼 수 있다는 전제조건이 문제 속에 들어간다. (키 순서대로 줄을 선 이유다)

어떤 방식이든 확실한 건 하나다. 맨 마지막 100번째 죄수는 누구도 모자색을 봐 줄 수 없기 때문에 절대 알고 맞출 수 없다. 결국 다른 사람들에게 어떤 힌트를 주는 역활만 해야 한다는 말이 되고 100번째 죄수는 희생을 감수해야 한다는 말이 된다. 최대 99명까지 살릴 수 있다고 볼 수 있다. 그 힌트를 어떻게 주어야 하느냐가 핵심이다.

아무것도 안하고 오로지 이 한 문제 때문에 2시간이 지났다. 역대급 고난도 문제 출현!

지금까지 나온 풀이 방법으로 거론 된 것이 박경의 과반수론, 양세찬과 뇌블리의 홀짝론, 사람들을 단위로 묶어서 하자는 이용진의 묶음론, 타일러의 거짓말론, 그리고 MC무의 대학살론(?) 등이 현재까지 진행 상황이다.

역대 최장, 답을 못 찾아서 3시간 동안 죄수 모자 색 맞추기 문제만 풀고 있다. 지금까지 정답을 바로 알지 못해 문제 푸는데 걸린 역대 최장 기록은 58분 33초 (세릴 문제), 옥스퍼드 재학생이 출연했던 옥스퍼드 문제가 1시간 18분 41초, 퇴근 시간을 걸고 풀다가 결국 시청자 문제로까지 갔던 최장 기록 문제가 1시간 53분 08초, 이후 인터넷 검색과 엄마 찬스, 심지어 SNS로 팬들에게 답을 묻기도 했던 문제(지구 문제)가 있었는데 이번에 최장시간 역대 기록을 모두 깬 초특급 문제가 3시간을 넘겼다.

어느정도 정리가 된 상태, 아래부터는 정답 풀이다. 결국 앞 사람의 모자를 볼 수 있는 건 뒷사람인데 모자의 색을 맞춰 말을 하려면 뒷 사람의 말이 중요한 뽀인트가 된다. 뒷 사람이 무얼 보고 자신의 모자 색을 맞출 수 있다면 반복적으로 99번부터 1번까지는 모자 색을 맞출 수 있다.

100번째 죄수가 99명의 모자색을 보면 짝수와 홀수로 나눌 수는 있게 된다. 어떤 수이든 짝수와 홀수는 존재하기 마련, 예를 들어 10명 중 3명은 흰색이고 7명은 검은색이라고 하자. 마지막 10번 죄수는 9명의 모자 색을 볼 수 있다. 자신의 모자 색은 볼 수 없기 때문에 검음색은 6명이 보이게 된다. 흰색은 홀수(3), 검은색은 짝수(6)다. 흰색이 5명이고 검은색도 5명이라고 해도 똑같다. 마지막 10번은 모자 색을 볼 수 없으니 눈에 보이는 건 흰색 5명과 검은색 4명(1명은 10번), 또는 흰색 4명(1명은 10번)과 검은색 5명이다. 짝수와 홀수로 색이 나뉘게 된다는 건 확실해졌다.

여기서 10번은 뒷 사람이 없기 때문에 아무 색이나 말해야 한다. 확률은 50%, 감형을 받거나 감형을 받지 못하거나다. 흰색 4명, 검은색 6명이라고 가정하고 계산해 보면 10번은 어떤 색이든 일단 말해야 하는데 앞에 흰색이 4명 보이고 검은색이 5명 보이게 된다. (10번 포함 흰색 4명, 검은색 6명 또는 흰색 5명, 검은색 5명이 될 수 있는 상황)

10번이 어떤 이유로든 상관없이 일단 검은색이라고 말하면 9번 사람은 검은색이 홀수(흰색은 짝수를 의미)다라는 것을 미리 토의해서 기준으로 정했기 때문에 9번은 검은색이 홀수라는 걸 알고 있고 앞에 8명의 모자색 중 검은색이 홀수로 되어 있어야 한다. 9번이 앞을 봤는데 검은색의 수를 보니 홀수가 그대로 유지되면 자신은 흰색이 되는 것이고 홀수가 깨졌다면 검은색이라는 걸 알 수 있게 된다. 10번이 어떤 색을 말해도 결과는 같다.

10번부터 1번 순서로 검/검/검/흰/흰/검/흰/검/흰/검 순번대로 줄을 섰다고 하자. 10번은 검은 색 모자를 썼지만 모자 색을 모른다. 하지만 앞에 검/검/흰/흰/검/흰/검/흰/검은 보인다. 검5, 흰4개다. 검은색은 짝수를 뜻하고 흰색은 홀수를 뜻한다고 미리 기준을 정했기 때문에 검은 홀수, 흰은 짝수가 된다.

10번이 아무 색을 말했다. 검은색이라고 하자. 9번은 10번 뒷사람이 검은색이라고 했기 때문에 9번을 포함해 1번 부터 9번까지 검은색이 홀수이어야 한다는 걸 알게 된다. 검정색을 세어보니 홀수였기 때문이다. 9번이 앞을 세보면 검정색은 검/흰/흰/검/흰/검/흰/검이 나온다. 검정색이 4개, 흰색이 4개다. 어라? 검은색은 홀수라고 했는데 앞에는 검정색이 짝수네!! 아 내가 검정색이구나! 바로 알게된다. (9번을 포함해야 홀수가 되기 때문)

이런식으로 뒷사람이 불러주는 색을 듣고 홀짝을 정하면 앞 사람은 뒷 사람 색으로 연상이 가능해진다. 9번이 검정색!이다 말하고 (감형 성공) 8번으로 넘어가면 8번은 또 검정색? 이라는 걸 들었으니 앞에 검은색이 홀수여야 한다. 8번 앞에는 흰/흰/검/흰/검/흰/검이 서 있고 검3, 흰4명이 있다. 여기서부터 주의해야 한다. 앞에 남아있는 사람은 검3 홀, 흰4 짝이 그대로 나왔기 때문에 홀짝 만으로는 8번이 어느 색인지 헷갈릴 수 있다. 하지만 검은색은 줄어든 반면에 흰색은 여전히 그대로라는 건 안다. 

결국 홀수는 검정, 짝수는 흰색인데 짝수(흰색)는 그대로이니 난 홀수색인 검정이 된다. 이런식으로 홀과 짝이 겹치는 순간 홀짝이 바뀐다. 7번은 자기 앞에 흰/검/흰/검/흰/검 흰(짝)3명, 검(홀)3명이 남게 되니 흰색이 짝이 되려면 내가 필요하구나 해서 자신이 흰색임을 알게 되는 식이다. (나도 소녀장원 풀이를 듣고 안거라 아마 내가 풀어준 말이 맞을 것이다) 

내가 푼 논리수학 문제 중에서도 확실히 가장 어려웠던 문제, 답을 알고 나서도 내가 완전히 이해하기 까지는 시간이 좀 필요했던 문제다. 구글에서 좋은 문제로 평가할 만 하다. 혼자는 힘들고 문제적 남자처럼 집단지성으로 풀어야 어느정도 가능성이 있는 문제가 아닌가 싶다. 혼자서 이걸 단시간에 푼다면 레알 천재라고 본다.