Решение. Сумасшедшая старушка (#144)
Рассмотрим ситуацию, когда первыми в очереди стоят k сумасшедших старушек, k<n. Назовём места старушек и последнего пассажира бизнес-классом. Основным является следующее утверждение:
(*) при любой рассадке последний пассажир займёт место в бизнес-классе.
Предположим, что это не так. Тогда пассажир X, на месте которого будет сидеть последний пассажир, сам окажется не на своём месте, но по правилам рассадки такое возможно только в том случае, когда место пассажира X займут до него. Следовательно, последний пассажир должен быть до пассажира X. Противоречие.
Теперь заметим, что старушки и последний пассажир могут выкинуть свои посадочные талоны, при этом на правила рассадки это никак не повлияет. Следовательно, все места в бизнес-классе для последнего пассажира равнозначны, и вероятность последним пассажиром занять своё место в бизнес-классе равна 1/(k+1). При k=1 получаем ответ 1/2.
Обозначим искомую вероятность через f(n). Докажем по индукции, что f(n)=0,5.
База индукции. Очевидно, что f(2)=0,5.
Шаг индукции. Предположим, что f(k)=0,5 при k≤n. Найдём f(n+1).
(А) С вероятностью 1/(n+1) старушка сядет на своё место, поэтому в силу (*) при этом условии последний пассажир займёт своё место с вероятностью 1.
(Б) С вероятностью 1/(n+1) старушка сядет на место последнего пассажира, поэтому в силу (*) при этом условии последний пассажир займёт своё место с вероятностью 0.
(В) С вероятностью (n-1)/(n+1) старушка займёт оставшиеся места, поэтому в силу предположения индукции последний пассажир при этом условии займёт своё место с вероятностью 1/2.
Следовательно, по формуле полной вероятности
f(n+1) = 1/(n+1)∙1 + 1/(n+1)∙0 + (n-1)/(n+1)∙1/2 = 1/2