Решение задачи 110

Решим общую задачу: пусть людей в очереди n. Пронумеруем людей в очереди: у старушки номер 1, у последнего человека -- n. Также пронумеруем места от 1 до n. Для удобства будем считать, что человеку с номером k нужно сесть на место с номером k (кроме старушки, у нее нет определенного места).

Если старушка села на первое место, то второй пассажир сядет на свое второе место, третий - на свое третье и так далее.

Если же старушка сядет на второе место, то мы свели задачу к такой же для n-1 человека. Действительно, место второго занято, поэтому он сядет на случайное из оставшихся n-1 мест (как будто бы он сумасшедшая старушка), а места остальных пассажиров до входа второго свободны.

Пусть теперь старушка села на третье место. Тогда второй пассажир сядет на свое законное второе место. Опять же можно заметить, что мы свели задачу к такой же для n-2 пассажиров (в очереди n-2 человека, первый входящий садится на случайное место).

Аналогично можно рассуждать и для места с номером k. Пусть старушка села на k-ое место. Тогда второй пассажир сядет на второе, третий -- на третье, .., (k-1)ый на (k-1)ое, и в очереди останутся n-k+1 пассажиров, у одного из них (первый кто заходит) место занято, у остальных нет. Это в точности та же задача для n-k+1 пассажиров. Если старушка села на место с номером n-1, то задача свелась к такой же для двух людей. Осталось вспомнить теорию вероятностей и все это посчитать.

Пусть p_k -- вероятность последнему пассажиру сесть на свое место, если в очереди k человек. Заметим, что p_2 = 1/2. Действительно, старушка садится на первое место с вероятностью 1/2, и в этом случае второй пассажир сядет на свое место. Пусть теперь в очереди n человек. Старушка сядет на первое место с вероятностью 1/n. Тогда последний человек в очереди сядет на свое место с вероятностью 1. На второе место старушка так же сядет с вероятностью 1/n, а последний человек сядет на свое место в этом случае с вероятностью p_(n-1) по написанным выше соображениям. Получается, вероятность того, что старушка села на второе место и последний человек сел на свое -- 1/n*p_(n-1). Аналогично, вероятность того, что старушка села на k-ое место и последний человек сел на свое -- 1/n*p_(n-k). Если же старушка садится на последнее место, то вероятность крайнего человек в очереди попасть на свое место равна 0. В итоге получаем: p_n = 1/n+1/n*p_(n-1)+...+1/n*p_2 = 1/n(1+p_(n-1)+..+p_2).

Покажем, что p_n равно 1/2 по индукции. То, что p_2 = 1/2 мы уже показали. Пусть теперь все p_2, p_3,.., p_(n-1) равны 1/2. Тогда p_n = 1/n(1+1/2+..1/2) = 1/n(1+(n-2)/2) = 1/n * (n/2) = 1/2.

Ответ: 1/2 (для любого числа человек в очереди, большего единицы).