Over at Programming Praxis, the author once asked about the Boarding Pass Problem:
One hundred people line up to board an airplane. Each has a boarding pass with assigned seat. However, the first person to board has lost his boarding pass and takes a random seat. After that, each person takes the assigned seat if it is unoccupied, and one of unoccupied seats at random otherwise. What is the probability that the last person to board gets to sit in his assigned seat?
The author offers a nice simulation in Scheme to solve this mathematical recreation, which comes from P. Winkler.1
Once we get the recurrence relations, it is easy to call Mathematica to the rescue:
RSolve[{n*p[n] - (n - 1)*p[n - 1] == p[n - 1], p[2] == 1/2}, p[n], n]
(* {{p[n] -> 1/2}} *)
Here’s a more direct and brute force approach, using a Monte Carlo simulation:
SeedRandom[101];
simulate[n_] := Module[{xs = ConstantArray[False, n], value},
xs[[RandomInteger[{1, n}]]] = True;
Do[
If[!xs[[i]],
xs[[i]] = True,
value = RandomChoice[Flatten[Position[xs, False]]];
xs[[value]] = True
],
{i, 2, n - 1}
];
!xs[[n]]
]
Here’s the result on 10,000 trials:
N[Mean[Boole[Table[simulate[100], {10000}]]]]
(* 0.5095 *)
For the interested reader, see also The lost boarding pass, and other practical problems by Geoffrey R. Grimmett and David R. Stirzaker. David Robinson wrote a simulation in R as well.
♪ Mirror of Haze • Listen to the Trees
Peter Winkler. Mathematical puzzles (revised edition). A K Peters/CRC Press, New York, 2024 ↩︎