The 'lost boarding pass' puzzle: efficient simulation in R

varianceexplained.org

35 points·Amorymeltzer··6 comments

Open articleView on HN

This problem was the weekly Puzzler on "Car Talk" on November 9:

http://www.cartalk.com/content/last-seat?question

Here’s a twist on the puzzle:

What if there are L seats, where L >= N. (If L > N, not all the seats are assigned to people)

What is the probability that the last person sits on his own seat?

The situation stops being a problem when someone either chooses seat 1 or seat N.

Because:

- If at any point someone chooses seat 1, then everyone else will get their chosen seat.

-If at any point someone chooses the last seat, everyone but the last guy gets his seat. The last guy gets seat 1, because it has to be free (if it wasn't , then my first condition would have applied).

So only seat 1 and N are possible, both having equal chance, thus 50%.

You can notice that the two conditions that resolved the "seat being taken" problem were when someone sat in a seat that no one else would have a ticket for. What kinds of seats are those? The 1st seat, the last seat, and empty seats.

This means that by adding L-N empty seats, the chances of the last guy having his seat is 1/(L-N + 1st seat + last seat) = 1/(L-N+2)

Yep, except that the guy has his seat if someone chooses any of the unassigned seats, so probability should be (L-N+1)/(L-N+2).

An interesting version of: All 100 people in line to board the plane drop their boarding passes and decide to sit wherever they please. How many do you expect to sit in their originally assigned seat?

This is one of those threads where having spoiler tags would be useful ;)

A hint / related keyword for a quick Google search for the answer is that yours is a question about fix points in permutations.

Reply on news.ycombinator.com