I came across this interesting little math problem by Oliver Roeder that I thought I would pass on. I actually worked it out while I was waiting to board my plane on my return from California yesterday.
There’s an airplane with 100 seats, and there are 100 ticketed passengers each with an assigned seat. They line up to board in some random order. However, the first person to board is the worst person alive, and just sits in a random seat, without even looking at his boarding pass. Each subsequent passenger sits in his or her own assigned seat if it’s empty, but sits in a random open seat if the assigned seat is occupied. What is the probability that you, the hundredth passenger to board, finds your seat unoccupied?
As with all such puzzles, how you arrive at the answer is more interesting than the answer itself.
The above website runs a regular weekly math feature called The Riddler.
My intuitive guess is 0.505
0.01 (probability that #1 gets the right seat) + 0.5x0.99 (toss-up for the last seat if #1 gets the wrong seat).
I heard this riddle on click and clack car talk a couple months ago. Yes, I completely agree, how one arrives to the answer is really neat. Can’t wait to spend many hours solving the other math riddles. Thanks for sharing the link!
Here are a couple fun ones:
(Easier but not intuitive) If you had a belt that wrapped around the Earth and the two ends of the belt met perfectly flat on the ground, how far off the ground would the belt hover around the entire Earth if the belt were 1 meter longer in length? Imagine a perfectly circular belt around a perfectly spherical Earth.
(Harder) Now instead of having a perfect circle around the Earth with that longer belt, how high off the ground would the two ends meet if you cinched the belt? Imagine a circle with a peak/triangle where the belt ends meet.
Both answers did not seem intuitive to me. And that’s why you gotta love math!
Only one person is obnoxious, 99% likely to take the wrong seat. But after, all are cooperative.
If the first person takes the wrong seat, the second person is 98% likely to get their own, and 1% likely to take the first person’s seat, hence there is only 1% chance of taking the wrong seat.
This is true for all subsequent passengers three through 99, only a 1% percent chance of the wrong seat, so it’s only 1% for the hundredth and last person.
Unless my thinking is completely wrong.
I’d want to run some more math on it, but my answer is that you have a 50-50 chance of finding your seat empty.
The naive approach would be to try to calculate the ugly, ugly probabilities of “Passenger N has a X% chance of finding their seat empty, therefore passenger N+1 has a Y% change of finding their seat empty.” I’m not gonna touch that with a ten foot pole.
A smarter approach would be to do an inductive proof. Let’s number passengers in reverse order -- so the first passenger to board is N, the second, N-1, all the way to you, passenger 1.
-- If there are two passengers, the chances of finding your seat empty are 1/2, as there’s a 50-50 chance Mr. Jerkface sits in his own seat.
-- If there are three passengers, there’s a 1/3 chance Mr. Jerkface sits in his own seat, a 1/3 chance he sits in your seat, and a 1/3 chance he sits in the second passenger’s seat, making passenger 2 the new Mr. Jerkface, giving you a 50% chance of getting your own seat (having assigned passenger 2 to the vacant seat of passenger 3). 1/3 + (1/3 * 1/2) = 50%.
-- For Mr. Jerkface N, there’s a 1/N chance they sit in the vacant seat left by the original Mr. Jerkface, and a 1/N chance they sit in your seat -- of these, you have a 50-50 chance of getting your seat Otherwise, they sit in the seat of passenger N-1 to 2, and by induction, the chances of you getting your seat from any Mr. Jerkface N-1 to Mr. Jerkface 2 is 50%.
The easiest approach (in my opinion) is to consider the ‘chain of displacement’. It’s essentially the inductive step, without the numbers. If a passenger sits in a random seat, one of three things is going to happen -- they’re going to take somebody else’s seat; they’re going to take the vacant seat (either their own, or the original one left empty by the first Mr. Jerkface). The only thing that’s going to end this chain is somebody taking the empty seat, or somebody taking yours. As both choices are equally likely, you have a 50% chance of getting your own seat.
It’s neat to realize that this problem doesn’t depend on the number of seats on the plane, and if there are X additional empty seats, your chances of getting your seat are (number of seats that end the chain in your favor)/(total number of seats that end the chain) = (1+X)/(2+X).
Affluenza Kid, Affluenza Kid’s mother, Cliven Bundy, Paul Elam, Martin Shkreli, Bill Kristol, or other?
I’m sorry, but I need more details before I can answer this.
Richard Feynman told the story of how he introduced John Von Neumann to the old cocktail party joke about the two trains:
There are two trains 100 miles apart heading toward eachother at 50mph each. A bee is between the two trains flying back and forth (it’s a bee, it’s not very smart) at 10mph. It starts in the exact middle heading toward one of the trains. How far does the bee fly before the trains meet and crush it?
Feyman says Von Neumann thought briefly and gave the correct answer. Feynman said, “I figured you’d know the trick to solving that one…” And Von Neumann said “Oh? There was a trick? Ah, yes.”
I’d better find my fucking seat unoccupied or some asshole is going to be standing in the aisle and it isn’t going to be me.”
Passengers:
I think Parse is right. Eventually, one of the passengers is going to take either your seat or the first passenger’s seat while looking for a random seat. The chances are equal between those 2 seats at any time a passenger chooses a random seat. If your seat is chosen first, you don’t get your seat. If the first passenger’s seat is chosen first, the chain of passenger displacement ends and you get your seat in the end. So your chances of getting your seat should be 50/50.
Belt around earth 1:
The circumference of a circle is C=2*Pi*r, where r is the radius. So you can calculate the radius of a circle as r=C/(2*Pi). If you increase the length of the belt by 1m, you get r_new=(C+1m)/(2*Pi)=C/(2*Pi)+1m/(2*Pi). The radius of the circle the belt encloses therefore increases by 1m/(2*Pi)=0.159m. So the answer is independent of the size of the original belt -- if you do the same thing around the Moon, the belt will hover 15.9cm above the ground too.
I was wrong in #1. Three initial possibilities (with first boarder = B1, etc);
(1) B1 picks their own seat (P=0.01)
(2) B1 picks B100’s seat (P=0.01)
(3) B1 picks any of the other seats (0.98).
(1) leads to no seating problems, and (2) only when B100 gets on.
As for (3), B1 and B100’s seats are on equal footing, so either will end up occupied with the same probability.
So,
0.01 (from (1)) + 0.5x0.98 (from (3)) = 0.5
#6
The exact middle of the track.
Marcus @6: The joke is that von Neumann did it the hard way, summing an infinite series in his head, in a few seconds. The ‘trick’ is that the trains meet in an hour, so the fly must have flown 10 miles.
“Mr. Jerkface”
Bit harsh. What if that person is 15 years old, moving interstate by themselves, has never been on a plane before, and didn’t realise that you had to sit in an assigned seat?
It’s a high probability that the person whose seat they have taken will just speak to the crew who will point out that they’re in the wrong seat… just sayin’.
Rob @#11: that’s correct.
Rob @11. The real trick is getting a 10 mph bee to outrace a 50 mph train.
Marcus @6. Are you sure it was Feynman? Eugene Wigner tells the anecdote in a 1966 documentary about von Neumann, at https://youtu.be/VTS9O0CoVng?t=1006 . In that story it’s a swallow which flies at 50 mph between two cyclists at 20 mph separated by 40 miles, and it’s Max Born who in the 1920s posed the question to von Neumann. (I’ve just updated the van Neumann Wikipedia article with that extra information.)
You take one marble out of the box marked “black/white”.
Doesn’t the bee fly into one of the trains before the trains run into each other?
Andrew @14: Oops, yeah. v[sub]bee has to be greater than v[sub]train.
Andrew Dalke@#14:
Are you sure it was Feynman?
Now I’m not. I thought it was but I could easily be mistaken.
With respect to the bee/train speeds in the problem, I chose numbers that were easy on my brain; I don’t remember the exact numbers. I should have said that clearly in my comment but I didn’t. Sorry. The purpose of my comment was not to dwell on the puzzle, but rather Von Neumann. (FWIW I think the chance is pretty high that Von Neumann, who was an amazing calculator, figured out the shortcut and was just messing around.)
Von Neumann, Feynman, et al, were from the period where calculating fast was a game that was played even at the highest levels of knowledge. In his wonderful “los alamos from below” Feynman recounts a story of calculating with Hans Bethe -- guys like Feynman, Bethe, Von Neumann, Oppenheimer, could generally rattle off pretty accurate approximations of just about anything that could be done in a human brain. Feynman also tells a story about getting stumped with cocktail party puzzlers -- for years people would come up to him, “have you heard the one about the guy who’s dog leash…”
“Yeah, the answer is 12″
Oh.
And someone comes up to him with one he hadn’t heard and gets part way into the first sentence and Feynman takes one of his guesses, ” … the girl was dead.” and the guy was blown away because Feynman was right. I guess at a certain point it becomes like guessing who’s going to get killed in any given game of thrones season: whoever you least would expect? They’re toast.
The response in this bee-train story is attributed to von Neumann but the person who posed the question is unspecified. You can see the long-form solution here.
Marcus @18. What you say about Los Alamos is certainly true. In Wigner’s account, the puzzle incident took place in the 1920s. It likely occurred in Germany as Born -- who Wigner says posed the question -- and von Neumann lived there at the same time during that decade. It almost certainly didn’t take place in the US.
The von Neumann documentary I linked to goes into more detail about him as a person, including a couple of clips of him speaking. Herman Goldstine tells a second anecdote about von Neumann’s mental computing prowess at https://youtu.be/VTS9O0CoVng?t=2334 , which you might also enjoy.
The Feynman puzzle story, by the way, is from “Surely You’re Joking, Mr. Feynman”; at page 7 of http://www.chem.fsu.edu/chemlab/isc3523c/feyn_surely.pdf .
My guess is this has to do with the concept of cycles. Consider this example:
1. Person #1 sits in person (on average) #50’s seat.
2. Person #2-49 will all sit in the correct seat.
3. Person #50 will choose a seat at random from the remaining, which will be on average Person #75’s seat.
4. Person #51-74 will sit in the correct seat.
5. Person #76 will choose a seat at random from the remaining, which will be on average Person #87’s seat.
…
This will continue until, on average, person #98 will choose at random between seat #99 and seat #100.
I’m going to put this at 50%.
I meant to delete the “cycles” concept, since it had nothing to do with it after I finished my reasoning.
I’ve altered my thinking. I believe I have the answer:
Let’s label each passenger P_1 through P_100. P_1 sits random in seat S_k. At this point, seats 2 through k-1 fill up just fine, at which point passenger P_k now must choose among the remaining seats, of which there are 100 -- (P_k-1).
Note that at any time a passenger P_k chooses seat 1, then all of the remaining seats fill up normally and you get your own seat. THIS IS THE ONLY WAY YOU WILL GET YOUR SEAT. The question then is, how what is the probability that any one of the “choice” passengers picks seat 1?
Each passenger P_k who makes a choice has a probability of 1/(100 -- (P_k-1) of choosing seat #1. Therefore the probability of none of that happening by the time you get on the plane is the product of probabilities (1-1/(P_k-1)) for k = 1 to N, where N is the number of passengers who make a choice. Each time a passenger chooses, we can assume that their choice is uniformly random.
At this point, we need to figure out the probability that any given passenger P_k will encounter this choice. As a quick intuition, passenger #3 is very unlikely to make this choice, because that would required either passenger #1 to choose seat 3 or passenger 1 took seat 2 and passenger #2 took seat 3. Similarly, passenger #4 is a “choice passenger” if either:
1) passenger 1 chose seat 4,
2) passenger 1 chose seat 2 and passenger 2 chose seat 4
3) passenger 1 chose seat 3 and passenger 3 chose seat 4
4) passenger 1 chose seat 2, passenger 2 chose seat 3, and passenger 3 chose seat 4
We can see at this point that the probability of any particular passenger being a “choice” passenger depends on the choices of those previous, and that there will always be exactly P_k ways for the K-1 passengers before to take passenger P_K’s seat.
Therefore, the probability of any particular passenger being chosen is P_k/100. Now we have all of the pieces: the probability of each passenger making a choice, and the probability of each of those passengers choosing seat #1. Thus the probability that you get your own seat becomes:
p(you get your seat) = prod(1 -- (P_k makes choice* P_k picks seat 1))
which equals the product from 1…K=99 of (1 -- (K/100) * (1/(101 -- K)))
Which for N = 100 equals 2.68%.
More generally, for N people on the plane, the probability will be equal to prod_(k=1:N) of (1 -- (K/N) * 1/(N-K+1))
Marshall: No, by the time B100 boards, only their seat (S100) or B1’s seat (S1) can be unoccupied, with equal probability.
If B1 picks S1 or S100, all passengers from B2 to B99 get their own seats, and B100 will get either S1 or S100 with equal probability.
If B1 picks Sk (k between 2 and 99), everyone gets their own seat until Bk gets on. If Bk picks S1 or S100, again, everyone after gets their own seat, leaving S1 or S100 free for B100.
If Bk picks Sn (n between k+1 and 99), then Bn is in the same boat as Bk was. Rinse and repeat, and in the end it is always S1 or S100 which ends up being free, with equal probability.
Another way of putting it: As soon as either S1 or S100 is occupied, everyone following, up to B99, is guaranteed to get their own seat, leaving one of S1 and S100 free. This is the sense in which S1 and S100 are on equal footing.
The chance of the last person getting their own seat is 99%.
The problem is equivalent to one of the first 99 people picking the 1st person’s seat, because once that happens, everyone from then on gets their assigned seat.
For the first person, the chance they pick their own is 1%.
For the second, the chance they pick the first person’s seat is 99/100 (first person doesn’t pick their seat) x 1/99 (second person picks first persons’ seat) = 1%
The pattern continues, with the nominators and denominators cancelling out at every step until you’re just left with 1/100.
Same goes for the last person, who has only a 1% chance of ending up in the first person’s seat, hence 99% in their own. Or, if you prefer, you sum the chances of any of the first 99 people getting to sit in the first person’s seat, and get 99% that way.
(All of which is just a fuller statement of left0ver1under’s correct answer, of course).
Ben Wright @26:
No! The second is looking for their own seat. The only way they can get the first person’s seat is if the first person chose the second person’s (1/100), in which case the second chooses a seat at random from the remaining 99 (1/99). So the probability that #2 person picks #1’s seat is 1/99*100 = .000101…, or about .01%
where * is multiplication, not ‘to the power’.
Rob Grigjanis @24: you’re totally right.
The answer is up, for those who haven’t checked.
http://fivethirtyeight.com/features/can-you-decode-the-four-secret-messages/
More than one person got it right, but I wasn’t one of them.