Random passengers

[bonanova]

Al and Bert are among 100 passengers assigned to one hundred seats on an airplane. Al was first to board, and Bert was last. Strangely, the first 99 passengers ignored their boarding passes and took random unoccupied seats. Bert liked the seat he was assigned and is not happy with the situation. If he's lucky, his seat is unoccupied and there's no problem. Otherwise, he insists the passenger erroneously occupying it move to his own assigned seat. The displaced passenger must then move, possibly displacing another person. This process continues until all passengers are seated.

What is the probability that Al must move?

[Molly Mae]

A start:

Less than 99%.  My first instinct is that Al only has a 1% chance of randomly choosing his assigned seat (and that's true).  But Al doesn't have to move if the current person displacing another passenger finds their assigned seat empty.

My intuition now says that the chance Al has to move is actually rather low (probably below 5%).  Basically, Al has to be in either (a) his assigned seat, or (b) a closed loop of passengers who have each others' seats.  I can't even think of how to go about solving that mathematically.

[flamebirde]

Spoiler

So the order goes Al --> 98 people --> Bert, I assume (100 people total).

The probability that Al has to move is the probability that *every single person* is sitting in a seat that is not theirs nor any of the previous passengers' seats, since Al is the first passenger to board. So Al has a 99/100 chance to choose a wrong seat. The next person, passenger 2, has a 97/99 chance to choose a wrong seat (Al's already sitting in a seat, and if the passenger sits in his own seat or in Al's actual seat the loop completes and Al won't have to move). But the next person, passenger 3, doesn't have a 95/98 chance... so that way seems like a dead end to me.

The other option would be to see how many closed loops generally form. That would give us an idea of how likely it is.

Another observation: If Al is only in loop with one other person, then there's a 2/100 chance that he has to move. If he's in loop with two other people, then there's a 3/100 chance that he has to move. So, his chances of being forced to move depends directly on how large his closed loop is.

 

[bonanova]

One approach, among several, is to

Spoiler

consider the conditions under which a given number of passengers move

and

Spoiler

whether it matters that Al was first to board.

 

[Molly Mae]

Ah.

The odds of Al moving seem to be 50%.  If we test it against a smaller number of passengers, we can see how often these closed loops form and how often Al is in his own assigned seat.  It seems as the likelihood of the latter decreases, the likelihood of the former increases appropriately.  

Here I have the layout for 3 and 4 passengers.  1 is Al and the last number is Bert (3 for 3 passengers, 4 for 4 passengers).  Any time 3 can take the third spot, Al stays put.  Any time Al is already in his assigned seat, Al can stay put.  Any time the displaced person finds their seat, Al can stay put.  Al staying put is denoted with a 'y'.  Al moving gets an 'n'.

Al stays put 3/6 times with 3 Passengers:
123 - y
132 - y
213 - y
231 - n
312 - n
321 - n

Al stays put 12/24 times with 4 passengers:
1234 - y
1243 - y
1324 - y
1342 - y
1423 - y
1432 - y
2134 - y
2143 - y
2314 - y
2341 - n
2413 - n
2431 - n
3124 - y
3142 - n
3214 - y
3241 - n
3412 - y
3421 - n
4123 - n
4132 - n
4213 - n
4231 - n
4312 - n
4321 - n

[Kay_kay]

Interesting one..

Spoiler

The probability that Al will have to move is 1/100. 

Essentially, Al will have to move only if he sat in Bert's seat in the first place. In all other situations, the sequence of seat changes will stop as soon as someone occupies the empty seat. 

 

[CaptainEd]

Kay_Kay, I don’t follow the argument.

Suppose Bert was assigned 100, Charlie (assigned 90) is in 100, Dog (80) is in 90, Al(70) is in 80. Ernest(60) is in 70. Seat 60 is the only empty seat. 

Al is not sitting in Bert’s assigned seat. But he is in a cycle with Bert and the empty seat. 

So I guess we want to know the expected size of a cycle.

[Kay_kay]

On 4/3/2018 at 1:02 AM, CaptainEd said:

Kay_Kay, I don’t follow the argument.

 

  Reveal hidden contents

 

Suppose Bert was assigned 100, Charlie (assigned 90) is in 100, Dog (80) is in 90, Al(70) is in 80. Ernest(60) is in 70. Seat 60 is the only empty seat. 

Al is not sitting in Bert’s assigned seat. But he is in a cycle with Bert and the empty seat. 

So I guess we want to know the expected size of a cycle.

 

 

My bad .. I did not consider all scenarios. Let me work on this some more ..

[bonanova]

On 4/2/2018 at 2:17 AM, Molly Mae said:

Ah.

  Hide contents

The odds of Al moving seem to be 50%.  If we test it against a smaller number of passengers, we can see how often these closed loops form and how often Al is in his own assigned seat.  It seems as the likelihood of the latter decreases, the likelihood of the former increases appropriately.  

