[100명의 죄수 문제] 파이썬으로 확률 알아보기

얼마전 재미있는 영상을 보았습니다. 

 

내용은 이러합니다.

 

100의 죄수가 있는 교도소의 교도소장이 1~100까지의 상자 속에 무작위로 자신의 번호가 적힌 쪽지가 있다. 죄수들은 50번의 기회 중 자신의 번호가 적힌 쪽지를 찾으면 탈출할 수 있다. 만약 단 한명이라도 50번 안에 쪽지를 찾지 못하면 전원 사형한다. 단, 죄수들을 게임이 시작 전 작전회의를 할 수 있다. 또한 한 명이 들어가고 다른 한 명이 들어올 때 교도관들이 처음 상태로 말끔히 되돌려서 이전 죄수가 표식을 남겼다해도 알 수가 없다. 이때 100명의 죄수들이 통과할 가장 높은 확률은?

 

해당 유튜브에서의 해법은 이러합니다. 모든 사람이 자신의 번호가 적힌 상자를 열어본다. 그 상자에 있는 쪽지 번호가 자신의 번호이면 통과이고 아니면 그 번호가 적힌 상자로 이동하여 상자를 열어본다. 이 과정을 계속해서 반복한다. 

 

일반적으로 100개 중 50개를 무작위로 선택하면 정답을 맞출 확률은 0.5입니다.

그러나 사람이 100명이니까 0.5의 100제곱을 해야합니다.

그냥 죽으라는 확률이죠 해법대로 하면 약 30%까지 확률이 올라온다고 합니다.

 

해법대로 쪽지를 찾아가다 보면 어떠한 사이클이 만들어진다고 합니다. 예를 들어 10개의 상자가 있을 때 5번의 기회가 있다고 하고, 각 상자 속 쪽지가 다음과 같다고 가정해보겠습니다.

상자 번호  ->  쪽지 번호

1 -> 3

2 -> 6
3 -> 4

4 -> 1

5 -> 2

6 -> 7

7 -> 10

8 -> 9

9 -> 8

10 - > 5

 

이런 반복 구조들이 등장하게 됩니다. 

1번 -> 3번 -> 4번 -> 1번

2번 -> 6번 -> 7번 -> 10번 -> 5번 -> 2번

8번 -> 9번 -> 8번

 

만약 4번 죄수라면 4번 상자를 열어봅니다.

4번 상자의 쪽지는 1번 그럼 1번 상자로 이동하여 열어봅니다.

1번은 상자의 쪽지는 3번 그럼 3번 상자로 이동하여 열어봅니다.

3번 상자의 쪽지는 4번, 4번 죄수이니까 4번이 적힌 쪽지를 찾았습니다.

 

처음에 자신의 번호가 적힌 상자를 열고 쪽지의 번호 대로 상자로 계속 이동하다보면 무조건 찾는다는 말입니다.

그러나 이것도 50번 안에 찾아야합니다. 만약 반복구조가 51이 되면 죄수들은 탈출에 실패합니다. 

 

여기서 의문이 들수 있는데 무조건 루프 안에 자신의 번호가 있는지 어떻게 보장하지? 라는 의문인데 해법 대로 해보면 무조건입니다. 있긴 있는데 만약 51개가 넘어가면 전원 사형이지만 말이죠

 

정리하자면 자신의 번호가 적힌 상자로 가서 쪽지에 적힌 상자로 가서 열어보고 이 과정을 50번의 기회안에 찾아낸다면 모든 죄수가 완벽하게 탈출이 가능하고 50번안에 탈출하지 못하면 죄수들은 완벽하게 실패합니다.

 

때문에 루프가 50개가 넘는지 안넘는지 검사만 하면 탈출할 수 있는지 아닌지 확인할 수 있습니다.

 

파이썬으로 루프 구조를 무작위로 만들고 실제 확률이 어떻게 나오는지 확인해보겠습니다.

import random as r

total = 0  # 총 시행 횟수
lose = 0  # 사형 당할 횟수

while True:
    amount = 0
    prevent = []  # 중복을 막기 위해서

    total += 1
    while amount != 100:  # 루프 구조 만드는 반복문 시작
        n = r.randint(1, 100-amount)  # 이걸 왜 빼냐면 루프의 총 개수를 말하는 것임
        node = []  # 루프 구조
        while True:
            m = r.randint(1, 100)  # 1부터 100까지 무작위
            if m in prevent:  # 만약 prevent리스트에 들어있으면
                continue  # 반복 위로 올라가서 다시 랜덤한 숫자 고르기
            prevent.append(m)  # 그냥 통과했다면 중복돼지 않은 숫자라는 말
            node.append(m)  # 루프에 추가
            if len(node) == n:  # 만약에 루프가 루프의 총 개수와 같다면?
                break  # 나가라
        if len(node) >= 51:  # 만약에 루프가 51개 이상이면? 
            lose += 1  # 무조건 지게 되므로 다른 루프는 볼 이유가 없다 새로운 게임을 위해
            break  # 나가야 한다.
        amount += n  # 여기로 왔다는 것은 루프가 51보다 작다는 것 이제 위로 올라가서 다른 루프 만들기

    print(100-(lose / total * 100), "총:" + str(total) + " 이김:" + str(total-lose))

이 프로그램을 시작하면 31%보다 약간 넘게 됩니다. 

 

0.5의 100제곱 보다 훠어어어얼씬 높은 확률로 통과하게 됩니다. 이 정도면 시도해 볼만 하지 않나요?