100명의 죄수와 상자 문제 계산기

죄수 100명에게 번호를 매기고 상자 100개에 번호표를 무작위로 하나씩 넣은 뒤, 죄수가 한 명씩 들어가 상자를 50개까지 열어 자기 번호표를 찾는 문제입니다. 서로 정보를 주고받을 수 없고 전원이 찾아야 모두 풀려납니다. 아무 상자나 열면 성공 확률이 2⁻¹⁰⁰으로 사실상 0인데, 전략 하나로 31%까지 올라갑니다.

자기 번호와 같은 번호의 상자를 먼저 열고, 그 안에 든 번호표의 상자를 다음에 엽니다. 이것을 열 수 있는 횟수까지 되풀이합니다. 번호표 배치는 순열이므로 이 전략은 자기 번호가 속한 사이클을 따라가는 것이고, 사이클은 반드시 자기 번호로 돌아오므로 그 길이가 열 수 있는 수 이하이면 반드시 찾습니다.

«전원 성공»이 «순열의 가장 긴 사이클이 짧다»는 사건 하나와 같아지기 때문입니다. 각자 따로 운을 시험할 때는 100번의 독립 시행이 모두 성공해야 하지만, 사이클 전략에서는 배치 하나가 좋은 배치이기만 하면 전원이 함께 성공합니다. 사람들의 운을 몰아서 한곳에 걸어 두는 셈입니다.

거의 떨어지지 않습니다. 절반씩 열 때 인원을 아무리 늘려도 1 − ln 2 ≈ 30.7% 아래로 내려가지 않습니다. 100명이면 31.18%, 1000명이면 30.74%로 극한에 가까워질 뿐입니다. 이 문제가 유명한 진짜 이유가 여기 있습니다.

확률이 빠르게 떨어지고, 흔히 쓰는 닫힌 식 1 − (H(N) − H(k))도 더는 성립하지 않습니다. 그 식은 열 수 있는 수가 절반 이상일 때 «긴 사이클이 많아야 하나뿐»이라는 사실에 기대기 때문입니다. 이 도구는 언제나 점화식으로 정확히 구하고, 닫힌 식은 쓸 수 있을 때만 나란히 놓아 대조합니다.

전송되지 않습니다. 계산은 전부 브라우저 안에서 이뤄지고, 입력값은 이 브라우저의 localStorage에만 남습니다.