|
||
|
Title: Insane passenger Post by BNC on Oct 25th, 2003, 6:34am 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)? |
||
|
Title: Re: Insane passenger Post by visitor on Oct 25th, 2003, 8:13am Since I don't know much about probabilities, everything is 50:50 to me. [hide] But in this case I think I may actually be right. [/hide] |
||
|
Title: Re: Insane passenger Post by towr on Oct 25th, 2003, 9:45am I think this is allready somewhere, but with a plane instead of a train.. I don't remember the answer though.. |
||
|
Title: Re: Insane passenger Post by Icarus on Oct 25th, 2003, 11:46am 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? |
||
|
Title: Re: Insane passenger Post by TenaliRaman on Oct 25th, 2003, 9:17pm I think the answer would be, |
||
|
Title: Re: Insane passenger Post by Barukh on Dec 1st, 2003, 9:31pm I knew this puzzle should be on the site... ;D 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? |
||
|
Title: Re: Insane passenger Post by rmsgrey on Dec 5th, 2003, 7:46pm For the original problem ::[hide] 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 [/hide]:: For the paranoid first passenger ::[hide] 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. [/hide]:: For the i'th passenger (non-paranoid version) ::[hide] 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 [/hide]:: A variant: What is the expected number of passengers that end up in the wrong seat? |
||
|
Title: Re: Insane passenger Post by rmsgrey on Dec 9th, 2003, 7:05am T&B, your answer is wrong, at least in a couple of cases: ::[hide] 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) [/hide]:: Calculations: ::[hide] 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 [/hide]:: |
||
|
Title: Re: Insane passenger Post by Eigenray on Dec 10th, 2003, 12:29am In the non-paranoid case, the expected number is E(n) = [hide]Hn-1 = 1+1/2+...+1/(n-1)[/hide]. For the paranoid case, Ep(n)=[hide]E(n)n/(n-1)[/hide]. Reasoning:[hide] 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[/hide]. [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:[hide] The probability that person i>1 doesn't sit in his own seat is 1/(n-i+2), and use linearity of expectation[/hide].[/Edit2] |
||
|
Title: Re: Insane passenger Post by rmsgrey on Dec 11th, 2003, 7:29am on 12/10/03 at 00:29:09, Eigenray wrote:
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 ;D |
||
|
Title: Re: Insane passenger Post by Eigenray on Dec 11th, 2003, 10:56pm 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. |
||
|
Title: Re: Insane passenger Post by hawkxor on Dec 7th, 2008, 3:39pm Sorry for revival, but it's worth mentioning the simple solution to the original question: [hide]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.[/hide] I was once on this board with name River Phoenix, but looks like account got deleted. |
||
|
Title: Re: Insane passenger Post by towr on Dec 8th, 2008, 12:30am on 12/07/08 at 15:39:36, hawkxor wrote:
|
||
|
Powered by YaBB 1 Gold - SP 1.4! Forum software copyright © 2000-2004 Yet another Bulletin Board |