The Car Talk Puzzler (nongambling)
 

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. [img]/images/graemlins/tongue.gif[/img] 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/puzzl...440/index.html

Re: The Car Talk Puzzler (nongambling)
 

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.

Re: The Car Talk Puzzler (nongambling) spoiler
 

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.

Re: The Car Talk Puzzler (nongambling)
 

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?

Re: The Car Talk Puzzler (nongambling)
 

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

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

Re: The Car Talk Puzzler (nongambling) spoiler
 

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.

Re: The Car Talk Puzzler (nongambling)
 

[ 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

Re: The Car Talk Puzzler (nongambling) spoiler
 

[ 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

Re: The Car Talk Puzzler (nongambling) spoiler
 

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

Re: The Car Talk Puzzler (nongambling) spoiler
 

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