Сумасшедший пассажир

Идёт посадка пассажиров в 100-местный самолёт. У каждого пассажира есть билет, в котором указано его место, и все места проданы (но, конечно, без овербукинга). Однако первый же зашедший в салон пассажир выбрал себе случайным образом одно из 100 мест и разместился на нём.

Следующие 99 пассажиров поступают следующим образом: если место, указанное в билете, свободно, пассажир садится на него. В противном случае (т.е. если назначенное ему место уже занято) пассажир садится на любое из свободных мест случайным образом.

Какова вероятность того, что последний (сотый) пассажир окажется на своём месте?

Решение
Для начала посмотрим, как искомая вероятность зависит от числа участников в задачах меньшей размерности. Обозначим через $P(n)$ вероятность того, что последний человек окажется на своём месте для случая, когда в самолёте $n$ мест.

Построив на бумажке дерево исходов, получим, что:
$P(1) = 1$
$P(2) = 1/2$
$P(3) = 1/2$
$P(4) = 1/2$

Видно, что $P(n)=1/2$ при $n>1$. Докажем это методом математической индукции.

Не ограничивая общности рассуждений, будем считать, что номер назначенного пассажиру места равен номеру пассажира в очереди. Т.е. у первого пассажира в билете указано место номер 1, у второго - место номер 2 и так далее.

Для $n=2$ утверждение верно. В самом деле, с вероятностью $1/2$ первый пассажир либо займёт свое место, либо сядет на место последнего (второго) пассажира.

Рассмотрим теперь задачу произвольной размерности $n$.

Пусть первый пассажир расположился на месте под номером $k$.

Если $k=1$ (вероятность этого события равна, очевидно, $1/n$), то все пассажиры, включая последнего, рассядутся по своим местам с вероятностью $1$.

Если $k=n$ (вероятность этого события также равна $1/n$), то последний пассажир уже точно не окажется на своём месте.

Предположим теперь, что первый пассажир занял место $1<k<n$ (вероятность этого равна $1-2/n$). В этом случае пассажиры со второго по $(k-1)$-й сядут на свои места. А вот пассажир под номером $k$ будет вынужден выбирать себе одно из свободных мест, потому что его место уже занято. Он может сесть либо на первое место, либо на одно из мест с $k+1$ по $n$, то есть всего ему будет доступно $n-k+1$ мест.

Можно заметить, что поведение $k$-го пассажира ничем не отличается от поведения первого пассажира в задаче размерности $n-k+1$. Если $k$-й пассажир сядет на первое место, то все остальные рассядутся по местам. Если же он выберет одно из мест $k+1..n$, то он станет тем самым сумасшедшим первым пассажиром по отношению к оставшимся в очереди.

Поскольку $1<k<n$, то $1<n-k+1<n$, и для этой размерности справедливо предположение математической индукции: вероятность того, что последний пассажир займёт свое место, равна $1/2$.

Мы рассмотрели три возможных варианта:
1) Если первый пассажир займёт место под номером 1 (вероятность этого равна $1/n$), то последний пассажир окажется на своём месте с вероятностью $1$
2) Если первый пассажир сядет на место под номером $1<k<n$ (вероятность $1-2/n$), то последний пассажир займёт свое место с вероятностью $1/2$
3) Если первый пассажир сразу сядет на последнее место (вероятность $1/n$), то последний пассажир займёт своё место с вероятностью $0$.

По формуле полной вероятности,$$P(n) = 1*\frac{1}{n} + \frac{1}{2}*\left(1 - \frac{2}{n}\right) + 0*\frac{1}{n} = \frac{1}{2}$$Доказательство методом математической индукции закончено.

Таким образом, вероятность того, что последний пассажир сядет на своё место, равна $1/2$: либо сядет, либо не сядет.