Suppose there are n people boarding a plane with n seats, and that each person has an assigned seat. Suppose the first person (Mr. Ford) decides he is above the assigned seats and randomaly (with equal probability for all seats) sits in any of the n seats on the plane. Each subsequent person to board the plane (people board one at a time) sits in their own seat if it is not yet occupied, and if it is occupied they sit in any of the remaining unoccupied seats with equal probability.

What is the probability the last person to board the plane will sit in their assigned seat.

As an example to make sure the problem is clear, let us take n=2 and have Mr. Ford assigned to seat 1 and Slagpit to seat 2. When Mr. Ford boards the plane with probability 1/2 he sits in seat 1, and thus slagpit will sit in seat 2, and with probability 1/2 he sits in seat 2 and thus slagpit will sit in seat 1. Thus when n=2, the probability is 1/2.

ttt this problem looks so fun (sorry I find threads with at leas 2 posts get looked at more:P)

My face hurts


Also, probability problems havnt keen in my field since UNI, but I'll scribble so
e things down and see if I can come up with something

1/n

I would like to add I gave this about 15 seconds of though, but thinking back on the stipulation that people try to sit in their own seat if possible, this answer seems increasingly wrong.

I'll see if I can find time to give it the due time it deserves later.

(n-1)/n is my guess, but it's probably wrong. I'll try and justify it later.

50% chance, because as soon as mrford takes the seat that is not his assigned seat, EVERYONE after him has the chance to either take their own assigned seat, or another seat that is not assigned to them because mrford is sitting in theirs.

but it isn't an instantanious problem, it is dynamic.

I've seen this question before.

I don't want to justify my answer and ruin the fun, but I feel pretty good about ((n-2)!*(n-2)+(n-1)!)/n!

With n not including Ford
n=1 => 1 = 1
n=2 => 1*1/2 = 1/2
n=3 => 1*1/2*2/3 = 1/3
n=4 => 1*1/2*2/3*3/4 = 1/4
n=5 => 1/5
n=x => 1/x

This is the chance that the last person won't sit in their own seat. So 1-1/n is the chance to sit in their own.

without a defined ammount of people getting on the plane, and a answer asking for the probability of the last person to board the plane, I am looking at a trick question?


I'd state that there is a 50% chance that the last person to board the plane gets their assigned seat. I'll justify that by saying this


When I sit down, there are three relevant possibilities:

A) I sit in seat z. In this case, guy z is guaranteed NOT to get his seat.

B) I sit in seat w. In this case, guy z is guaranteed to get his seat (since everyone from then on sits in their proper seat).

C) he sits somewhere else. This essentially just repeats the experiment by forcing some other passenger to sit in a random seat.

