Guest mathfreak Posted October 11, 2004 Share Posted October 11, 2004 a line of 100 airline passengers is waiting to board a plane. they each hold a ticket to one of the 100 seats on that flight. (for convenience, let's say that the nth passenger in line has a ticket for the seat number n.) unfortunately, the first person in line is crazy, and will ignore the seat number on their ticket, picking a random seat to occupy. all of the other passengers are quite normal, and will go to their proper seat unless it is already occupied. if it is occupied, they will then find a free seat to sit in, at random. what is the probability that the last (100th) person to board the plane will sit in their proper seat (#100)? Link to comment Share on other sites More sharing options...
Duke Posted October 11, 2004 Share Posted October 11, 2004 no chance for poor Mr-100 Link to comment Share on other sites More sharing options...
jordan Posted October 11, 2004 Share Posted October 11, 2004 I don't know how to make this all into one probability, but my simple guess would be: There is a 1/100 chance that the first guy takes seat #100. There is also a 1/100 chance that the first guy would take seat #2. If guy one takes seat #2, then there is a 1/99 chance that guy two takes seat #100. Now, when guy three gets on, I first thought there would be a 2/99 chance that his seat would be taken, but I think that's wrong. If guy one doesn't pick seat #2, then the odds would be 1/99 that seat #3 is taken, not 2/99. Ok. Enough from me. I don't know how to add all of that up, but I think it's the right start to the problem. Link to comment Share on other sites More sharing options...
YT2095 Posted October 11, 2004 Share Posted October 11, 2004 Why didn`t airport security arrest the crazy person? Link to comment Share on other sites More sharing options...
Kedas Posted October 11, 2004 Share Posted October 11, 2004 Probably close to 1/100, because that would be the chance if the first 99 go sit at random places. just a thought But like YT2095 said they really should arrest that person edit: For every person that comes in there is always 1 seat to make it right again. (except for the last person), not 100% sure though --- hmm doesn't seem to work but it was just a thought Link to comment Share on other sites More sharing options...
MandrakeRoot Posted October 12, 2004 Share Posted October 12, 2004 The probability that person 100 can not sit on his seat is 1/100 + 99/100*1/99 + 99/100 * 98/99 *1/98 + ..... (probability that person one takes his seat + the probab that he takes another and person 2 takes his seat etc....) There are 99 terms making this 99/100 and thus the probability that he will sit on seat 100 1/100 . Mandrake Link to comment Share on other sites More sharing options...
Kedas Posted October 12, 2004 Share Posted October 12, 2004 The probability that person 100 can not sit on his seat is 1/100 + 99/100*1/99 + 99/100 * 98/99 *1/98 + ..... (probability that person one takes his seat + the probab that he takes another and person 2 takes his seat etc....) There are 99 terms making this 99/100 and thus the probability that he will sit on seat 100 1/100 . Mandrake Wrote that down also but getting 99 times 1/100 did 'feel' wrong. (maybe I should just believe in this logic ) Anyone that tried it with a program to prove it? Link to comment Share on other sites More sharing options...
Kedas Posted October 12, 2004 Share Posted October 12, 2004 I just quickly wrote a program out of curiousity. but I got a chance of around 1/2 ?? Do you see something wrong in the program? Dim person(100) As Integer Dim Random As Integer Sub crazy() Countright = 0 Count = 0 Do Count = Count + 1 'attempts For n = 1 To 100 'init loop person(n) = 0 Next n Random = RandomNumbers(1, 100) 'first crazy person person(1) = Random 'takes seat number random For n = 2 To 100 If CheckIfFree(n, n) Then person(n) = n 'if their seat is free then take it Else: Do 'take a free random seet Random = RandomNumbers(1, 100) OK = CheckIfFree(Random, n) 'random=seat number , n=number of persons with a seat If OK Then person(n) = Random 'if free take it Loop Until OK 'if not free pick an other seat End If Next n 'the same for the next person If person(100) = 100 Then Countright = Countright + 1 Loop Until Count = 1000 Debug.Print (Countright / Count) End Sub Function CheckIfFree(ByVal location As Integer, ByVal personcount As Integer) As Boolean Dim personNR personNR = 0 Do personNR = personNR + 1 CheckIfFree = True If person(personNR) = location Then CheckIfFree = False Loop Until (personNR = personcount Or CheckIfFree = False) End Function It's slow though because random numbers are always choosen from 1 to 100 also if there are only two seats free so it has to generate much more random numbers this way to get the right one. person(x)=y x=number of the person that comes in y= seat that he took Link to comment Share on other sites More sharing options...
JHAQ Posted October 12, 2004 Share Posted October 12, 2004 I was going to say 100! but am not sure Link to comment Share on other sites More sharing options...
MandrakeRoot Posted October 13, 2004 Share Posted October 13, 2004 I just quickly wrote a program out of curiousity.but I got a chance of around 1/2 ?? Do you see something wrong in the program? I wrote a little matlab program which runs quite fast and indeed you are right. There is a flaw in the reasoning i gave above. If person 1 takes seat k then all people 2,...,k-1 can sit normally in their place. Person k will choose one seat from the 100 - k + 1 remaining etc... So the probability would be the sum over k of (person k takes the seat of 100 + person k does not take the seat of 100 * person k + 1 takes the seat of 100 etc...) I dont have time to write it out completely but i guess that would turn out to be 1/2 like the programs seems to show.... Mandrake Link to comment Share on other sites More sharing options...
MandrakeRoot Posted October 13, 2004 Share Posted October 13, 2004 In fact it is easy : Take the problem of n seats and n passengers of which the first is crazy like in the above problem for n = 100. n = 2 => This is easily seen that the probability that passenger two can sit on his seat is 1/2. Now Assume that the probability that passenger n can sit on his seat is 1/2, then for n+1 we obtain : 1) passenger 1 sits on his own seat 1/(n+1) 2) passenger 1 sits on any seat except for seat (n+1) : probability (n-1)/(n+1) Now rename seat and remark this is the same problem as problem with only n passengers . We obtain all in all therefore the probability that passenger (n+1) can sit on his seat with (n+1) seats is 1/(n+1) + (n-1)/(n+1)*1/2 = 1/2 So indeed it is 1/2, like the programs show Mandrake Link to comment Share on other sites More sharing options...
YT2095 Posted October 13, 2004 Share Posted October 13, 2004 doesn`t it all depend on what order the passengers are let onto the plane? imagine the "crazy guy" takes seat 2 when he should have seat 1. won`t all the other GOOD passengers take their appropraite seats accordingly, leaving the guy that had seat 2 to either sort it it with crazy man or take his allocated seat? the error would be 1 in 100, leaving only 2 people to sort it out, the person whos chair it was and crazy one! even at random, it`s still only an Offset problem, no matter what order they board, or even if they take the seat 1 number higher up, it`s just an offset Link to comment Share on other sites More sharing options...
MandrakeRoot Posted October 13, 2004 Share Posted October 13, 2004 The way i understood it was that the passengers went in only when the previous one is seated (somewhere). Like in a stack where you can only pop off one thing at a time ! Mandrake Link to comment Share on other sites More sharing options...
YT2095 Posted October 13, 2004 Share Posted October 13, 2004 but the 98 passengers will pick their own seats as allocated on their ticket, that will only leave the problem with the crazy guy and the guy whos seat he took Link to comment Share on other sites More sharing options...
Kedas Posted October 13, 2004 Share Posted October 13, 2004 but the 98 passengers will pick their own seats as allocated on their ticket, that will only leave the problem with the crazy guy and the guy whos seat he took In real life yes but here that person without seat will take an other seat (wrong seat). The order how they come in doesn't change the chance. It will have an other result but the chance will stay 1/2. Even if the crazy person doesnt go in first, but not last. person 100 must be last (the person that has the chance of 1/2) Link to comment Share on other sites More sharing options...
Guest dimension Posted October 15, 2004 Share Posted October 15, 2004 1/100, I think Every one is random, the poor man can select one seat from 1 to 100, but only no. 100 belongs to him Link to comment Share on other sites More sharing options...
MandrakeRoot Posted October 15, 2004 Share Posted October 15, 2004 1/100' date=' I thinkEvery one is random, the poor man can select one seat from 1 to 100, but only no. 100 belongs to him[/quote'] We have demonstrated up that the probability is 1/2. Mandrake Link to comment Share on other sites More sharing options...
Guest Dr.Zak Posted October 16, 2004 Share Posted October 16, 2004 I would like to say that 1) let the crazy man have a seat number (i) 2) let th crazy man take the seat number (k) and (i < k < 100 ) (for convenience, let's say that the nth passenger in line has a ticket for the seat number n.) 3) If n < k the nth passenger takes his right seat and there is no problem 4) If n >= k the nth passenger change his seat randomly 5) then the probability of occuping certian seat (but not kth seat) by (k)th passenger = 1 / (100-k+1) the probability of occuping certian seat (but not (k+1)th seat) by (k+1)th passenger = [( 100-k)/ (100-k+1)]*[1 / (100-k)] the probability of occuping certian seat (but not (k+2)th seat) by (k+2)th passenger = [( 100-k)/ (100-k+1)]*[( 100-k-1)/ (100-k)]*[1 / (100-k-1)] . . . and so on the probability of occyping certian seat (but not 100) by the passenger 100 =[( 100-k)/ (100-k+1)]*[( 100-k-1)/ (100-k)].......*[2 /3]*[1/2] =[( 100-k)!/ (100-k+1)!] =[1/ (100-k+1)] and this probability valid for seat no 100 where k < 100 but if k=100 the seat is the other one Link to comment Share on other sites More sharing options...
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now