The Car Talk Puzzler (nongambling)

[uuDevil]

The NPR radio show "Car Talk" has a semiregular "puzzler" that they present to their listeners. This week's puzzler is a probability problem:

[ QUOTE ]

One Seat Left. Is It Yours?
.
RAY: You're one of a hundred people standing in line to get onto an airplane that has 100 seats. There's a seat for every person who's in line, and each of you has a boarding pass for your assigned a seat. The first person to walk onto the plane drops his boarding pass and, instead of picking it up, decides, "I'm just going to sit anyplace." He takes a seat at random.
.
Now, every other passenger will take either his assigned seat or, if that seat is taken, that passenger will take any seat at random.
.
TOM: I've been on that flight!
.
RAY: Because you are such a kind, generous, and accommodating person, you are the last passenger to walk onto the plane. Obviously, there's going to be one seat left, because everyone else is sitting in his correct seat, or not.
.
The question is: What are the chances that you get to sit in your assigned seat?
.
TOM: A snowball's chance in hell!
.
RAY: I'm going make this multiple choice.
.
A: 1 out of 2.
B: 1 out of 10.
C: 2 out of 50.
D: 1 out of 100
E: Zero.
.
Think you know?


[/ QUOTE ]

I'm not sure what the prize is, if any. /images/graemlins/tongue.gif But if you want to you can submit your answer at their webpage and maybe get your name mentioned on the air:

http://www.cartalk.com/content/puzzler/transcripts/200440/index.html

[MrBlini]

Nice puzzler. Rather than submit my answer here and spoil the fun: One of the choices here is the correct answer when the number of passengers and number of seats available are both changed to ten.

[pzhon]

Method 1 in white:
<font color="white">
Let the first person's seat and your seat be 1A and 1B, respectively or not. Ignore what happens everywhere else. Just watch what happens to these two seats. Precisely one person will sit in these two seats before you board. The person who sits in 1A or 1B has an equal chance to choose 1A rather than 1B, so the probability is 1/2 that your seat is unoccupied.</font>

Method 2 in white:
<font color="white">
Let the probability you get your own seat in this scenario with n passengers be p(n). Where does the first person sit?
* With probability 1/n, the first person sits in the right location, and you get your seat with probability 1.
* With probability 1/n, the first person sits in your seat, and you get your seat with probability 0.
* With probability 1/n, the first person sits in the seat of person i+1, and after passengers 2 through i sit down, passenger i+1's seat is occupied, and passenger i+1 chooses randomly. This is the scenario with n-i passengers, so you get your seat with probability p(n-i).

p(2) = 1/2. Suppose p(2) through p(n-1) are 1/2.
p(n)= (1+0+p(n-1)+...+p(2))/n
=(n/2)/n = 1/2.
So, by (strong) induction, the probability you get your own seat is 1/2.</font>

Nice problem.

[SossMan]

I'm not sure I understand the structure...let's say David is the 1st passenger who dropped his boarding pass and picks a seat at random.

What happens when Mason (who was 27th in line) goes to his seat and David is sitting in his seat? Does he, then, pick another seat and the process continues?

[MrBlini]

Yes, Mason picks (at random) Al's seat.

Now Al is going to have to do the same when he boards.

[tpir90036]

I am not sure I understand your method 1 solution. Why does "precisely one person" have to be sitting in those two seats? Two people could end up randomly selecting them just as easy as any other seat on the plane if theirs had been already randomly taken when they get on.

[RocketManJames]

[ QUOTE ]
Nice puzzler. Rather than submit my answer here and spoil the fun: One of the choices here is the correct answer when the number of passengers and number of seats available are both changed to ten.

[/ QUOTE ]

I saw this problem maybe a year ago, and a few friends and I solved it. But, if I recall, for N passengers, N &gt; 3, the answer remains constant. Does not matter if there are 10, 100, or 1000 passengers.

-RMJ

[Paul2432]

[ QUOTE ]
I am not sure I understand your method 1 solution. Why does "precisely one person" have to be sitting in those two seats? Two people could end up randomly selecting them just as easy as any other seat on the plane if theirs had been already randomly taken when they get on.

[/ QUOTE ]

Once either of seats 1A or 1B are occupied, every passenger will have his seat available, so noone will sit in the other seat until the last passenger boards.

Paul

What's the trick to reading the "answers in white"? What is see is, well, just white. . . /images/graemlins/confused.gif

[slickpoppa]

try to highlight that area with your cursor like you were going to copy and paste something

[uuDevil]

[ QUOTE ]
I'm not sure I understand the structure...let's say David is the 1st passenger who dropped his boarding pass and picks a seat at random.

What happens when Mason (who was 27th in line) goes to his seat and David is sitting in his seat? Does he, then, pick another seat and the process continues?

[/ QUOTE ]

So there is a poker application?

I think this situation may be undefined. However (don't tell the mathematicians), if you cancel the infinities, I think you'll still get the right answer. /images/graemlins/tongue.gif

[GuyOnTilt]

It seems like the answer should be 1:1. As soon as someone picks your seat as a replacement for their own or picks the first person's original seat, no one else will be misseated. So when it's your turn to board, the last seat remaining should either be the one you were assigned to, or the one the first passenger was assigned to. I'm not positive though, but that's what my head wants to believe... I can't think of a scenario where both yours and the first passenger's seat are both taken when you board. So yeah, I'll pick 1:1.

GoT

[RiverTheNuts]

Correct.

If someone's seat is gone theyll randomly pick another... unless they pick yours or the first persons, this chain will continue. If no one has picked yours or the first persons when the 2nd to last person boards, its 50/50

If someone has picked yours or the first persons, then every passenger after this will have his/her seat available, so it will still be 50/50 as to if that person chose yours or the initial person's