2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 задача про сумасшедшую старушку, теорвер, рекурсивно
Сообщение07.06.2011, 15:21 


05/12/05
10
Добрый день,

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

Задача такая: В самолёте $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$.

 Профиль  
                  
 
 Re: задача про сумасшедшую старушку, теорвер, рекурсивно
Сообщение07.06.2011, 15:45 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: задача про сумасшедшую старушку, теорвер, рекурсивно
Сообщение07.06.2011, 16:06 
Заслуженный участник


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

 Профиль  
                  
 
 Re: задача про сумасшедшую старушку, теорвер, рекурсивно
Сообщение07.06.2011, 16:38 
Заслуженный участник


08/04/08
8556
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 я не понял :-( Объясните!

 Профиль  
                  
 
 Re: задача про сумасшедшую старушку, теорвер, рекурсивно
Сообщение07.06.2011, 16:51 
Заслуженный участник


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

 Профиль  
                  
 
 Re: задача про сумасшедшую старушку, теорвер, рекурсивно
Сообщение07.06.2011, 17:00 
Заслуженный участник


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

 Профиль  
                  
 
 Re: задача про сумасшедшую старушку, теорвер, рекурсивно
Сообщение07.06.2011, 17:08 


19/05/10

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


(Оффтоп)

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

 Профиль  
                  
 
 Re: задача про сумасшедшую старушку, теорвер, рекурсивно
Сообщение11.06.2011, 14:37 


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

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

 Профиль  
                  
 
 Re: задача про сумасшедшую старушку, теорвер, рекурсивно
Сообщение11.06.2011, 15:11 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
Задача уже возникала много раз, и не только здесь

topic12465.html
topic37503.html
post326161.html

 Профиль  
                  
 
 Re: задача про сумасшедшую старушку, теорвер, рекурсивно
Сообщение07.06.2013, 22:27 


13/12/09
122
МАИ прикладная математика
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 я не понял :-( Объясните!


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

 Профиль  
                  
 
 Re: задача про сумасшедшую старушку, теорвер, рекурсивно
Сообщение04.07.2013, 06:38 
Аватара пользователя


04/07/13
6
Ответ 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 $
по формуле полной вероятности, и что и требовалось доказать.

 Профиль  
                  
 
 Re: задача про сумасшедшую старушку, теорвер, рекурсивно
Сообщение07.07.2013, 14:07 


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

 Профиль  
                  
 
 Re: задача про сумасшедшую старушку, теорвер, рекурсивно
Сообщение07.07.2013, 18:30 
Супермодератор
Аватара пользователя


20/11/12
5728
 !  zer0, предупреждение за неоформление формул $\TeX$ом.

 Профиль  
                  
 
 Re: задача про сумасшедшую старушку, теорвер, рекурсивно
Сообщение12.07.2013, 14:01 
Аватара пользователя


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

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

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

 Профиль  
                  
 
 Re: задача про сумасшедшую старушку, теорвер, рекурсивно
Сообщение28.09.2018, 06:08 
Модератор
Аватара пользователя


11/01/06
5660
Обобщение задачи в arXiv:
Absent-minded passengers

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 15 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group