10장 카드 중 5장을 뒤집어 자신의 번호를 연속으로 맞추는 확률

답이 없어 보이는 것도 고민해 보면 어느정도 답이 나오는 경우가 있다.

1-10까지 숫자가 적힌 카드 10장이 한줄로 책상에 놓여있는 방이 있다.
10장의 카드 순서를 무작위로 섞는다.

1-10번 까지 번호가 적힌 모자를 무작위로 나누어 쓴 10명의 사람이 있다.
이 10명의 사람이 1명씩 방에 들어가서 10장의 카드 중 원하는 5장을 뒤집는다.
만약 그 5장 중에 자신의 모자에 쓴 번호와 같은 카드가 있으면 통과할 수 있다.

카드는 다시 그 같은 자리에 뒤집어 놓고, 다른 문으로 나가면 된다.
아직 참가 하지 않은 사람과는 이야기를 나눌 수 없다.

다음 사람이 방에 들어가서 같은 활동을 반복한다.

1명이라도 실패하면 통과할 수 없고 미션은 실패하게 된다.

----
10명이 모두 통과해야 미션 성공이다.
그렇다면 미션을 성공할 가능성은 얼마나 될까?

만약 일정금액을 내고 시도해서 성공하면 100배의 보상을 해 준다고 하면 도전하겠는가?

---
10명이 다 통과해서 미션을 성공 할 확률은 (1/2)^10 = 1/1024 이다. 즉 동전을 10번 던져서 모두 앞면이 나올 확률과 같다. 약 0.1%의 확률이다. 1000번을 도전하면 1번 정도 성공할 수 있다.

만약 카드 100장이 있고 100명이 들어가서 50장을 뒤집어서 자신의 번호를 맞추는 게임을 한다면 100명이 모두 합격할 확률은 (1/2)^100 = 약 10의30승 분의 1 약 0.0000000000000000000000000001% 정도가 된다. 거의 불가능하다고 보면 된다.

---
하지만 방법이 없는 것은 아니다.
확률을 어느정도 끌어 올릴 수 있다.

아래 해답을 보기 전에 해결책을 스스로 한번 생각해 보기 바란다.

<해답>

방법은 참가한 사람들은 각자 자기 번호와 카드의 순서를 확인하고, 자기 번호와 같은 순서의 카드를 뒤집는다. (예를 들면 내가 4번 모자를 쓰고 있다면 한줄로 놓여 있는 카드중에 4번째 카드를 뒤집는다.) 그리고 거기에 써있는 번호를 확인하고 그 번호 순서의 카드를 뒤집는다. (위 그림에서 4번째 카드에 7이라고 적혀 있으니 7번째 놓여 있는 카드를 뒤집는다.) 이걸 계속해서 반복한다.(7번째 카드에 6이라고 적혀있으니가 6번째 카드를 뒤집고, 6번째카드에 3이라고 적혀 있으니까 3번째 카드를 뒤집는다. 3번째 카드에 4라고 적혀 있으니 자신의 번호를 찾았다.) 그럼 몇개의 순환되는 수가 부분군(7-6-3-4-7)을 이루게 된다. 여기에서 반복되는 마지막 7을 제외하면 4개의 카드가 부분군이 된다.

부분군이 5개 카드 이내에서 만나고 거기에 내 번호가 있으면 10명이 모두 같은 방법으로 통과 할 수 있다.
부분군이 (1-2-3-4-5-6-1) 6개 이상이 되면 5번 만에 자신의 번호를 찾아낼 수 없으므로 미션을 성공할 수 없다.

어떤 부분군의 길이가 k가 될 확률은 1/k 이다. (수학적으로 따져 보면 된다)
실패할 확률은 부분군이 6보다 커질때다. 따라서 실패할 확률은 1/6+1/7+1/8+1/9+1/10 = 약 0.645 즉 64.5% 정도 된다. 그럼 성공할 확률은 35.5% 정도 된다. 아까 0.001% 보다 훨씬 높은 확률로 성공할 수 있다.

만약 기회를 10번을 주고 그 중에 1번만이라도 10명이 모두 통과해서 미션성공을 하면 보상을 해 준다면
한번 도전에 미션을 성공할 확률이 약 1/3 이고 실패할 확률이 2/3 가 되므로

10번 연속으로 실패할 확률은 (2/3)^10 =0.017 약 1.7%정도 된다.

그렇다면 10번을 반복했을 때 1번이라도 성공할 확률은 98%가 된다.
----
학생들과 시합을 해 봐야 겠다.
10명의 학생이 10번을 시도해서 1번이라도 미션을 성공하면 선생님이 이기는 걸로...
단 1번 할때 마다 미션을 실패하면, 매번 카드의 배열은 무작위로 바꿔야 한다.

만약 카드의 배열을 바꾸지 않고 그대로 둔다면, 다시 시도하는 학생들이 마음속으로 맨 첫번째 카드를 10번째 카드자리로 옮겼다고 생각하고 게임을 하면 된다. 그래도 실패하면 그 다음 3번째 도전할 때는 1,2번째 카드를 9,10번째 자리로 옮겼다고 생각하면 된다.

이렇게 10번을 도전하면 그 중 1번이라도 미션을 성공(10명이 카드를 5장 뒤집어서 모두 자신의 번호를 맞춤) 할 수 있는 확률은 98%가 되므로 거의 대부분 이길 수 있다고 보면 된다.

----

어떻게 생각하면 승산이 없는 싸움 같지만, 생각을 조금만 바꾸면 거의 이길 수 있는 게임으로 바꿀 수 있다.