일단 제일 간단한 전략인 무작위 선택을 생각해봅시다. 만약 50개의 박스를 무작위로 고른다면 자신의 지폐를 찾을 확률은 50%입니다.
100명의 사람들에게 모두 동일한 확률이죠.
그렇다면 100명 모두 무작위로 선택해, 모두 다 자신의 지폐를 가질 확률은 각자의 확률인 1/2를 100번 곱하면 되겠죠!
아쉽게도, 이 방법은 .000....0008로 0에 수렴합니다. 그렇게되면 님들의 돈은 제가 갖겠죠!
하지만 무작위로 선택하는것보다 훨씬 좋은 방법이 존재합니다!
너무 좋은 방법이라 심지어 단 둘이서 무작위 선택할때의 확률인 25%보다
100명이서 할 때 더 높은 확률인 31.38%로 승리할 수 있는 방법이죠!
여러분은 아마 박스 그 자체에서 정보를 얻을 수 있다는 사실을 간과했을겁니다.
박스는 항상 똑같은 순서대로 놓여있고, 누가 들어가던 똑같은 박스를 고르면 똑같은 숫자가 적힌 지폐가 들어있죠.
그렇다면 이 정보를 도대체 어떻게 이용한다는것일까요?
방법은 간단합니다. 일단 박스를 차례대로 번호를 매긴다고 합시다. (100명 모두 동일한 방법/순서로 번호를 매깁니다)
그러고는, 당신의 번호에 해당하는 박스를 열어 확인합니다.
아마 님의 박스에는 님의 번호가 적힌 지폐는 들어있지 않을거에요. 대신, 다른 번호가 적힌 지폐가 있겠죠?
그러면 그 지폐에 적힌 번호에 해당하는 박스로 가서, 그 박스를 또 열고, 그것을 반복합니다.
예를 들어 자신의 번호가 79번이라면, 79번째 박스를 열고, 거기서 14번이 나왔다면 14번 박스로가서 또 열고,
14번박스에서는 2번이 나왔다면 2번 박스로 가서 열고.....(반복)
쉽게 말하면, 당신이 연 박스 안의 지폐가 가르키는 숫자의 박스를 계속해서 열어나간다는거죠.
시작은 님 지폐번호구요.
그렇게 한다면 박스들끼리 일종의 고리를 형성하게 될거에요.
무슨 말인지 이해가 잘 되지 않으신다구요?
예를 들어 일단 갯수가 적은 여섯개의 박스만 있다고 생각해봅시다.
그리고 만약 당신 지폐의 번호가 3번이었다면, 처음 3번 박스를 확인합니다.
1번지폐가 있군요! 그러면 1번 박스를 확인합니다.
거기엔 6번지폐가 들어있군요! 이젠 6번으로 갑니다.
4번지폐가 들어있네요! 그럼 4번 박스로 가서 확인해보면...
님의 지폐를 찾았습니다! 3번지폐가 여깄었네요!!
그럼 이런 식으로 고리가 형성되게 될거에요.
3 -> 1 -> 6 -> 4 ->3 ... 이런 4개짜리 긴 고리 하나랑
2 -> 5 -> 2 ... 이런 2개짜리 짧은 고리 하나랑요.
고리의 크기와는 상관없이 고리의 마지막 박스는 항상 님의 지폐가 들어있게 되는거에요!
다시 원래 문제인 100개의 박스로 돌아와서 생각해보죠.
짧은 고리는 그림과 같은 경우죠. 30 -> 82 -> 5 ... 세개로 이루어진 박스요.
그리고 가장 긴 고리는 100개의 박스가 모두 연결되는 경우일 거에요.
또, 항상 하나의 박스는 오직 하나의 고리에만 속하게 됩니다. 왜냐구요?
위 그림에선 31번 박스와 68번 박스가 둘 다 41번 박스만 가르키고 있는데,
41번지폐는 오직 31, 68번 둘중의 하나의 박스에만 들어있으니까요.
마찬가지로, 41번박스는 오직 하나의 번호가 적힌 지폐만 가지고있죠.
그렇기에 이렇게, 한 박스는 오직 하나의 고리안에만 속해있습니다.
만약 이 박스 고리가 50개보다 짧은 갯수의 박스로 이루어져 있다면 당신은 당신의 지폐를 찾을 수 있겠죠!
박스를 무작위로 섞을 경우, 31.18%확률로 가장 긴 고리가 50개이하입니다.
나머지 68.82%의 확률은 50개보다 길구요.
그렇기에 만약 고리가 50개 이하의 박스로 이루어져있다면, 모두의 승리입니다!
누가 어느 지폐를 가지고 있던 최대 50번 안에는 이 "고리" 방법으로 모두 승리할 수 있는거죠!
하지만 만약 50개 이상의 박스로 이루어진 고리라면? 아쉽게도 긴 고리에 속한 모두 다 실패하고 맙니다.
