Theater sitting arrangement

[Nsof]

From a friend

100 people, numbered 1 to 100, are waiting in line to sit in the theater. The theater has 100 seats also numbered 1 to 100.
The people sit one after the other according to the following rules:
1) Person number 1 randomly chooses one of the seats with equal probability and sits there.
2) Each person after that sits in the chair that equals his/her number unless it is already taken. If that happens s/he randomly choose one of the available seats with equal probability and sits there.

What is the probability that person 100 sits in seat 100?
--edit: fixed some spelling errors
_________________
Will sell this place for beer

[Zag]

I have to admit that I've seen a puzzle like this before, but I figured it out when I first saw it, so I feel justified in claiming this one.

The answer is exactly 50%.

Explanation:

Ignore the 100, let's just say that there are N seats, where N > 1

Person 1 chooses his seat randomly. He might choose
Seat 1: 1/N
Seat 100: 1/N
Some other seat (N-2)/N

The chances of the first two are equal, and, if either is chosen, completely determine the final answer. That is, if the random person accidentally chooses his own seat, Mr. 100 will end up with his own seat. And if random person chooses seat #100, then Mr. 100 obviously will not get it. So, so far, we have equal chance of success or failure.

If Mr. Random chooses some other seat, then nothing matters until we get to the person whose seat he chose, because everyone up until that point will be taking his assigned seat. At this point, we are back to the original problem -- there are N ₁ seats left, and a person is choosing randomly from amongst the available seats. He might choose
Seat 1: 1/N ₁
Seat 100: 1/N ₁
Some other seat (N ₁ -2)/N ₁

Etc.

[MatthewV]

[50% of the time

I thought about an easier problem-- a theater with just 5 seats and the same setup and then expanded the process.
So if Dude1 sits in seat number...

5, then there is a 0 chance D5 will be in 5.

4, then seats 2,3,4 are full. D4 will sit randomly in 1 or 5 (0.5 chance of D5 in 5)

3, then seats 2,3 are full. D3 will sit randomly in 1,4,5. If 1, D5 will be in 5. If 4, then D4 will sit randomly in 1 or 5. if 5, D5 will not sit in 5. So... what 1/3 of the time, D5 will be in 5, 1/3 we get a 0.5 from D4 next, and 1/3 we get D5 not in 5. But this all sums to a 0.5 chance D5 ends up in 5.

2, then seat 2 if full. And D2 will make us go 1/4 of the time to seat 1 (D5 will sit in 5), seat 3 (see above, 0.5 success), seat 4 (see above, 0.5 success), seat 5 (no success). This still goes to 0.5

1, then everyone will sit in their seat, D5 will be in 5.]

From my understanding, this could expand to 100 seats. My friends always hate the way I deal with situations of probability; I am posting partly because I would like to see if/where my logic is flawed.

[MatthewV]

See--- I hate trying to figure out math in terms of math. And it took took long to type apparently!

[Lepton*]

50% - either he does or he doesn't

[Nsof]

I found the same solution Zag found. My friend had another solution:

1) He split the sample space (all the legal seatings of the people) into two sets:
Set 1 contains all sample cases where person 100 does not sit in chair 100.
Set 2 contains all sample cases where person 100 sits in chair 100. (This set represents the event 'person 100 sat in chair 100'. We are interested in finding the probability of this event.)

I would expect that the order of Set 1 should be much larger than that of Set 2 because if we look at all possible permutations of 1,…,100 there are 99 times more permutation where 100 is not at the end (of which Set 1 is composed) compared to where 100 is in the end (of which Set 2 is composed).

While not all permutations are legal i expected the ratio to remain. But
2) He then showed a bijection between the two sets such that the bijection pairs cases that have the same probability.
This meant that the two sets have the same probability of occurring and so the answer is 0.5.

The explanation for why the Sets are the same size comes from the following claim: If person 100 is not in chair 100 then he must be in chair 1.

To see that, the following must be shown (all require more rigorous proof)
Lemma: if its person N's turn to sit and her/his chair is taken then all people 1,...,N-1 are sitting in chairs 2,...,N
Corollary 1: if its person N's turn to sit and her/his chair is taken then chair 1 is available
Corollary 2: if its person N's turn to sit and s/he chooses to sit in chair 1 then everyone after person N will be sitting in their place.
Corollary 3: If someone other than person 100 is in chair 1 then person 100 must be sitting in chair 100.
Corollary 4: If person 100 is not in chair 100 then he must be in chair 1.

