The Drunk Passenger on Plane Problem
다음은 The Drunk Passenger on Plane Problem에 대해 설명하고, 정답과 왜 그러한 정답이 도출되는 지에 대해 분석한 영상이다.
흥미로운 문제라 생각되어서, 이 문제에 대해 대해 생각한 기록을 남기고자 한다.
The Drunk Passenger on Plane Problem
위 영상에서도 설명하지만, 구태여 설명하자면 다음과 같다.
- 비행기에 1부터 100까지의 좌석이 준비되어있다.
- 각 좌석에는 번호가 매겨져 있어, 승객이 이를 인식할 수 있다.
- 이 100개의 좌석에 100명의 승객이 각자 자신에게 배정된 좌석을 찾아간다.
- 승객에게 배정된 좌석의 번호와, 승객이 입장하는 순서는 같다.
- 첫번째로 입장하는 승객은 1번 자리에 배정되었고, 그 다음에 입장하는 승객은 2번 자리에, …
- 첫번째로 입장하는 승객은 술에 취했기 때문에, 무작위 자리에 앉는다.
- 나머지 모든 승객은 다음과 같은 조건에 따라 자리에 앉는다.
- 자신의 좌석이 비어있다면, 그 좌석에 앉는다.
- 자신의 좌석에 이미 누군가 앉아있다면, 다른 무작위 좌석에 앉는다.
100번째 승객이 자신의 좌석인 100번 좌석에 앉을 확률은?
내 첫번째 생각
사실 접근이라고 부르기도 뭐하다. 단순히 설명만 듣고나선 냅다 100!을 떠올렸지만, 이 숫자가 어떻게든 활용될려면, 좀 더 디테일을 살려야 할 것임을 곧바로 직감했다.
두번째 생각
결국 궁금함을 찾지 못하고 설명까지 모두 듣고 말았지만, 결국 이해해서 내 것으로 만들면 되는 것 아닌가. 이제부터 다시 처음부터 하나하나 내가 직접 젠가를 쌓아올리고자 한다. 쌓아올리면서 한번도 무너지지 않은 탑은 언젠가 무너지기 마련이기에.
우선 경우의 수를 정리해보자.
모든 경우의 수를 정리하는 것은 어림잡아도 사람이 계산할 수 있는 정도가 아니겠지만, 그래도 최대한 구분을 지어보자.
- 첫번째 승객이 자기 좌석에 앉는 경우
- 첫번째 승객이 다른 좌석에 앉는 경우
가장 먼저 일어날 사건은 이렇게 구분 될 것이다. 그리고 만약에 전자라면, 그 누구도 무작위로 앉지 않을 것이니, 어떠한 무작위성도 시나리오에 개입되지 않고 100번째 승객은 자신의 좌석에 앉을 수 있을 것이다.
문제는 후자인데, 여기서 다양한 시나리오가 갈린다.
첫번째 승객이 다른 좌석에 앉음으로써, 높은 확률로 자리를 빼앗긴 승객이 다른 승객의 좌석을 빼앗을 것이다. 그러면, 이 승객에 의해서 자리를 빼앗긴 승객도 높은 확률로 다른 승객의 자리를 빼앗을 것이고, 이러한 연쇄가 여러번 반복될 수 있다. 하지만 무한정 반복되지는 않을 것이다.
그러면 언제 멈출까?
- 마지막 100번째 승객이 앉을 때
우선, 마지막 승객이 앉을 때까지 연쇄가 이어진다면, 기내는 혼돈의 현장일 것이다. 서로 뺏고 뺏기면서 어떻게든 99명이 앉아 마지막 100번째 승객이 앉을 자리는 한자리밖에 남아있지 않을 것이다. 그리고 이 자리가 어디냐가 중요하다. 원래 자기 자리라면 좋겠지만, 이 연쇄가 마지막 승객에게까지 와서 100번째 자리가 빼았겼다면, 100번째 승객은 1번 좌석에 앉을 수 밖에 없다.
- 중간에 누군가가 1번 좌석에 앉을 때
첫번째 승객이 무조건 자기 좌석이 아닌 다른 좌석에 앉는 경우로 분기했기 때문에, 여기서 1번 좌석은 무조건 비어있는 순간이 있다. 만약에 1번 승객에 의해 자리를 빼앗긴 사람이 무작위로 1번 좌석을 골라 앉아 연쇄를 끊는다면, 그 이후의 승객부터는 무작위성이 개입되지 않고 100번째 승객까지 자신에게 배정된 좌석에 앉을 수 있을 것이다. 만약에 1번 승객에 의해 좌석이 빼앗겼고, 빼앗긴 이 좌석의 원래 주인인 승객이 1번 좌석이 아닌 다른 좌석을 빼앗아 앉아도, 결국 이 좌석의 원래 주인인 승객이 다시 1번 좌석에 앉는다면, 그리고 이 승객이 100번 승객이 아니라면, 결국 100번 승객은 100번 좌석에 앉을 수 있을 것이다.
바로 이 부분이 가장 흥미로웠는데, 연쇄가 이어지는 도중을 상상해보자.
좌석을 빼앗긴 승객이 무작위로 앉을 좌석을 정한다고 가정하자. 첫번째 승객이 7번째 승객의 좌석을 빼았았다. 그리고 당신이 7번째 승객이다. 2~6번째 승객들은 무탈하게 자신의 좌석을 잘 찾아 앉았겠지만, 적어도 당신에게는 그렇지 않다. 이제 선택 가능한 경우의 수는 1번 좌석, 그리고 8~100번 좌석이 남았다.
- 1번 좌석은 이 연쇄를 끊는 선택지다. 무조건 100번째 승객은 100번째 좌석에 앉을 것이다.
- 100번 좌석은 100번째 승객이 자신의 좌석에 앉지 못하게하는 선택지다.
- 8~99번 승객은 자신의 좌석을 잘 찾아 앉을 것이고, 100번째 승객은 1번 좌석에 앉아야만 한다.
- 나머지 8~99번 좌석은 이 연쇄를 계속 이어가는 선택지다.
- 결국 이 연쇄를 끊을지, 말지, 100번의 자리를 뺏을지의 결정을 다음 사람에게 떠넘기는 셈이다.
그리고 언제나, 이러한 결정을 내릴 때는 1번 좌석과 100번 좌석을 고를 확률은 각각 동일하다.
결론
그렇기 때문에, 결국 100번 승객이 자신의 좌석인 100번 좌석에 앉을 확률은 반반이기에 50%이다.
결론을 내고 나서…
이미 알아버렸지만 모른척하고 다시 풀기란 쉬운 일이 아니다. 자꾸만 뇌가 요령을 피우려는 것을 견제해가며 문제를 푸는 것은 참으로 어렵다. 그래도 이렇게 하나씩 풀어나가 보려고 한다.
이 글이 내 블로그의 첫 포스팅이다. 전날 밤 어찌저찌 테마를 정하고 첫 포스팅으로 무엇을 작성할지 고민했는데, 아침에 이 문제를 우연히 접했고, 첫 포스팅으로 알맞을 것 같아서 올린다.
문제를 나름대로 이해하고, 분석하여 글로 어딘가에 쓴다는 건 굉장히 수고스러운 일이 아닐 수가 없음을 깨닫는 아침이자 낮이었다. 생각보다 많은 시간을 포스팅에 투자했다. 꾸준히 쓰다보면 좀 더 짧은 시간내에 포스팅 하나는 뚝딱하지 않을까 싶다.
이 글을 완독해주신 당신이라면 분명 무엇인가에 진득히 매달릴 수 있는 인내심을 가진 사람이라고 생각한다. 나 주제에 누굴 평가하겠느냐만.
감사히 여기며, 당신에게 오늘은 빛나고, 내일은 밝을 것이라고 무책임하게 호언장담하고 싶다.