If you happen to feel a little guilty about eating too much food, here’s a fun math problem to help you forget the guilt:

At the Thanksgiving family gathering, there are 12 people and 12 seats. The host has assigned each seat to a specific guest by writing their name on it. However, the great-uncle arrived first and, in a confused manner, randomly chose a seat to sit in. Subsequent guests look for their assigned seat first. If their assigned seat is empty, they sit there; if it is already occupied, they randomly choose another seat. The host sits last. What is the probability that the host ends up sitting in their own assigned seat?

This problem seems rather complicated at first glance. Suppose the great-uncle took X’s seat; then the choices for X and the remaining guests differ, and there are endless possibilities when X arrives. You might argue that the people who come before X do not matter, as they took their own seats as if they were never invited. However, since the great-uncle was already in a confused state, further argument would confuse him more.

Let us convert this calculation problem into a proof problem: the probability that the host ends up sitting in their own assigned seat is \(\frac{1}{2}\). To prove this, we use Complete (Strong) Mathematical Induction:

  • Verify the base case (\(n=n_0\)).
  • Assume the statement is true for all previous cases (\(n=k,k−1,k−2,…,n_0+1\)).
  • Use this stronger assumption to prove the statement is true for \(n = k + 1\).

Base Case (\(n = 3\))

Suppose there are 3 seats: one for the great-uncle, one for the host, and one for guest X. The great-uncle has three possible outcomes, tabulated below:

The great-uncle has three outcomes as tabulated below along with the possibilities for each choice:

outcome possibility of the outcome possibilitry of the host taking his own seat
Take host seat \(1\over3\) 0
Take his own seat \(1\over3\) 1
Take guest X’s seat \(1\over3\) \(1\over2\)

According to the Law of Total Probability, the total possibility of the host seating in his own seat is therefore:

\[{1\over3}\times0 + {1\over3}\times1 + {1\over3}\times{1\over2} = {1\over2}\]

Thus, the base case holds.

Inductive Step (\(n = k + 1\))

Now suppose there are \(n=k+1\) seats: one for the great-uncle, one for the host, and \(k-1\) for the remaining guests. The great-uncle’s possible outcomes are:

outcome possibility of the outcome possibilitry of the host taking his own seat
Take host seat \(1\over k+1\) 0
Take his own sear \(1\over k+1\) 1
Take any of the guests’ seat \(k-1\over k+1\) \(1\over2\)

When the great-uncle takes a guest’s seat, the confusion propagates. Before the displaced guest arrives, the other guests simply take their own seats and it does not affect the outcome. When the displaced guest does arrive, he becomes the new “confused great-uncle” if we treat the great-uncle’s seat as his own. This reduces the problem to \(i\) seats where \(i=k,k−1,k−2,…,3\).

Assuming the possibilitry of the host taking his own seat is \(P(i) = {1\over2}\), the total possibility \(P(k+1)\) is:

\[\begin{align*} P(k+1) &= {1\over k+1}\times0 + {1\over k+1}\times1 + {k-1\over k+1}\times P(i) \\ &= {1\over k+1} + {k-1\over k+1}\times{1\over2} \\ &= {1\over2} \end{align*}\]

Thus, the statement holds for \(n = k + 1\).

Conclusion

By complete induction, the probability that the host sits in their own assigned seat is \(\frac{1}{2}\) for any number of seats \(n \geq 2\). \(_\blacksquare\)

PS:

Actually, there’s no need to calculate this problem explicitly. First, the great-uncle’s seat and the host’s seat are fundamentally equivalent - either one can be occupied by the great-uncle or by the displaced guest. Second, before the host sits down, either the great-uncle’s seat is empty, or the host’s seat is empty, and these are the only two possibilities. A guest’s assigned seat won’t be empty, because each guest would sit in their assigned seat and wouldn’t choose to sit in either the great-uncle’s or the host’s seat.

Combining these two points, there is a 50% chance that the host’s seat will remain empty. The problem is interesting because it deliberately draws attention to the seating process, but in fact, the final result is independent of the process. The formula:

\[\frac{1}{n} + \frac{n-2}{n} \times \frac{1}{2} = \frac{1}{2}\]

is no coincidence - there is deep mathematical meaning behind it.