rude_flier_explanation.md

Background for the rude_flier puzzle

Puzzle is posed at http://fivethirtyeight.com/features/will-someone-be-sitting-in-your-seat-on-the-plane/

See https://gist.github.com/RMGiroux/af436bed97ceb7b1f759 for perl implementation

Empirical results

Running my script shows the result is very close to 50% regardless of the plane size.

Theoretical explanation

This makes sense for a 2 passenger plane - there's a 50% chance that the rude flier took your seat.

Trying to explain why it's STILL 50% for larger planes is where I got confused.

For a 3 passenger plane

• 1/3 of the time, the rude flier picked his own seat (and you get your own seat for sure).
• 1/3 of the time, he picks YOUR seat, and your chance of getting your seat is 0.
• The OTHER 1/3 of the time, you get your seat 1/2 the time, since the 2nd passenger picked one of the remaining seats (RUDE and yours) at random.

So you get your own seat 1/3 + 1/3*1/2 of the time, which is 1/2.

Now, does this scale to higher plane sizes?

For a 4 passenger plane

• 1/4 of the time, the rude flier picked his own seat (and you get your own seat for sure).
• 1/4 of the time, he picks YOUR seat, and your chance of getting your seat is 0.
• 1/4 of the time, he took P2's seat
  • 1/3 of the time, P2 will take RUDE's seat, and you get your seat 100%
  • 1/3 of the time, P2 will take YOUR seat, and you get your seat 0%
  • 1/3 of the time, P2 will take P3's seat
    • 1/2 the time, P3 will take RUDE's seat, and you get your seat 100%
    • 1/2 the time, P3 will take YOUR seat, and you get your seat 0%
• 1/4 of the time, he took P3's seat
  • 1/2 the time, P3 takes RUDE's seat, and you get your seat 100%
  • 1/2 the time, P3 will take YOUR seat, and you get your seat 0%

So you get your seat 1/4 + (1/4 * (1/3 + 1/3 * 1/2)) + 1/4*1/2 = 1/4 + 1/8 + 1/8 = 1/2 of the time.

I sense a trend :)

I'm just going to declare victory here and claim that this extends out to an arbitrary plane size.