Back to Lessons

Boarding chaos

Drunk Passenger's Seat

100 seats on the plane. The drunk passenger ignores her ticket and picks one at random.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
Her ticket (seat #1) Where she sat
She sat in seat #43 — that's someone else's seat. Chaos begins.

One hundred passengers line up to board a plane. Each has a ticket for a specific seat. Passenger #1, unfortunately, is drunk. She ignores her ticket and sits in a random seat.

Drunk Passenger's Seat

100 seats on the plane. The drunk passenger ignores her ticket and picks one at random.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

Every other passenger is sober. They go to their assigned seat. If it's taken, they pick a random empty seat instead.

Boarding Process

100 seats. Passenger #1 is drunk. Step through each boarding one at a time.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

You're passenger #100, the last to board. What's the probability you end up in your own seat?

What do you think?
With 100 passengers, what's the probability the last passenger (#100) gets seat #100?

Run the simulation and slide the passenger count from 3 to 100. No matter the size, the rate hovers right around 50%.

Drunk Passenger

Why the details don't matter

The instinct is to trace through all 100 passengers and track cascading displacements, but that's a trap. The problem has a structure that makes the answer obvious once you see it.

Focus on just two seats: seat #1 (the drunk's assigned seat) and seat #100 (your seat). Ignore everything else.

At every step of the boarding process, only these two seats matter for the final outcome.

Whenever a displaced passenger picks a random seat, they will eventually either fill seat #1 or seat #100. Every other seat gets filled by its rightful owner sooner or later.

The domino chain

Displacements form a domino chain. Each displaced passenger either ends the chain by sitting in seat #1, dooms you by taking seat #100, or passes the problem to someone else.

The Symmetry Argument
Passenger 1 picks a random seat\text{Passenger 1 picks a random seat}
If she picks seat #1 (her own), everyone else boards normally and you get seat #100.
Step 1 of 6

Building intuition with small cases

The argument works for any number of passengers, and the smallest cases confirm it:

What do you think?
With just 2 passengers, passenger 1 is drunk. What's P(passenger 2 gets seat #2)?

3 passengers:

  • Drunk picks seat 1 (prob 1/3): everyone's fine. You (passenger 3) get seat 3.
  • Drunk picks seat 3 (prob 1/3): you're out of luck.
  • Drunk picks seat 2 (prob 1/3): passenger 2 is displaced, picks randomly between seats 1 and 3. Each has probability 1/2.

P(seat 3 free)=13⏟drunk picks seat 1+13⏟drunk picks seat 2×12⏟passenger 2picks seat 1=13+16=12P(\text{seat 3 free}) = \underbrace{\frac{1}{3}}_{\text{drunk picks seat 1}} + \underbrace{\frac{1}{3}}_{\text{drunk picks seat 2}} \times \underbrace{\frac{1}{2}}_{\substack{\text{passenger 2} \\ \text{picks seat 1}}} = \frac{1}{3} + \frac{1}{6} = \frac{1}{2}

Self-Referential Structure

The drunk passenger problem has a recursive structure. When a displaced passenger picks seat kk (for some other displaced passenger), the subproblem from that point forward is identical in structure to the original, just with fewer passengers. Because of this self-similarity, the result is 50% for any nn.

Each displacement creates an identical subproblem with fewer seats. The recursive structure guarantees the same 50/50 split at every level.

Recursive Structure

8 passengers. Watch how each displacement creates the same subproblem.

1—
2—
3—
4—
5—
6—
7—
8—
drunk'syours

Only two seats matter

Throughout the entire boarding process, seats 2 through 99 get filled correctly in sequence. The chaos only propagates when someone is forced out of their seat, and when that happens, the displaced person faces the same binary choice: will I end the chain by taking seat #1, or will seat #100 get taken first?

Every intermediate step preserves the symmetry between seats #1 and #100. No amount of cascading can break it.

This problem is a favorite in quant finance interviews at Goldman Sachs, Citadel, and DE Shaw. The interviewer wants to see you resist the urge to compute and instead identify the structural shortcut. Saying "by symmetry, only two seats matter" is the winning move.

Variations

What do you think?
What if the first TWO passengers are drunk (both pick random seats)? What's P(passenger 100 gets seat #100)?
What do you think?
What if the drunk passenger isn't first in line, but somewhere in the middle (say, passenger 50)? What's P(passenger 100 gets seat #100)?
10 passengers, passenger 1 is drunk. P(passenger 10 gets seat #10)? (decimal like 0.50)
1/3

The takeaway

The drunk passenger problem looks like it needs a 100-case simulation or a recursive formula. It doesn't. Only two seats — the drunk's assigned seat and yours — are in contention. By symmetry, each is equally likely to be the last one filled.

When you see a complex sequential process, ask: "What's the minimal state I need to track?"