Airplane Boarding Problem 비행기 타기 문제
오늘은 크게 어렵진 않지만 그래도 생각해볼 가치가 있는 문제를 가져와보았다. 이 문제는 quant라는 곳에서 인터뷰 문제로 나온 적이 있다고 한다.
<문제>
One hundred people are in line to board a plane which has exactly 100 seats. Each passenger has a ticket assigning them to a specific seat, and the passengers board one at a time. The first person to board is drunk, picks a random seat, and sits in it. The remaining passengers board; if they find their assigned seat empty, they sit in it. If they find their seat taken, they pick a random seat to sit in. Everyone boards, and is seated. What is the probability that the final person who boards gets to sit in their assigned seat?
백명의 사람들이 정확히 100좌석이 있는 비행기에 탑승하는 줄을 서고 있다. 각각의 승객은 특정 자리에 앉을 수 있는 티켓이 있고, 승객들은 한 명씩 좌석에 앉는다. 첫 번째로 앉는 사람은 술에 취해 임의의 자리를 선택하고 앉는다. 남아있는 승객들은 만약 자신의 자리가 비었다면 그곳에 앉고, 비어있지 않다면 비어있는 임의의 자리에 앉는다. 이때 마지막 앉는 사람이 자신의 자리에 앉을 확률은 얼마인가?
승객의 수가 100명이나 있어 확률을 그냥 구하긴 어려워 보인다. 먼저 승객이 2명,3명 있을 때의 확률을 구해보자.
1) 승객이 2명일 때
두 번째 사람은 첫 번째 사람이 첫 번째 좌석에 앉으면 자신의 자리에 앉을 수 있다. 따라서 이 경우 확률은 자명하게 0.5이다.
2) 승객이 2명일 때
승객이 3명일 때는 세 번째 사람이 자신의 자리에 앉는 경우는 크게 두가지가 있다. 첫 번째 사람이 첫 번째 자리에 앉았거나, 첫 번째 사람이 두 번째 자리에 앉고, 두 번째 사람이 첫 번째 자리에 앉으면 된다. 확률을 구해보면, 1/3 x 1 + 1/3 x 1/2 = 0.5 여전히 0.5임을 알 수 있다.
그럼 과연 승객의 수와 관계 없이 확률이 항상 0.5일까? 한 번 증명해보자.
먼저 자신의 자리에 앉지 못하는 승객을 '취한 승객' 이라고 정의해보자. 최초의 '취한 승객'은 첫 번째 승객이 될 것이다. 취한 승객은 자기 자리에 앉거나 아니면 다른 승객의 자리에 앉는 선택을 할 수 있다. 만약 자기 자리에 앉는 경우 그 뒤부터는 모두 자기 자리에 앉을 것이고, i 번째 승객의 자리에 앉는 경우는 다음 번에 취한 승객이 i번째 승객이 된다. 뭔가 확률에 대한 점화식을 세울 수 있을 것만 같은 느낌이 든다.
let) P(n) = |승객이 n명일 때 구하는 확률|
P(1) = 1
P(2) = P(3) = 0.5
Pn에 대한 점화식을 세워보자.
1) 첫 번째 승객이 자신의 자리에 앉는 경우
이 경우에는 반드시 마지막 승객이 자신의 자리에 앉으므로 첫 번째 승객이 자신의 자리에 앉을 확률만 고려해주면 된다.
∴1/n
2) 첫 번째 승객이 자신의 자리에 앉지 않는 경우
이 경우는 또 여러가지 경우로 나뉜다. 왜냐하면 첫 번째 승객은 2번부터 n번까지의 자리에 앉을 수 있기 때문이다. 첫 번째 승객이 i번째 자리에 앉는다고 가정해보자 (확률 1/n). 그럼 이제 취한 승객은 i번째 승객(단, 2 ≤ i < n)이 된다. i번째 승객의 선택은 크게 두 종류이다.
(a) 첫 번째 자리에 앉는다.
(b) 나머지 자리에 앉는다.
(a)를 선택하는 경우에는 1)과 마찬가지로 마지막 승객이 자신의 자리에 앉는 것이 분명하고, (b)를 선택하는 경우에는 다시 취한 사람이 이전되게 된다. 따라서 구하는 확률은 남은 사람이 n-i+1명이므로 P(n-i+1)이다.
∴∑1/n x P(n-i+1)
→ P(n) = 1/n + ∑1/n x P(n-i+1)
= 1/n (1 + ∑ P(n-i+1))
= 1/n(1/2 + P(2) + P(3) + .... + P(n-1) + 1/2)
P(2) = P(3) = 1/2이므로 귀납적으로 P(n)은 모두 1/2이다.