Решение. Сумасшедшая старушка (#144)
Замечание (*). Последний пассажир сядет либо на своё место, либо на место старушки.
Действительно, если предположить, что найдётся рассадка, при которой это не так, то пассажир X, на место которого сядет последний пассажир, сам окажется не на своём месте, но по условию задачи такое возможно только в том случае, когда место пассажира X займут до него. Противоречие.
Старушка и последний пассажир рассаживаются, не глядя в свой посадочный талон: старушка – потому что сумасшедшая, а последний пассажир – потому что не остаётся выбора. С учётом также замечания (*), если старушка и последний пассажир поменяются посадочными талонами, то вероятность рассадки не изменится, но благоприятный исход для последнего пассажира сменится неблагоприятным. Следовательно, исходы равновероятны и равны 0,5.
Обозначим X₁, …, Xₙ – случайные величины, соответствующие номеру занятого места пассажирами 1, …, n соответственно. По условию, X₁ – это место, занятое старушкой. Также без ограничения общности положим, что k-му пассажиру назначено место k.
Если старушка занимает своё место, то все пассажиры также рассаживаются по своим местам. Если же старушка занимает место k-го пассажира (k > 1), то все предыдущие пассажиры (за исключением старушки) занимают свои места. Таким образом,
Заметим, что условные веротяности в выражении выше соответствуют исходной задаче, но с n - k + 1 пассажирами, в которой уже k-й пассажир играет роль старушки. Поэтому равенство продолжается, формируя рекуррентное соотношение
Найдём pₙ из полученного рекуррентного соотношения
Докажем по индукции, что pₙ = 0,5.
База индукции. Очевидно, что p₂ = 0,5, поэтому при n = 2 соотношение верно.
Шаг индукции. Пусть pₖ = 0,5 при 1 < k ≤ n-1. Тогда из рекуррентного соотношения выше легко получаем pₙ = (1 + 0,5 (n - 2))/n = 0,5
Обозначим искомую вероятность через 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.