Author |
Topic: Insane passenger (Read 3979 times) |
|
BNC
Uberpuzzler
Gender: 
Posts: 1732
|
 |
Insane passenger
« on: Oct 25th, 2003, 6:34am » |
 Quote  Modify
|
A line of N passengers is waiting to board an empty train. Each of them is holding a ticket to one of the N seats on that train (since it doesn't matter, let's say that the n'th passenger in line has a ticket for the seat number n.) They are boarding one at a time.
Unfortunately, the first person in line is insane, and will ignore the seat number on his ticket, picking a random seat to occupy (1-N). All the other passengers are quite normal, and will go to their proper seat. But, if that seat is already occupied, they will find a free seat to sit in, at random.
What is the probability that the last person to board the train (the N'th passenger) will sit in his proper seat (#N)?
|
| « Last Edit: Oct 25th, 2003, 7:12am by BNC » |
 IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
visitor
Guest
|
Since I don't know much about probabilities, everything is 50:50 to me. But in this case I think I may actually be right.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Insane passenger
« Reply #2 on: Oct 25th, 2003, 9:45am » |
Quote Modify
|
I think this is allready somewhere, but with a plane instead of a train..
I don't remember the answer though..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Insane passenger
« Reply #3 on: Oct 25th, 2003, 11:46am » |
Quote Modify
|
I don't recall seeing anything like this before, but that's no guarantee.
Here is a related question: suppose the uncooperative passenger's insanity takes the form of paranoia. He refuses to sit in the seat assigned him because he believes it is a trap. He still chooses his seat randomly, but only from among the remaining n-1 seats. What is the probability of the last passenger getting his assigned seat now?
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
I think the answer would be,
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Insane passenger
« Reply #5 on: Dec 1st, 2003, 9:31pm » |
Quote Modify
|
I knew this puzzle should be on the site... 
Here's another related question: in the original formulation, what's the probability of the i-th passenger to sit in her (i-th) seat?
|
| « Last Edit: Dec 1st, 2003, 9:32pm by Barukh » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2872
|
|
Re: Insane passenger
« Reply #6 on: Dec 5th, 2003, 7:46pm » |
Quote Modify
|
For the original problem
::
If the insane guy sits in either his own seat or the last guys seat, the probabilities are then 1 and 0 respectively. For any other seat, i, the probability is the same as the 100-i passenger case (all earlier passengers sit in their own seat, the i'th passenger has a choice between seat 1 and all seats>i at random).
For 2 passengers, the probability is 0.5
For N>2 passengers, assuming that for N>k>1 the probability is 0.5, the probability is 1/N+0/N+(N-2)*(0.5)/N=0.5
Hence, by induction, for N>1 passengers, the probability of the last passenger sitting in his own seat is 0.5
::
For the paranoid first passenger
::
If he sits in any seat other than the last, it reduces to a smaller number of passengers case of the first version, so the probability is 0/(N-1)+(N-2)*(0.5)/(N-1)=(N-2)/(2N-2) or 49/99 for the 100 passenger case.
::
For the i'th passenger (non-paranoid version)
::
Consider a random order of the seat numbers. Use that to represent a seating order by: each time a passenger makes a "random" choice, he chooses the first seat on the list. Whenever a passenger sits in a seat, that seat is removed from the list. If someone chooses seat k>i or seat 1 before someone sits in seat i, then person i will come along before any further "random" choices are made (next person to choose "randomly" is person k or non-existent respectively). If no-one does, then i-1 people are sat in seats 2 to i before person i gets the chance, so i must precede all k>i and 1 in the list if person i is not to sit in the right seat. Only considering the order of i, all k>n and 1 in the list, gives i preceding the others 1 time in n-i+2
::
A variant: What is the expected number of passengers that end up in the wrong seat?
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2872
|
|
Re: Insane passenger
« Reply #7 on: Dec 9th, 2003, 7:05am » |
Quote Modify
|
T&B, your answer is wrong, at least in a couple of cases:
::
For N=2, the expected number in the wrong seat is 1 (non-paranoid) or 2 (paranoid). For N=3, it's 1.5 (non-paranoid) or 2.25 (paranoid)
::
Calculations:
::
N=2, non-paranoid: 1/2*0 (1st passenger in own seat) + 1/2*2 (1st passenger in other seat) = 0 + 1 = 1
N=2, paranoid: 1*2 (1st passenger must sit in only other seat) = 2
N=3, non-paranoid: 1/3*0 (own seat) + 1/3*2 (3rd seat) + 1/6*2 (2nd seat; 1st seat for 2nd passenger) + 1/6*3 (2nd seat; 3rd seat) = 0 + 2/3 + 1/3 + 1/2 = 1.5
N=3, paranoid: 1/2*2 (3rd) + 1/4*2 (2nd; 1st) + 1/4*3 (2nd; 3rd) = 1 + 1/2 + 3/4 = 2.25
::
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Insane passenger
« Reply #8 on: Dec 10th, 2003, 12:29am » |
Quote Modify
|
In the non-paranoid case, the expected number is E(n) = Hn-1 = 1+1/2+...+1/(n-1). For the paranoid case, Ep(n)=E(n)n/(n-1).
Reasoning:
If person 1 sits in seat i, then people 2 through i-1 get their own seats, and person i chooses from seats 1 or (i+1) through n. This is almost the same as the original problem for n-i+1 people, if we now think of seat 1 as belonging to person i. The difference is that if person i sits in seat 1, which happens with probability 1/(n-i+1), this is still a person in the wrong seat. Therefore:
E(n) = [sum]i=2n 1/n*[1+1/(n-i+1)+E(n-i+1)].
If we let an = E(n)+1/n, then:
an = 1 + 1/n*(a1+...+an-1),
a1+...+an-1 = (an-1)n,
and plugging into the formula for an+1:
an+1 = 1 + 1/(n+1)*[(an-1)n + an] = an + 1/(n+1),
and therefore an = Hn, and E(n) = an - 1/n = Hn-1.
[Editted with simpler derivation]
[Edit2]You know, I was thinking there should be a simpler argument, given the simplicity of the answer, and then I noticed that rmsgrey's post all but gives it away:
The probability that person i>1 doesn't sit in his own seat is 1/(n-i+2), and use linearity of expectation.[/Edit2]
|
| « Last Edit: Dec 10th, 2003, 2:04am by Eigenray » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2872
|
|
Re: Insane passenger
« Reply #9 on: Dec 11th, 2003, 7:29am » |
Quote Modify
|
on Dec 10th, 2003, 12:29am, Eigenray wrote:| rmsgrey's post all but gives it away |
|
It does? I mean, it does. Of course, how clever of you to spot that I'd deliberately made sure that it was a trivial extension from what I'd written, and it wasn't at all the case that I had no real idea how to solve the problem elegantly, and in fact hadn't even got a general expression for the answer in any shape or form... 
Nice to see the smileys getting in the spirit of the season too
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Insane passenger
« Reply #10 on: Dec 11th, 2003, 10:56pm » |
Quote Modify
|
To be fair, I found the recurrence (after the first two I thought were right weren't), spent some time getting the generating function which turned out to be useless, then I just asked Maple who gave me some ugly formula involving the digamma function and refused to simplify it, then I found that was the same as [psi](n)+[gamma], then Mathworld told me what that was, and then I was able to prove it inductively. Then, rereading your post for some insight into a simpler proof, it hit me. Of course, it's much more obvious if you already know the answer.
|
|
IP Logged |
|
|
|
hawkxor
Newbie
Gender:
Posts: 5
|
|
Re: Insane passenger
« Reply #11 on: Dec 7th, 2008, 3:39pm » |
Quote Modify
|
Sorry for revival, but it's worth mentioning the simple solution to the original question:
Consider boarding of the 100th passenger. Certainly seats 2-99 are all full, for sane passenger would have sat in his seat if not already taken. Empty seat must be either the 1st or the 100th, and is either with equal probability by symmetry. Hence answer is 1/2.
I was once on this board with name River Phoenix, but looks like account got deleted.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Insane passenger
« Reply #12 on: Dec 8th, 2008, 12:30am » |
Quote Modify
|
on Dec 7th, 2008, 3:39pm, hawkxor wrote:| I was once on this board with name River Phoenix, but looks like account got deleted. |
|
The account is still there. You can try password recovery, or if you have a different email-address you could try emailing William (although then there's the issue of proving it's really your account).
|
| « Last Edit: Dec 8th, 2008, 12:31am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove