Занимательная задача

[Trotil]

Условие:

100 пассажиров заходят в самолет по одному. В самолете есть 100 мест, пронумерованных от 1 до 100, и у каждого пассажира есть назначенное ему место. Первый пассажир, вместо того, чтобы сесть на свое место, выбирает случайным образом одно из ста мест и садится на него. Все последующие пассажиры ведут себя следующим образом: если их "правильное" место еще не занято, они садятся туда, а если занято, выбирают случайным образом одно из оставшихся свободных мест и садятся на него.

Вопрос: какова вероятность того, что последний пассажир сядет на свое место?

Наткнулся в сети. Решение даже не искал, сам хочу поразмышлять...

 

[Forever Free]

Первый пассажир, вместо того, чтобы сесть на свое место, выбирает случайным образом одно из ста мест и садится на него.

Получается что выбирает не из 100 мест, а из 99 - он же на свое не садится ?

 

[Trotil]

Да нет... Вместо того, чтобы сделать выбор 1 из 1, он делает выбор 1 из 100. Так понятнее? Другими словами, по первому пассажиру
p=1/100 - он займет свое место
p=99/100 - он займет чужое место

 

[Forever Free]

Теперь понял.

 

[Trotil]

Ответ, вероятно... 1/2.

Входит первый пассажир, будем считать, что его место - k-оe, а он сел на первое (вер. 1/100).

C такой же вероятностью (вер. 1/100) последним может войти человек с первым местом и занять k-тое вместо своего.

 

[Forever Free]

Вот вопросец появился:
Тут же события зависимые ? От вероятности какое место займет первый пассажир зависит вероятность какое место займет следующий, и последний ?

 

[Изменившаяся]

Тут же события зависимые ? От вероятности какое место займет первый пассажир зависит вероятность какое место займет следующий, и последний

мне тоже кажетсЯ, что дело в зависимсоти. Ведь мест остается все меньше и меньше, а людей рпошло много: каждый из 100 человек допоследнего мог занять его место.

 

[Forever Free]

Если бы не это условие в задаче ----->

Все последующие пассажиры ведут себя следующим образом: если их "правильное" место еще не занято, они садятся туда

тогда число всех равновозможных случаев посадки пассажиров 100!,
а вероятность посадки пассажира на свое место 1/100!. Но вот это условие, черт возьми, меня смущает ...

 

[Trotil]

1/100!

Это всех пассажиров одновременно на свои места. А для каждого 1/100.

(если бы не это условие в задаче )

 

[server ne naiden]

Нам сказано, что пассажири заходят по дному. Может тогда так:
вероятность первого 1/100, второго 2/100, а последного 99/100?

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

А может так:
Раз первый выбирает не своё место, то он тогда выбирает, как сказал Forever Free из 99. тогда вероятность второго 1/100, и так далее... А последнего - 99/100...

короче, сама уже запуталась

 

[Forever Free]

Это всех пассажиров одновременно на свои места. А для каждого 1/100.

Это если считать что каждый заходит в пустой салон, ведь так ? Т.е. 1/100 справедливо только для первого.

 

[Trotil]

Решаем задачу сначала на малых числах перебором... Пусть у первого пассажира первое место, у второго - второе, ..., у n-того - n-тое. Они входят по-очереди и первый выбирает любое место.

n=2. Здесь всего два варианта - удачный и нет. p(2)=1/2

n=3. 3 варианта выбора первым кресла.
1/3 - удачный выбор, (1 кресло)
1/3 - неудачный (2-ое)
1/3 - неудачный (3-ее)

(1) - тогда все пассажиры автоматически садятся на свое место - последний садится с вер. p=1 на свое место
(2) - второй с p=1/2 выберет не третье место, значит p=1/2 третье место будет свободно и что последний сядет на свое место
(3) - первый занял место последжнего пассажира. Последний туда точно не сядет!



Теперь это нужно обобщить на большее кол-во мест.


Для произвольного n:

Первый пассажир выбирает произвольно из n мест:

1/n - первое место => p=1 для последнего
1/n - второе место - второй оказывается в положении первого - задача сводится к нахождению p(n-1)
1/n - третье место - второй садится на свое, третий оказывается в положении первого - задача сводится к нахождению p(n-2)
...
1/n - n-тое место - последний на свое место точно не сядет - оно занято!

=1/n*1+1/n*p(n-1)+1/n+1/n*p(n-2)+...+1/n*p(2)+1/n*0=1/n*(1+p(n-1)+p(n-2)+...+p(2))" src="http://graph.mixei.ru/Formula/formula.php?f=p=1/n*1+1/n*p(n-1)+1/n+1/n*p(n-2)+...+1/n*p(2)+1/n*0=1/n*(1+p(n-1)+p(n-2)+...+p(2))">

Далее нужно ее решить )

+p(n-1)+p(n-2)+...+p(2))" src="http://graph.mixei.ru/Formula/formula.php?f=p(n+1)=1/(n+1)*(1+p+p(n-1)+p(n-2)+...+p(2))"> или

n*p=1+p(n-1)+p(n-2)+...+p(2)) (из первого)
(n+1)*p(n+1)=1+p+p(n-1)+p(n-2)+...+p(2)) (из второго)

-> n*p=(n+1)*p(n+1)-p
=> p=p(n+1)=const =1/2 (мы ее получили на малых числах n=2,3)

Можно тоже самое доказать безо всяких вычислений, кстати. Заметим, что у нас только два крайних случая - выбор кресла первого пассажира и выбор кресла последнего. Выбор между ними осуществляется равновероятный.

Выбор любого другого кресла по сути ничего не решает. Допустим, первый пассажир выбрал k-тое место. Пассажиры 2, 3, ..., (k-1)-ый садятся на свое место, т.к. они свободно.

K-тый пассажир оказывается в положении первого: если он выберет 1-ое кресло - все садятся на свои места и последний тоже, если на последнее - неудачный исход. Если выбирает любое другое - момент "x" снова откладывается )

то если считать что каждый заходит в пустой салон, ведь так ?

Нет, для любого, хоть для первого, хоть для последнего.

 

[Федот Стрелец]

Я видел такую интерпритацию:

При посадке в самолет выстроилась очередь из n пассажиров, у каждого из которых имеется билет на одно из n мест. Первой в очереди стоит сумасшедшая старушка. Она вбегает в салон и садится на случайное место (возможно, и на свое). Далее пассажиры по очереди занимают свои места, а в случае, если свое место уже занято, садятся случайным образом на одно из свободных мест. Какова вероятность того, что последний пассажир займет свое место?

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