Старушка в самолете

[Ian]

Я был почти уверен, что публиковал здесь эту задачу, но стал искать и не нашел. Излагаю по памяти.
В очереди на посадку n пассажиров, в самолете n мест, у каждого на руках билет на одно из этих n мест, и все билеты напечатаны правильно, все разные. Но где-то в очереди есть старушка, которая не может прочитать номер своего места, и в свою очередь сядет на любое из пока свободных. А каждый из остальных пассажиров сядет на свое место, и только если оно занято -на любое из пока свободных. Какова вероятность для произвольного из указанных пассажира Пети оказаться на своем месте?

[zykov]

У меня получается рекурентная формула для [math]P_n - искомой вероятности в зависимости от [math]n.
Для [math]n=2 будет [math]P_2=3/4. 50% - он сядет первым (на своё место), 50% - старушка сядет первой (тут у него шанс сесть на своё - 50%).
Далее для [math]P_n

1. С вероятность [math]1/n он садится первый (на своё).
2. С вероятностью [math](n-2)/n другой пассажир (не старушка) садится на своё. Тогда у него шанс [math]P_{n-1}.
3. С вероятностью [math]1/n старушка садится первой. Тут либо с вероятность [math]1/n она садится на своё, тогда он сядет на своё. Либо с вероятностью [math](n-1)/n она займёт чужое. В этом случае она либо займёт его место с вероятностью [math]1/(n-1) и тогда он на своё уже не сядет (вероятность 0). Либо с вероятностью [math](n-2)/(n-1) она сядет на место другого пассажира. Тогда далее этот другой пассажир будет играть роль старушки. В свою очередь он сядет на случайное место. Если сел на место старушки, то дальше он не мешает. Если нет, то он займёт чьё-то другое место и этот другой будет играть роль старушки.

Отсюда рекурентная формула: [math]P_n=\frac{1}{n}+\frac{n-2}{n}P_{n-1}+\frac{1}{n}(\frac{1}{n}+\frac{n-1}{n}(\frac{1}{n-1}0+\frac{n-2}{n-1}P_{n-1})).
Можно немного упростить: [math]P_n=\frac{1}{n}+\frac{1}{n^2}+\frac{n-2}{n}(1+\frac{1}{n})P_{n-1}=\frac{n+1}{n^2}(1+(n-2)P_{n-1}).
Как тут явную формулу получить - не вижу. Скорее всего её нет.
Ассимптотика на бесконечности примерно [math]1-\frac{-1.421+\ln n}{n}.

[zykov]

Если интересно, вот первые значения до [math]n=20:

P(2) = 0.75
P(3) = 0.777778
P(4) = 0.798611
P(5) = 0.815
P(6) = 0.828333
P(7) = 0.839456
P(8) = 0.848916
P(9) = 0.857088
P(10) = 0.864237
P(11) = 0.870559
P(12) = 0.876199
P(13) = 0.88127
P(14) = 0.88586
P(15) = 0.89004
P(16) = 0.893865
P(17) = 0.897383
P(18) = 0.900631
P(19) = 0.903641
P(20) = 0.906441

[peregoudov]

Да, я уже видел эту задачу, наверное, на старом форуме. Там ответ какой-то до безобразия простой.

[Ian]

zykov, спасибо!
Составил табличку значений
[math]P_n=1-\frac{n+1}{6n(n-1)}\left( 1+6\sum_{k=3}^n\frac{k-1}{k(k+1)}\right)
-и совпала с Вашей идеально.
Но что же все-таки с историей этой задачи...год назад где-то обсуждали...

[zykov]

Я не помню, чтобы я раньше видел эту задачу.
Наверно Вы на другом форуме её обсуждали.

[peregoudov]

Ну, не знаю, не знаю. Гугл на запрос "сумасшедшая старушка самолет" выдает кучу ссылок. По первой --- то самое простое решение. Следующая, правда, dxdy... Ссылки на старый форум не нашел. Но задачу я точно видел, вот только не помню, где.

P. S. Нашел, кажется!
http://www.sciteclibrary.ru/cgi-bin/yab ... 1196105188
http://www.sciteclibrary.ru/cgi-bin/yab ... 1041678070

[zykov]

Source of the post По первой --- то самое простое решение

Там условие другое.