задача про сумасшедшую старушку, теорвер, рекурсивно

[mospehraict]

Добрый день,

посмотрите, пожалуйста, такое решение следующей классической задачи о старушке.

Задача такая: В самолёте $N$ мест, и есть $N$ пассажиров. Первый пассажир, который заходит в самолёт - сумасшедшая старушка, которая занимает произвольное место (возможно, что и своё). После этого каждый пассажир занимает своё место, если оно свободно, либо произвольное, если своё занято. Найти вероятность того, что последний пассажир займёт своё место.

Пусть $P$ - вероятность того, что последний не займёт своё место.

Тогда рассмотрим старушку: она может с вероятностью $1/N$ сесть на любое из $N$ мест.

Граничные случаи: пусть она займёт своё место, тогда все остальные сядут на свои места, и последний тоже, т.о. $P=0$. Пусть она сядет на место последнего, тогда он точно не сядет на своё, $P=1$.

Основной случай: пусть старушка села на место с номером $M$, таким что $2\le M\le N-1$. Тогда все пассажиры с номерами $i$: $2\le i\le M-1$ займут свои места (т.к. они все свободны). Рассмотрим пассажира $M$ как старушку, при этом местом этой старушки обозначим место изначальной старушки. Это законно, т.к. новая старушка садится произвольно на любое место, и в случае, если новая старушка сядет на своё место, то дальше все сядут на свои, в противном случае она сядет на место $M+k$, и $M+k$-й пассажир опять станет старушкой.

Обозначим $P(N)$ - вероятность того, что последний человек не сядет на своё место в случае задачи из $N$ человек. Получаем рекуррентное соотношение:

$$P(N) = \frac{1}{N}(0 + P(N-1) + \cdots + P(2) + 1 )$$

Очевидно, что $P(2)=1/2$. Докажем по индукции, что $P(N)=1/2$. Пусть $P(N)=1/2$, тогда

$$P(N+1) = \frac{1}{N+1}( P(N) + P(N-1) + \cdots + P(2) + 1) = \frac{1}{N+1}P(N) + \frac{N}{N+1}P(N) = P(N) = \frac{1}{2}$$

Т.о. получаем ответ: $P = 1 - P(N) = 1/2$.

[ИСН]

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

[sup]

На самом деле решение ещё проще. Какое место может достаться последнему пассажиру? Легко видеть, что либо его собственное либо старухино. Но узнает он об этом только взглянув на свой билет. Значит вероятность $1/2$.

[Sonic86]

mospehraict в сообщении #455227 писал(а):

Граничные случаи: пусть она займёт своё место, тогда все остальные сядут на свои места, и последний тоже, т.о. $P=0$. Пусть она сядет на место последнего, тогда он точно не сядет на своё, $P=1$.

Мелкое замечание: синтаксис неправильный. $P$ - это ответ, он дается на задачу в целом, а не на какие-то условия. Писать надо условную вероятность.

-- Вт июн 07, 2011 19:42:35 --

Кстати! Поскольку ответ $N$ не содержит, то должно существовать рассуждение, не опирающееся на $N$ существенно. До решения ИСН я додумался: там будет $P_N=\frac{1}{N} + \frac{N-2}{N}P_k + \frac{0}{N}, 1<k<N$, - но тут $N$ нужно, а вот решение sup я не понял Объясните!

[sup]

Да все очень просто. Какое кресло может достаться последнему пассажиру? Оно не может принадлежать ни одному из оставшихся пассажиров: коль скоро оно осталось пустым до самого конца, оно было пустым и тогда, когда зашел его хозяин. Вывод - это либо кресло старухи либо последнего пассажира.
Положим на стол старухин билет и билет последнего пассажира (прям как карты, рубашкой кверху). Они, разумеется, неотличимы. Один из них соответствует свободному креслу, второй нет. Выбрать "нужный" билет можно, очевидно, с вероятностью $1/2$. И этот выбор, по сути дела, произошел в момент покупки билета.

[Sonic86]

О! Понял!
Можно еще так: на каждом шаге существует обобщенная старушка, значит, понижая размерность, случай $N$ сводим к $N=2$ !!!

[mihailm]

Sonic86 в сообщении #455282 писал(а):

О! Понял!
Можно еще так: на каждом шаге существует обобщенная старушка, значит, понижая размерность, случай $N$ сводим к $N=2$ !!!

(Оффтоп)

обобщенные старушки мне еще не встречались

[mospehraict]

ИСН в сообщении #455233 писал(а):

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