Here I have the layout for 3 and 4 passengers.  1 is Al and the last number is Bert (3 for 3 passengers, 4 for 4 passengers).  Any time 3 can take the third spot, Al stays put.  Any time Al is already in his assigned seat, Al can stay put.  Any time the displaced person finds their seat, Al can stay put.  Al staying put is denoted with a 'y'.  Al moving gets an 'n'.

Al stays put 3/6 times with 3 Passengers:
123 - y
132 - y
213 - y
231 - n
312 - n
321 - n

Al stays put 12/24 times with 4 passengers:
1234 - y
1243 - y
1324 - y
1342 - y
1423 - y
1432 - y
2134 - y
2143 - y
2314 - y
2341 - n
2413 - n
2431 - n
3124 - y
3142 - n
3214 - y
3241 - n
3412 - y
3421 - n
4123 - n
4132 - n
4213 - n
4231 - n
4312 - n
4321 - n

 

These cases are the ones I calculated as well, and led me to the right conclusion. (I had to solve it as it's not mine originally and I did not receive the solution.) It took a little insight to get me thinking along productive lines. See the spoilers in my April 1 post - btw not an April Fools post - to get there.

[Molly Mae]

On 4/1/2018 at 4:53 AM, bonanova said:

One approach, among several, is to

  Hide contents

consider the conditions under which a given number of passengers move

and

  Hide contents

whether it matters that Al was first to board.

 

Given that the first 99 board randomly, it doesn't matter when Al boards, as long as he does so before Bert.  He's just as likely to get any one seat if he boards 1st as he is 99th (that is, the possible arrangements of passengers remains the same, regardless of when they board).

[bonanova]

Clue.

Spoiler

What is the probability that an arbitrary passenger must move? What does that imply?

 

[plasmid]

Spoiler

When Al gets on the plane, he will do one of three things: (1) he will sit in his own seat, (2) he will sit in Bert's seat, or (3) he will sit in someone else's seat. The odds that he will sit in his own seat (and be guaranteed to not have to move) or in Bert's seat (and be guaranteed to have to move) are equal.

If Al sits in someone else's seat, call that someone else Charlie. Al will have to move if and only if Charlie has to move and claim his assigned seat which Al took. And Charlie will either (1) sit in Al's seat so Al won't have to move, (2) sit in Bert's seat so Al will have to move (note that the odds of picking Al's seat or Bert's seat are again equal), or (3) sit in someone else's seat so that Al and Charlie will both have to move if and only if that someone else has to claim their seat which Charlie took.

This keeps repeating until someone sits in Al's seat (so Al doesn't have to move) or sits in Bert's seat (so Al has to move), and at each step in the process the person who's taking a seat has equal probability of choosing Al's seat or choosing Bert's seat. So the odds that Al has to move are 50/50.

 

[CaptainEd]

Please disregard this post. I now understand that 50/50 does not mean probability 1.

Edited April 15, 2018 by CaptainEd
Brain freeze— I forgot that 50/50 means 1/2.

[bonanova]

8 hours ago, plasmid said:

  Hide contents

When Al gets on the plane, he will do one of three things: (1) he will sit in his own seat, (2) he will sit in Bert's seat, or (3) he will sit in someone else's seat. The odds that he will sit in his own seat (and be guaranteed to not have to move) or in Bert's seat (and be guaranteed to have to move) are equal.

If Al sits in someone else's seat, call that someone else Charlie. Al will have to move if and only if Charlie has to move and claim his assigned seat which Al took. And Charlie will either (1) sit in Al's seat so Al won't have to move, (2) sit in Bert's seat so Al will have to move (note that the odds of picking Al's seat or Bert's seat are again equal), or (3) sit in someone else's seat so that Al and Charlie will both have to move if and only if that someone else has to claim their seat which Charlie took.

This keeps repeating until someone sits in Al's seat (so Al doesn't have to move) or sits in Bert's seat (so Al has to move), and at each step in the process the person who's taking a seat has equal probability of choosing Al's seat or choosing Bert's seat. So the odds that Al has to move are 50/50.

 

Nice.

One thing I liked about this puzzle is that it's open to clear thinking. Even tho at first it seems too complex.

[bonanova]

This was my take.

Spoiler

Bert enters a plane with a random empty seat. Chances are 1/100 that it's his, when no one has to move. Else, chances are 1/99 the empty seat belongs to the guy in Bert's seat, so probability that 1 passenger moves is (99/100) (1/99). Surprise!!! That's also 1/100. Chances that two passengers move is (99/100)(98/99)(1/98) = OMG also 1/100. And so on.

What does that mean? There are 100 equally likely cases (1/100 for each) that { 0 1 2 3 4 ... 48 49, 50 51 ... 97 98 99 } passengers have to move. The 99 candidate passengers who move, or not, are indistinguishable (being first to board does not make Al special in any way.) The chances that any passenger will be asked to move varies uniformly from 0/99 to 99/99, with expected value of 49.5/99 = 50%.

Al is one of those passengers.