https://youtu.be/PE4vLbyOgw0?si=H5YvcFUmX8Xx2SI1

출처는 위와 같음 영상을 못 보는 블부이들에게 가벼운 요약을 해줌

100명의 죄수가 있어. 이 죄수들은 모두 1~100까지의 넘버링을 가지고 있지

그리고 어떤 방에 100개의 상자가 있는데, 이 상자에는 각각 1~100까지의 숫자 카드가 들어있어

죄수들은 한명씩 방에 들어가서 100개의 상자 중, 50개를 열어볼 수 있는데, 자신의 넘버링이 적힌 상자를 오픈했다면 이 미션은 성공이야

100명의 죄수가 모두 성공한다면 모두가 생존하고, 단 한명이라도 실패하면 모두가 사형이야

단, 죄수들은 전략을 짤 수 있는데 어떤 전략을 짜면 가장 생존 확률을 높일 수 있을까?

박스에도 넘버링이 있을 테니, 없으면 만들면 되고 자신의 넘버링이 적힌 상자를 연 뒤, 번호를 확인 후

해당 번호의 상자로 가서 그 상자를 열고, 이걸 반복하는 것이 가장 확률을 높이는 방법이라고 해

정공법으로 찾는다면 (1/2)^100 이라는 말도안되는 성공확률이지만

이 방법이라면 모든 죄수가 성공할 확률이 33%까지 올라간다고 해

구체적인 방식을 예로 들자면

내 번호가 1번이라면 1번상자를 열고 상자를 열었는데 30번이 있다면 30번 박스를 열고, 30번에서 40번 번호가 나왔다면 40번 번호를 열고 그러다가 1번을 찾는다면 거기서 끝

이게 왜 가능하냐면 100개의 박스에 100개의 번호가 들어있으니

이렇게 1->4->3->9->10...

이러한 방식의 루프를 만들게 되는데, 이 루프는 모두 닫힌 루프가 됨

왜냐하면 항상 박스에 있는 번호는 어떠한 다른 박스를 가리키기 때문에, 루프가 성립하지 않고 중간에 끊기는 경우는 있을 수 없음

1->4->9->10...->30->1

이렇게 루프를 도는데, 30번 박스가 1번 박스를 가리켜서 루프를 닫을 때 비로소 자신의 번호를 찾게 되겠지

그럼 이 전략을 사용했을 때, 죄수가 50번 내에 번호를 찾지 못하는 경우는 뭐가 있을까?

어떠한 루프가 51개 이상의 루프로 이루어졌을 때야

51개의 노드로 구성된 루프에 속한 죄수들은 모두 딱 하나의 상자를 남기고서 루프를 닫지 못하고, 하나만 더 열면 되는데... 자신의 상자를 찾을 수 없겠지

100개의 상자로 닫힌 루프를 만들 때 길이가 51이상인 루프가 생기지 않을 확률. 그말인 즉슨 100개의 상자를 배열해서 루프를 만드는 모든 경우에서 51이상인 루프가 생기는 경우를 빼

그렇다면 그 수치가 모든 루프가 길이 50이하로 구성될 확률과 같지

이 밑으로는 적분이니 넘어가고, 계산을 마쳤을 때 무려 30%의 확률이 나온다고 해

(1/2)^100의 수치가 0.3까지 올라오는 전략이라니 너무 신기해서 퍼왔음

3줄요약

1. 죄수 100명이 각자 번호가 있고, 100개의 상자 중 절반을 열어서 자신의 상자를 찾으면 성공. 다만 1명이라도 실패하면 모두 처형

2. 정공법으로 찾는다면 각자 찾아낼 확률은 1/2이고, 100명이니 1/2를 100번 곱한 확률과 같음. 그냥 불가능하다는 이야기

3. 루프 전략을 사용하면 모두가 성공할 확률이 30%가 됨. 루프전략이란
자신의 넘버링이 적힌 상자를 연 뒤, 그 안에 적힌 번호를 확인 후 해당 번호의 상자로 가서 그 상자를 열고 반복.