The Bijection
Let's look at a sample case s from Set 1 (where person 100 does not sit in chair 100).
By corollary 4, person 100 sits in chair 1, so s looks something like
s = (100, s2, s3,…,s99, s100)
We'll define f(s)=r=(s100, s2, s3,…,s99, 100)
f switches between person 100 and the person sitting in chair 100

Claim 1: f is a bijection
Claim 2: Prob(s) = Prob(r)
Again both need to be explained further.

obviously not as elegant as Leptons
_________________
Will sell this place for beer

[Zag]

[groza528]

[Antrax]

I'm confused. Why can't #2 sit in seat #1, for instance? In the rules it says that if your seat is occupied, you choose randomly from what's available. So if #1 sits in seat #2, person #2 has a 1/99 chance of sitting in seat #1. No?
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[groza528]

2 can sit in #1. I said they cannot choose a lower-numbered seat *except* #1. If 2 is in #1 then 100 will be in #100.

[Quailman]

[Nsof]

[lexprod]

[Zag]

Ummm. right. I wrote that while I was in a meeting, and I wasn't thinking correctly. I agree that person 100 can only end up in his own seat or seat #1. (It's a scientific fact that being in a meeting will make you stupider.)

[lostdummy]

Actually, above solution presume that people try to seat in exact order, from 1 to 100. While it can be assumed from posted problem, it is not explicitly stated - only thing that is explicitly stated is that person #1 will enter first to choose seat.

I guess it would make slightly harder problem to solve if we ask for probability of person #100 to sit in his seat if entrance order is also random (except from person #1).

[ralphmerridew]

The solution only requires that person #100 be the last person to enter. (Just number the people by the order in which they enter; their seats can be scattered all around the auditorium.)

[lostdummy]

Well, the (same) result only require that person #100 be the last person, but it seems like some of above solutions assumed ordered entrance of other people - for example, statement that "Person X may not select a lower-numbered seat other than #1 " may require ordered entrance.

Anyway, it would be interesting to see what would be solution for case where person #100 can randomly enter (ie only #1 is fixed as first to enter).

Alternative question without changing how they enter would be:
what is chance for n-th person ( n = 2..100) to sit in his seat ?

[groza528]

[lostdummy]

Well, my initial remark still stays - problem does not explicitly state order of entrance, and thus it does not require person #100 to enter last.

And if person #100 have random position in entrance order, solution is not same. I have result value from simulation, and it is noticeably different (around 95% chance to sit in his chair). Would be interesting to see math solution on that one ;p

[ralphmerridew]

I think that, with N people, the chance that person #k (k>1) sits in his own seat is (N+1-k)/(N+2-k).

Intuitive explanation:
Consider the seats 1, k, k+1, ... N. (Total of N+2-k.) Of those, exactly one will be occupied when person #k is about to sit. If that seat is #k (prob. 1/(N+2-k)), then person #k won't get his seat; otherwise (prob. (N+1-k)/(N+2-k)), he will.

Anybody care to make that rigorous?

[ralphmerridew]

Also, prob. that a randomly chosen not-1 person will sit in his correct seat:

If my previous answer is correct, prob. is:
P = sum (k = 2 to N : Prob (he is #k) * Prob (#k gets own seat)
= (1/(N-1)) * sum (k = 2 to N : Prob #k gets own seat)
= (1/(N-1)) * sum (k = 2 to N : (N+1-k)/(N+2-k))
= (1/(N-1)) * (sum (k = 2 to N : 1 - 1/(N+2-k)))
= (1/(N-1)) * (N-1 - sum (k = 2 to N : 1/(N+2-k)))
= (1/(N-1)) * (N-1 - (1/N + 1/(N-1) + 1/(N-2) + ... + 1/2))
= (1/(N-1)) * (N - (1/N + 1/(N-1) + ... + 1/2 + 1))
= (1/(N-1)) * (N - H_n)
= (N - H_N) / (N - 1)
~= (N - ln N + y) / (N - 1)
where y is Euler's constant (~= .57).

[lostdummy]

Nice - it has same result as my simulation (95.8%) , so it looks like good solution.

That (N+1-k)/(N+2-k) part is quite simple and elegant and it solve also original #100 problem. Only thing that could be questionable is if chance of free seat at 1,k,k+1...N is really same for every seat. But result number suggest that is is ;p

[ralphmerridew]

Everybody from person 1 through person k-1 treats seats 1, k, k+1, ... N identically, so the chance that each is occupied before person k's turn must be equal.