Due to the stimulating questions here, this question might have been posted earlier. Sorry if it has. Also this question involves an airplane. I just used the word "plane" for the alliteration.
There are 100 people on a plane. Let's label them Persons 1-100. The order the people sit down is determined by his or her seat number. There are 100 seats, labeled Seats 1-100. Person 1 does not know where to sit and will sit in any random passenger seat. Persons 2-100 are assigned to their corresponding seat number and will sit there. If someone is already sitting at the assigned seat, the person would sit at a random unoccupied passenger seat. Here's an example:
Person 1 sits in seat 5
Person 2 sits in Seat 2
Person 3 sits in Seat 3
Person 4 sits in Seat 4
Person 5 sits in Seat 7
Person 6 sits in Seat 6
Person 7 sits in Seat 1
...
This is just one example of what might happen. The question is: What is the probability that Person 100 sits in Seat 100?
If there are any unclear parts please feel free to ask. I doubt i have left anything out, but if I did, please feel free to say so.
If this isn't solved by tomorrow, I'll give a hint.😀
Let p(n) be the probability that the last person will sit in the last seat if there are n seats and people.
First calculate:
p(2)=1/2
p(3)=1/2
p(4)=1/2
p(5)=1/2
Hm... I notice a pattern. Proveable by strong induction, or whatever it's called. Unless of course, I'm completely wrong.
OK.
Lets call the probability of someone sitting in the nth seat on an n-seater plane P(n)
For n=2
P(2) = 1/2 (the first guy either takes seat 1 or seat 2)
For n=3
P(3) = the chance of first guy sitting in seat + chance of first guy NOT sitting in seat x 2seater scenario
Therefore
P(3) = 1/3 + 2/3 * P(2)
= 1/3 + 1/3
= 2/3
P(4) = 1/4 + 3/4 * P(3)
= 1/4 + 2/4
= 3/4
P(n) = 1/n + (n-1)/n * P(n-1)
P(n) = (n-1)/n
So for our 100 seater plane the chances of holder of ticket 100 getting his seat is 1/100.
Which is surprising .. so I could be wrong!
chance of seat being taken:
P(2) = 1/2
P(3) = 1/3 + 1/3 x 1/2 = 1/2
P(4) = 1/4 + 1/4 x 1/3 + (1/4 + 1/4 x 1/3) x 1/2 = 1/2
p(5) = 1/5 + 1/5 x 1/4 + (1/5 + 1/5 x 1/4) x 1/3 + (1/5 + 1/5 x 1/4 + (1/5 + 1/5 x 1/4) x 1/3) * 1/2 = 1/2
p(n) = 1/n + 1/n x 1/(n-1) + (1/n + 1/n x 1/(n-1)) x 1/(n-2)...
= 1/n + 1/(n^2-n) + 1/(n^3-3n^2+2n)
This may help someone.
The answer's 1/2, but I can't quite prove it.
Ok, so we wish to calculate p(n)
Let's look at the first guy. If he takes seat 1 or seat n, we get probability of 1 and 0 respectively.
If he takes seat 2, then we have the n-1 seat scenario, because then person 2 has to choose randomly between n-1 seats, and the fact that every seat (except for 1) has been increased by one makes no difference, because so has the numbers of the people.
If he takes seat 3, then person 2 takes seat 2, and person three has to choose between n-2 seats, with the seats and people all having their numbers increased by two, thus making no difference.
Continuing in this fashion, we get that np(n) = 1 + 0 + p(2) + p(3) + ... p(n-2) + p(n-1). Clearly true by strong induction.
I invite some one to poke holes in my proof.
Originally posted by wolfgang59Sorry to say this, but indeed you are:
OK.
Lets call the probability of someone sitting in the nth seat on an n-seater plane P(n)
For n=2
P(2) = 1/2 (the first guy either takes seat 1 or seat 2)
For n=3
P(3) = the chance of first guy sitting in seat + chance of first guy NOT sitting in seat x 2seater scenario
Therefore
P(3) = 1/3 + 2/3 * P(2)
= 1/3 + 1/3
= 2/3
P ...[text shortened]... holder of ticket 100 getting his seat is 1/100.
Which is surprising .. so I could be wrong!
The calculation for P(3) should be
P(3) = 1/3 + 1/3 * P(2)
= 1/3 + 1/6
= 1/2
By using 2/3 you forgot that half of that chance is when person 1 sits in seat 3. In that case, person 3 obviously cannot sit in seat 3 anymore.
If you change that in your proof along with the identical mistakes in the other P(m)'s your proof will become a valid proof for P(n) = 1/2 for all n.
Originally posted by DejectionSorry, but I can't find any holes 🙂
Ok, so we wish to calculate p(n)
Let's look at the first guy. If he takes seat 1 or seat n, we get probability of 1 and 0 respectively.
If he takes seat 2, then we have the n-1 seat scenario, because then person 2 has to choose randomly between n-1 seats, and the fact that every seat (except for 1) has been increased by one makes no difference, because ...[text shortened]... -2) + p(n-1). Clearly true by strong induction.
I invite some one to poke holes in my proof.
Originally posted by TheMaster37I was calculating P(3) as a 1 in 3 chance he took seat 3 and a 2 in 3 chance he did not.
Sorry to say this, but indeed you are:
The calculation for P(3) should be
P(3) = 1/3 + [b]1/3 * P(2)
= 1/3 + 1/6
= 1/2
By using 2/3 you forgot that half of that chance is when person 1 sits in seat 3. In that case, person 3 obviously cannot sit in seat 3 anymore.
If you change that in your proof along with th ...[text shortened]... cal mistakes in the other P(m)'s your proof will become a valid proof for P(n) = 1/2 for all n.[/b]
My solution may be wrong but that is not the flaw.
greenpawn is correct IF they all choose at random, and more than one person can sit in a seat, and then everyone that isn't in seat 100 is put in seat 100 and anyone on seat 100 is killed, then the 100th person picks randomly.
With the original stipulation, dejection is correct.
Originally posted by greenpawn34Not quite. The only time the second person will not sit in seat 2 is if person one sat in seat 2.
Been thinking about this.
When the first guy gets on the plane it's 100/1 he
will sit in seat No.100
When the 2nd guy gets on it will be 99/1
When the 3rd guy gets on it will be 98/1 and so on...
So you do a factorial of 100 (99+98+97+96.....)and add 1.
This means the probability of person 2 sitting in seat 100:
P(2|S100) = (1/100) * (1/99)
This problem is very simple. At any given time, we are only dealing with only one person displaced at a time, everyone else will take their proper seat.
Now one of two things will happen eventually.
If the displaced person takes the first seat, then everyone else will be able to take their own seat, including the last person.
If the displaced person takes the last seat, then clearly the last person won't be able to, but will have to take the first person's seat.
If the displaced person takes any other seat, then the decision is passed to the person whose seat was taken, so that one of the top two WILL happen.
So we are only interested in which seat is taken first, Seat #1, or Seat #100. And since there is no reason to assume either is more likely, that makes it a 50/50 chance.
EDIT: The first person is considered "displaced" for purposes of analysis, as if he chooses either significant seat, then we know how it all ends.