Честно говоря, я не совсем понимаю такое решение. Из него следует рекуррентное соотношение (такое же, как и у меня), но это рекуррентное соотношение нужно всё-таки решить.

[PAV]

Задача уже возникала много раз, и не только здесь

topic12465.html
topic37503.html
post326161.html

[voipp]

Sonic86 в сообщении #455261 писал(а):

mospehraict в сообщении #455227 писал(а):

Граничные случаи: пусть она займёт своё место, тогда все остальные сядут на свои места, и последний тоже, т.о. $P=0$. Пусть она сядет на место последнего, тогда он точно не сядет на своё, $P=1$.

Мелкое замечание: синтаксис неправильный. $P$ - это ответ, он дается на задачу в целом, а не на какие-то условия. Писать надо условную вероятность.

-- Вт июн 07, 2011 19:42:35 --

Кстати! Поскольку ответ $N$ не содержит, то должно существовать рассуждение, не опирающееся на $N$ существенно. До решения ИСН я додумался: там будет $P_N=\frac{1}{N} + \frac{N-2}{N}P_k + \frac{0}{N}, 1<k<N$, - но тут $N$ нужно, а вот решение sup я не понял Объясните!

а как вы решать собрались это уравнение?

[buggsbuggs]

Ответ 1/2, конечно же, очевиден (поскольку вся иная информация не влияет на шансы последнего пассажира), но строгость и понятность приводимых выше решений меня лично не вполне устроила.

Предлагаю следующее решение. Пусть A- событие, состоящее в том, что последний пассажир сядет на свое место. Рассмотрим случай, когда у нас было n пассажиров и обозначим вероятность A через $P_n$ . Очевидно, что $ P_2=1/2$. Пусть известно, что для всех индексов s, не больших n, $P_s=1/2$. Рассмотрим случай, когда пассажиров (и мест) n+1. Введем гипотезы $H_k, k=1,...,n+1$, каждая из которых задает номер места, которое заняла бабушка. Тогда
$P(H_k)=\frac{1}{n+1}, k=1,...,(n+1), P(A/H_1)=1, P(A/H_{n+1}) = 0.$

Пусть реализовалось $ H_k$ и $2\leq k\leq n$. Тогда пассажиры с номерами от 2 до k-1 сели на свои места ($k-2$ человека). Поскольку первый (бабушка) уже сидит, то осталось $n-k+1$ мест и столько же пассажиров. При этом, хотя $k$-й и не может сесть на свое место, но, если он сядет на свободное первое, то все остальные пассажиры рассядутся по своим местам. Поэтому можно назвать первое место k-м, а k-го пассажира бабушкой, усаживающейся наугад (поскольку реально его место занято, он не связан ничем в выборе места). Следовательно,
$P(A/H_k) = P_{n-k+1} = 1/2 $
по индукционному предположению. Окончательно,
$P(A) = \frac{1}{n+1} (1+\sum_{k=2}^n P_{n-k+1} )= \frac{1}{n+1} (1+\frac{n-1}{2}) = 1/2 $
по формуле полной вероятности, и что и требовалось доказать.

[zer0]

По строгости меня вполне устраивает рассуждение:
Номер последнего незанятого места либо в билете старушки (БС) с некоторой вероятностью P(С), либо в билете пассажира БП с вероятностью P(П).
Ясно, что P(С)+Р(П)=1. Представим, что перед вылетом кто-то поменял их билеты, а старушка и все остальные пассажиры действовали так как раньше (они не могут отличить места старушки и пассажира). Но теперь P(C) - это то, что было P(П) и наоборот. А раз они в сумме 1, то каждый по 0.5.

[Deggial]

zer0, предупреждение за неоформление формул $\TeX$ом.

[buggsbuggs]

По некоторому размышлению склонен согласиться с решением zer0 (правда вряд ли оно относится к теме форума «рекурсивно»), но объяснял бы я его немного по-другому.

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

Теперь разобъем все рассадки пассажиров на две группы – ту, где последнее место значится в билете последнего пассажира (благоприятные варианты) и ту, где последнее место значится в билете старушки. Попросим местного карманника поменять билеты старушки и последнего пассажира (это следует делать уже в салоне самолета, поскольку билеты и паспорта проверяют перед самой посадкой, а значит, придется купить карманнику билет на этот рейс). Поскольку старушка при занятии места не смотрит в свой билет, то в результате все благоприятные варианты станут неблагоприятными и наоборот. В силу взаимной однозначности получившегося соответствия вариантов количества благоприятных и неблагоприятных вариантов одинаковы. Ответ, разумеется, $\frac12$.

[maxal]

Обобщение задачи в arXiv:
Absent-minded passengers