어느 게시판에 올릴 지 몰라 과학 게시판과 더지니어스 게시판에 둘다 올립니다.
스포일러 있습니다.
진실 탐지기는 더지니어스 룰브레이커의 결승전에서 처음 공개된 게임입니다.
각 한 턴씩 번갈아가며 질문해서 상대의 숫자 4자리 비밀번호를 먼저 맞추는 사람이 이깁니다.
단, 질문을 받았을 때 반드시 거짓으로 대답해야합니다.
진실을 말했을 경우에는 패널티로 자신의 비밀번호에 포함되지 않는 번호가 하나 공개됩니다.
이 게임의 핵심은 총 10000가지인 비밀번호의 경우의 수를 줄여나가는 것입니다.
만약 진실일 확률이 50:50인 질문을 한다고 칩시다. (예: 당신의 패스워드는 짝수입니까?)
그러면 짝수던 홀수던 가능한 패스워드의 가짓수는 50%로 줄어들게 됩니다.
혹은 진실일 확률이 30:70인 질문을 한다면 (예: 당신의 비밀번호는 3000 이상입니까?)
70%의 확률로 경우의 수는 30%가 줄어들고 30%의 확률로 경우의 수가 70% 줄어들 것입니다.
즉, 어떤 질문을 하던 장단점은 존재합니다.
따라서 이 글에서는 필요한 질문 개수의 기댓값을 중점으로 분석해보겠습니다.
가장 정석적인 플레이는 숲들숲들이 말하던 '바이너리'입니다. 바이너리는 경우의 수를 절반씩 줄여나가는 방법을 말합니다.
그러면 경우의 수는 항상 10000→5000→2500→1250→625 ... 로 줄어들게 되고
최악의 경우에는 14번의 질문으로 패스워드를 알아낼 수 있고, 최상의 경우에는 13번의 질문으로 패스워드를 알아낼 수 있네요.
확률을 계산해봤습니다. (자세한 설명은 생략. 직접 해보세요 ㅋㅋ)
13번의 질문으로 알아낼 확률은 64%, 14번의 질문으로 알아낼 확률은 36%입니다.
기댓값은 13.36으로 매우 낮은 편이네요. 말그대로 최상의 방법입니다.
그럼 이상민씨가 사용한 방법은 어떨까요?
이상민씨는 중복된 숫자가 있는지, 4자리 각각의 짝수(0포함), 홀수 여부를 물어본 다음에 각각 자리수를 바이너리 방식으로 추려나갔습니다.
중복된 숫자가 있는지 물어보지 않았다면 기댓값은 13.6입니다.
그러나 이상민씨는 중복된 숫자가 있는지를 물어봤습니다. 결과는 중복된 숫자가 없었죠.
그러면 두가지 경우로 나뉘어집니다. 하나는 짝수, 홀수가 각각 두개씩 존재하는 경우, 다른 경우는 홀수나 짝수가 1개 존재하는 경우입니다.
(홀수 4개 / 짝수 4개는 고려하지 않았습니다.)
만약 홀수 짝수가 각각 2개 존재하는 경우에는 기댓값이 13.8입니다. → 임요환의 비밀번호였죠. 실제로 이상민씨는 14번의 질문만에 맞췄습니다.
그러나 홀수 짝수가 1개 3개씩 존재하는 경우에는 기댓값은 13.47이군요.
또다른 방법도 있습니다. 10000가지의 경우의 수를 2000:8000으로 나눈 다음, (예: 비밀번호는 2000 이상입니까?)
바이너리를 이용하는 방법이죠. 기댓값은 13.6입니다.
임요환의 방법은 난잡해서 분석하기가 힘들었고요 -_-;;
결론: 이 게임은 바이너리가 최강이다.
숲들숲들이 맞았네.