So A and B happen with equal probability. If C happens, then some other passenger (the one who's seat is taken) has to take a random seat, and again, there are the same three relavent possibilities as above.

So this is just a repeating random experiment, that eventually ends in state A or B. Since A and B are equally likely in each repetition of the experiment, common sense (and I guess some theorem of probability theory) tells us that the whole repeating experiment will end at A or B with equal probability.

More theory than complex equations IMO

As a lower bound for the probability, keep in mind that if the first person randomly sits in their proper seat, then everyone following them will sit in the correct seat as well (including the final boarder) and so the probability must at least be 1/n which is the answer some people have gotten so far.

However, consider that the first person (corresponding to seat A) sits in seat B, and then the second person whose proper seat is B sits in seat A, then the remaining passengers once again all sit in their assigned seat.

Thus the correct answer must be more than 1/n.

First of all, there wont be a answer like the one in your example (unless we make assumtions like you did in your example), since we have two unknowns.
Ns = Number of seats and Np = Number of passengers

so lets start with the basic, we can, to "dumb" it down abit say that the probability = amount of wanted outcomes/amount of possible outcomes. This is what you showed in your example.
Even if this is basic, we can strech it out to be valid also for more complex contexts.

As for your question, i belive you should turn it around, and calculate how many unwanted outcomes there are.

It would be far to easy to calculate the probability for the following : What is the probability that the last passengers seat ist taken when said person enters the plane, and just assume that the other Np could be assigned randomly like this : n x (n-1) x (n-2) x ... 3 x 2 x 1, but since its not random (they will try to sit in their seat first)
We have to move away from the domain of Combinatorics and into probability.

We know that the passengers can be seated in n! different ways.
This is only true if Ns=Np given by n! / (n-k)! = nPk where P = Permutation , in other words, this assumes the plane is fully booked, your problem does not mention this, so i take we have to make this assumtion to not over complicate the task at hand.

so we have to introduce a new unknown Nr , this is a passenger that sits in her/his designated seat.

n! / n1! x n2! x n3! x ... x nr!

Dont think its entirely correct , but this is my try !

You guys are giving this entirely too much thought!

50%

My previous calc is obvously wrong, I think ford's is too.

2 persons:
If there are two other people, there's a 50% chance that the person with it's seat free gets in first, followed by a 100% that the last person doesn't get its seat. If the person with the seat stolen enters first, it's a 50% chance/risk that he takes the remaining persons seat and 50% that he takes fords. This amounts to 25% chance for the last person to sit in its own seat.

3 persons:
The tree of possibilities for three persons is no that much harder, as all but one probabilities lead to the the calc above. I will call the person with the stolen seat Soviet from now on, and any other will be called Xenu.

1/3 that Soviet enters first -> 1/3 that Soviet takes fords seat and 2/3 that Soviet takes one of the others
I.e. a 1/9 chance that the last person will get bound to get its own seat after this event, and 2/9 resulting in the case above with 25%.

2/3 that Xenu enters first -> Also leads to the case above.

P = 8/9*0.25 + 1/9 -> 1/3

4 persons:

1/4 Sov -> 1/4 takes ford, 3/4 takes someone elses leading to the probabilty above
3/4 Xenu -> probability above

P = 15/16*1/3 + 1/16 = 3/8

5 persons:

1/5 Sov -> 1/5 takes ford, 4/5 takes someone elses
4/5 Xenu

P = 24/25*3/8 + 1/25 = 2/5

Hmmm, iterative solution?

P(n) = ((n^2-1)/n^2) * P(n-1) + 1/n^2
P(n) = ((n^2-1) * P(n-1) + 1)/n^2

Edit: this doesn't take into account the chance that ford takes his own seat and it didnt really count him as a person either, easily fixed.

P(n) = 1/n + ((n-1)/n) * S(n)
S(1) = 0
S(2) = 1/4
S(n>=3) = ((n^2-1) * S(n-1) + 1)/n^2

I see what you are doing there, and it makes 100% sense

but in regards to the parameters to this problem, I believe there is a much simpler solution.

If person a sits in my seat, then everyone gets their own seat

if person a sits in persons b seat, then person b can sit in anyones seat, and only that person is displaced.

It is east to look at this as being extremely complicated, but as it goes on the seat choices become more and more limited, considering that there is a limit to the n in this problem. It generally rests in th.....

You know what, I got this all figured out in my head but can't explain it really well. I'll try again later

still think it's 50%

But the 50% is easily disproved for n=2...?

I'd give you this though, as n goes to infinity, P may go towards 0.5. :)

The series according to my formula:
0
1/4
1/3
3/8
2/5
15/36
21/49
28/64
36/81
44/100

The fraction from the previous step has an uncanny way of forming an integer when multiplied with the n^2-1 part...

I already see the major problem here and therefore refuse to answer.
The problem is that Mr. Ford is seat 1 and Slagpit is in seat 2.
This is wrong as Slagpit would not sit near Mr. Ford.

I`m pretty sure (but cant prove) that its 50%

I have gotten 50% for 2, 3 and 4 persons involved.

See!

I'm not crazy

I just realized I'm still focusing on the "S" part from my problem. For all n but n=1 is P(n)=0.5 :)

Edit: note that n in my formula isn't counting ford

with 3 persons, If person A sits in person B`s seat, and person B sits in person C`s seat, person C cant sit in their seat, how do you account for that possible outcome in your formula ?

Its 50%

Two possible outcomes with equal likelihood

Outcome 1: Mr Ford takes someone's seat who takes someone else's seat etc. until somewhere along the line, someone takes Mr. Ford's seat.

Outcome 2: Mr Ford takes someone's seat who takes someone else's seat etc. until somewhere along the line, someone takes the last person's seat.

As soon as one of the two outcomes is met, the loop closes.

The Loop goes from Mr Ford takes person A's seat. Until we get to person A, everyone else takes their assigned seat. Then person A takes either your seat, Mr Ford's seat, or person B's seat. Until we get to person B, everyone else takes their assigned seat. Then person B takes either your seat, Mr Ford's seat, or person C's seat. We can go through as many people as we need to, but regardless of how many people we go through, the chances of it ending when someone takes Mr. Ford's seat are equal to the chances of it ending when someone takes your set.

By the way, all you fools using 'n's and numbers need to stop trying to do arithmetic and start doing mathematics.

I just realized I left out a part, and now it sums to 1/2 for all n.

The easiest way to describe it is the options for each person:

a) 1/n probability that they sit in their correct seat

b) 1/n probability that they sit in the last person's seat -> immediately removes possibility that the last person can

c) (n-2)/n probability that they sit in neither seat and we must continue to the next person.

Since 1 person has already gone, the next person has the same options, except n->(n-1). Additionally, if the first person is in their seat, then choice a) is the same probability but now corresponds to sitting in the first person's seat, then allowing everyone else to sit in their proper seat.

The third person is the same as the second except with n-2 and this goes on all the way down until the person before last has two options, and either he sits in his own seat (or the first person's seat) or in the last person's seat.

Okay, so let A(x)==1/x and B(x)==(x-2)/x corresponding to a) and b) above, then we can write out the general form of the probability that the last person sits in their seat as:

A(n) + B(n)*A(n-1) + B(n)*B(n-1)*A(n-2) + B(n)*B(n-1)*B(n-2)*A(n-3) + ...

until we get A(0) (which we will define to be 0).

If you plug in those equations for A() and B(), this reduces to:

1/n + 1/(n*(n-1)) + (n-2)/(n*(n-1)) + (n-3)/(n*(n-1)) + (n-4)/(n*(n-1)) + ...

which reduces to:

1/(n*(n-1))*(n-1 + n-2 + n-3 + n-4 + n-5 + ... )

which we can write as:

((n-1)*n - (1+n-1)/2*(n-1))/(n*(n-1)) = 1 - 1/2 = 1/2 for all n

So MrFord is correct... but I require a lot more rigor than his intuition and so I've given it for others to see as well.

Curses, I came back to this and it has long been answered.

VICTORY!

I just attempted to explain it verbally instead of mathmatically I guess.

I got enough of equations and fluff at work, I like to use deductive logic over math sometimes. It pulls through some times

althought I thought my explination many posts up was pretty straight forward

Tertius - your explanation is needlessly complex.

But it is mathmatically correct none the less

it's like congress passing a bill about toilet paper. There doesn't need to be 200 pages on the topic and it takes too long, but it works eventually either way


Some people require the cold hard visual equations to see the proof

others simply can work through the basic theory in their head and deduce the outcome

nither way is generally more correct than the other

@Rockman, well of course calculating the actual probability brute force is going to be more computationally complicated, but it is a proof.

Besides, when I started writing that, your post was still at your second edit where you had decided that 50% was definitely wrong.

This is the first correct answer+reasoning I found (altho by seat "w" you mean the seat that you are assigned to Mr. Ford) (Twiztid did answer 1/2 first but I could not follow his reasoning). 1/2 is the answer. Rockman also has a very nice solution. Tertius, I believe also has a solution, but it looks to painful to read heh...

Should I post up some more math puzzles? This seemed to have generated some good interest. Perhaps next thread we can have people PM me solutions for the first 24 hours or so to give everybody a chance to do it on their own:)?

How bad could it be? lol

I would say that Rockman's solution posted at Dec 8th 2010, 3:23:49 might be easier to read than Ford's...

damnit ford sit in your own seat and we wouldnt have to go through this

True my first explanation was the most basic (and was correct), but it did not satisfy the requirement of proving that only one loop can be generated. I then decided that multiple loops could be generated, before realizing that my first thought was indeed correct that every displaced person could be traced back to the thieving Mr Ford.

I sit where I want!

Heh, it took me 2 reads before I fully understood Rockman's solution. It's briliant ;)

24 hours of pms sounds good to me.

Why did this take so long? It's a pretty basic formula:

n = Number of seats
p = Number of passengers
s = Likelihood of getting own seat

s = (n-p+1)/(n-p+2)

When n=p, s=0.5

-Fooglmog
Guy with no clue.

I don't see why its 50%. Lets say there's 5 seats and 5 people on the plane. Guy 5 is going to be the last guy to get on.

Mr. Ford gets on and has a 1/5 chance of sitting in guy 5's seat. But he sits in guy 2's seat who then has a 1/4 chance of sitting in guy 5's seat. Assuming it hasn't been sat in yet, next guy 1/3, next guy 1/2. But they add up since each guy that sits has a chance of sitting in guy 5's seat.

Oh, I see now that as soon as someone sits in Mr. Ford's seat its over and guy 5 gets his own seat. It still doesn't seem like its 50%.

Ford: 1/5 chance of last guys, 1/5 his own, 3/5 others.
Guy 2: 1/4 chance of last guys, 1/4 chance of Ford's, 1/2 chance others.
Guy 3: 1/3 chance of last guys, 1/3 chance of Ford's, 1/3 chance of guy 4.
Guy 4: 1/2 chance Ford, 1/2 chance guy 5.

But it could have ended if any of those guys sat in guy 5's seat... doesn't just depend on Guy 4.

what's with the C&O questions anyway. sheesh.. go arrange some tables and committees around the tables or something:P

Yeah, but my solution is filled with typos because I wrote it way too late at night :-(

The idea is there, but the grammar and spelling isn't.

You know here is my next issue with this damn problem.
Fordy just sit your ass in your seat and stop trying to bully everyone on the plane.

I already told you


I sit where I want!

fordie needs to sit down and eat his damn peanuts