The probability of getting my seat

[BMAD]

Balcony seating at the opera is by ticket only, and all the tickets are sold and all the ticketholders are in line to enter. But it turns out that the first person through the door is rather inebriated by the time the hall is open for seating and, instead of taking the properly assigned seat, chooses a chair at random (presumably the one with the lowest-seeming relative velocity to his or her person). The next people come in one at a time—and if their seat is available, they take it. But if someone is already sitting there, rather than disrupt things, they just pick some other random seat. Which raises the question, "what is the probability that the last opera lover ends up in his or her assigned seat?"

[bonanova]

p = 1/2.

Edit: here is an analysis that I think works.

Call the first (inebriated) to enter F.

Call the last to enter L.

It does not matter how many seats there are.

F chooses a seat at random.

If F chooses F's seat, then everyone, including L, gets his own seat.

If F chooses L's seat, then L does not end up in his own seat.

These outcomes have equal likelihood.

If F chooses a seat other than of F or L, say of Q.

Every passenger after F until Q gets his own seat, and Q must choose a seat.

If Q picks F's seat, everyone, including L, gets his own seat.

If Q picks L's seat, then L does not end up in his seat.

These outcomes have equal likelihood.

If Q chooses a seat other than of F or L, say of R,

Every passenger after Q until R gets his own seat, and R must choose a seat.

If R picks F's seat, everyone, including L, gets his own seat.

If R picks L's seat, then L does not end up in his seat.

These outcomes have equal likelihood.

And so it goes until L enters the plane.

With equal likelihood, he finds his seat empty or taken.

Edited July 14, 2013 by bonanova
Analysis added

[DeGe]

If any displaced person takes the seat of the first person, all the following persons take their respective seats.

Let us define any displaced person taking the first person's seat as "closing the loop".

So, if the first person takes his own seat, he closes the loop and everyone gets their own assigned seats

Now, lets define combinations to see how many persons other than the first person are needed to close the loop

If one person is needed to close the loop, it means that the first person sits on his assigned seat

If two are needed to close the loop, it means that the first person takes the seat of xth person in the line and the xth person takes the first person's seat; the rest sit as assigned

If three are needed to close the loop, it means for example that the first person takes the seat of 5th person, the 5th person takes the seat of 8th person and the 8th person takes the seat of 1st person. The rest sit as assigned

And so on

(Note that two persons needed could also mean that first person takes seat of the last; all others sit as assigned and the last person must take the seat of the first)

Therefore,

Persons needed Combinations possible

1 n-1C0 (only the first person closes the loop)

2 n-1C1 (first person + any one other closes the loop (could be the last person also))

3 n-1C2 ...

n-1 n-1Cn-2 (the person before last closes the loop)

n n-1Cn-1 (the last person closes the loop)

So, the possible ways of seating arrangement are:

n-1C0 + n-1C1 + n-1C2 + … n-1Cn-1

n-1 everywhere because the first person is already chosen by default; we are looking at how many others are needed

n-1Cn-1 would mean that the 1st person takes the seat of 2nd, he takes seat of 3rd, he takes seat of 4th…..last before one takes the seat of last, and the last person has to take the seat of the first person

Sum of this combinations is = 2^(n-1)

So, all the people can sit in 2^(n-1) ways

Out of this, there are n-1 combinations where the last person's seat is taken before he enters

(except in the case of n-1C0, there is always 1 case where the last person's seat is already taken)

So, the probability of last person NOT getting his assigned seat is:

n-1 / 2^(n-1)

The probability of getting the assigned seat is then:

1 - [n-1 / 2^(n-1)]

[bonanova]

Does person N get his assigned seat?

For each of the first N-1 persons:

1. If he takes Person 1's seat,the answer is Yes.
2. If he takes Person N's seat, the answer is No.

It's all about those two seats.

They have exactly the same probability of being chosen.

[DeGe]

If any displaced person takes the seat of the first person, all the following persons take their respective seats.

Let us define any displaced person taking the first person's seat as "closing the loop".

So, if the first person takes his own seat, he closes the loop and everyone gets their own assigned seats

Now, lets define combinations to see how many persons other than the first person are needed to close the loop

If one person is needed to close the loop, it means that the first person sits on his assigned seat

If two are needed to close the loop, it means that the first person takes the seat of xth person in the line and the xth person takes the first person's seat; the rest sit as assigned

If three are needed to close the loop, it means for example that the first person takes the seat of 5th person, the 5th person takes the seat of 8th person and the 8th person takes the seat of 1st person. The rest sit as assigned

And so on

(Note that two persons needed could also mean that first person takes seat of the last; all others sit as assigned and the last person must take the seat of the first)

Therefore,

Persons needed Combinations possible

1 n-1C0 (only the first person closes the loop)

2 n-1C1 (first person + any one other closes the loop (could be the last person also))

3 n-1C2 ...

n-1 n-1Cn-2 (the person before last closes the loop)

n n-1Cn-1 (the last person closes the loop)

So, the possible ways of seating arrangement are:

n-1C0 + n-1C1 + n-1C2 + … n-1Cn-1

n-1 everywhere because the first person is already chosen by default; we are looking at how many others are needed

n-1Cn-1 would mean that the 1st person takes the seat of 2nd, he takes seat of 3rd, he takes seat of 4th…..last before one takes the seat of last, and the last person has to take the seat of the first person

Sum of this combinations is = 2^(n-1)

So, all the people can sit in 2^(n-1) ways

Out of this, there are n-1 combinations where the last person's seat is taken before he enters

(except in the case of n-1C0, there is always 1 case where the last person's seat is already taken)

So, the probability of last person NOT getting his assigned seat is:

n-1 / 2^(n-1)

The probability of getting the assigned seat is then:

1 - [n-1 / 2^(n-1)]

Bonanova is right. In the above solution, the number of cases where the last person does not get his seta is much higher than n-1. It is actually 2^(n-2) considering all possibilities where the "loop is closed" with n-2 persons instead of n-1 so that the last person's seat is always available.

The probability will then be as suggested by Bonanova.

[bonanova]

Kudos to DeGe.

I started a recursive / summation approach, and ran quickly out of steam

(read: lacked ability to think through to conclusion.)

If you're familiar with the problem (a classic that I shared a while back),

when I was first asked about it, I ran away from the calculus and made the assumption that

gave the answer immediately. And I impressed the female colleague who posed it to me.

I looked for the easy way out here as well.