Whose Seat Am I In?

Spring 2020 ARML Power Contest

Note: in this problem there are two kinds of people, “absent-minded” and “clear-headed.”
To make it easier to keep them separated, absent-minded people will be referred to using
masculine pronouns and clear-headed people by feminine pronouns.

There are n people, numbered 1–n by the order in which they walk into the room.
They are to sit in n seats, also numbered 1–n. Person number 1 is supposed to sit in seat
number 1, person 2 in seat 2, and so on. That is, each person is assigned to sit in his or her
own particular seat. Of course, some of these people are absent-minded, and forget where
they are supposed to sit. These people instead sit in an empty seat at random (which might
be their own assigned seat), with equal probability for sitting in each empty seat. A person
who is not absent-minded will sit in her own seat unless someone else is already sitting there,
in which case she will choose a random unoccupied empty seat, with equal probability for
each seat.

One absent-minded person

To begin, explore the situation where there are n people, and only person 1 is absent-
minded.
If there are just n = 2 people, person 1 sits in his own seat half the time, while he sits in
seat 2 the other half of the time. There are two possibilities, and person n gets to sit in her
own seat with probability exactly 1/2.
Next, examine the possibilities when there are three people, and only person 1 is absent-
minded. The notation (a, b, c) will be used to mean that person a is sitting in seat 1,
person b in seat 2, and person c in seat 3. This will be called a seating arrangement or
simply arrangement for short, and similar notation will be used for more people sitting in
more seats. Note that the arrangements (1, 3, 2) and (2, 3, 1) are not possible with just one
absent-minded person, because person 1 did not sit in seat 2, so it was available for person 2
to sit in when she walked into the room. Not being absent-minded, she would have sat in her
own seat 2 so the middle number in the triple would have been 2, not 1 or 3. The remaining
possibilities are:

Person 1 Person 2 Person 3

with with
sits in then sits must sit Notation Probability
probability probability
seat in seat in seat
1 1/3 2 1 3 (1, 2, 3) 1/3
1 1/2 3 (2, 1, 3) 1/6
2 1/3
3 1/2 1 (3, 1, 2) 1/6
3 1/3 2 1 1 (3, 2, 1) 1/3
Notice that there are four possible seating arrangements, and person 3 gets to sit in her
own seat with probability 1/3 + 1/6 = 1/2. Also note that she can only sit in seats 1 or 3.

1
[4] Problem 1. Make a table like the one above for four people, with only the first person being
absent-minded. Hint: there should be eight possible seating arrangements, and amazingly
person 4 still has probability exactly 1/2 of sitting in her own seat. Feel free to turn the
paper sideways (“landscape mode”) so your table isn’t cramped on the page.

[1] Problem 2. In the four-person scenario, in which seats can person 4 sit?

When there were two people, there were 2 seating arrangements; with three people there
were 4 arrangements, and with four people there were 8 possible seating arrangements.
Person n ended up sitting in either her own seat or in seat 1, with probability 1/2 for each.
While it can be dangerous to generalize from just a few examples, the natural generalization
here turns out to be correct.

[2] Problem 3. For any n ≥ 2 and k with 2 ≤ k ≤ n, explain why person k can only end up
sitting in seat 1 or seat j with j ≥ k. In other words, person k cannot end up sitting in
seats 2 through k − 1. (In particular, person n can only end up sitting in seat 1 or her own
seat n.)

[2] Problem 4. For any n ≥ 2 and any k, 2 ≤ k ≤ n, choose any subset consisting of k of the n
people that includes person 1. Explain why there is exactly one possible seating arrangement
where each person in this set is in the wrong seat and each person not in this set is in the
correct seat.

[2] Problem 5. Prove that there are exactly 2n−1 possible seating arrangements.

[2] Problem 6. Prove that, for any n ≥ 2, the probability that person n sits in her own seat n
is 1/2.

Problem 7.
[1] (a) When n = 3, determine the probability that person 2 is in her correct seat.
[1] (b) When n = 4, determine the probability that person 3 in in her correct seat.
[1] (c) When n = 4, determine the probability that person 2 is in her correct seat.

The observations in this last problem also generalize:

[3] Problem 8. When there are n people, and only person 1 is absent-minded, show that the
n−k+1
probability that person k (k > 1) will end up sitting in her correct seat is .
n−k+2
Problem 9.
[1] (a) With n = 3, compute the probability that there are exactly s people sitting in their own
seats, where s is each integer from 0 up to 3.
[1] (b) Compute the expected value of the number of people sitting in their own seats when
n = 3.

2
 Problem 10.
[1] (a) With n = 4, compute the probability that there are exactly s people sitting in their own
seats, where s is each integer from 0 up to 4.
[1] (b) Compute the expected value of the number of people sitting in their own seats when
n = 4.

[3] Problem 11. Determine and prove a formula depending on n that computes the expected
value of the number of people sitting in their own seats for each given n.

Multiple absent-minded people

To continue, explore the situation where there are n people, and the first a of them are
all absent-minded, where a can be any integer between 1 and n. To receive credit for the
next three problems, work or explanations must be shown (you can check your answers with
the formulas in the problems that follow them).

Problem 12. Let n = 3 and a = 2.

[1] (a) Compute the number of possible seating arrangements.
[1] (b) Compute the probability that person 3 sits in her own seat.

Problem 13. Let n = 4 and a = 2.

[1] (a) Compute the number of possible seating arrangements.
[1] (b) Compute the probability that person 3 sits in her own seat.
[1] (c) Compute the probability that person 4 sits in her own seat.

Problem 14.
[1] (a) Compute the number of possible seating arrangements for n = 5 and a = 2.
[1] (b) Compute the number of possible seating arrangements for n = 5 and a = 3.

These patterns persist as well:

[1] Problem 15. Given that k > a, show that person k can only sit in seats with numbers
either at least k or at most a.

Problem 16.
1
[1] (a) Prove that person n will sit in her own seat with probability .
a+1
n−k+1
[2] (b) Prove that person k (with k > a) will sit in her own seat with probability .
n−k+a+1
[3] Problem 17. Prove that with n people, the first a of whom are absent-minded, there are
a!(a + 1)n−a possible seating arrangements.