задачка

[avva]

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

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

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

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

Comments

[flaass.livejournal.com]

Я добавлю задачку, у которой знаю ответ, но не знаю правильного решения.
Каждый из 100 ковбоев наугад прицелился в одного из остальных. Потом они начинают по очереди стрелять: на К-м шаге К-тый ковбой стреляет, если он еще жив и мишень еще жива. Убивает, конечно.
Каково матожидание числа оставшихся в живых?

[mirdin.livejournal.com]

Если не ошибаюсь, то благодаря большому коричеству пассажиров, у каждого из которых практически независимое распределение вероятностей, можно применить центральную предельную теорему, которая даст нам ответ 1/2 сразу и без долгих размышлений.
ЗЫ: с теорией вероятности у меня не очень хорошие отношения, поэтому могу и ошибаться.

[airatburganov.livejournal.com]

1/100

[mirdin.livejournal.com]

А можно решение?

[krimsky.livejournal.com]

polovina

[(Anonymous)]

-Какова вроятность того, что вы сейчас на улице встретите живого динозавра?
-Одна вторая: либо встречу - либо не встречу.

[ahaxopet.livejournal.com]

Ответ правильный, но он будет таким даже при небольшом количестве пассажиров :-)

[mirdin.livejournal.com]

Посчитайте вероятность для 3-х пассажиров ;) Будет не 1/2 ;)

[ahaxopet.livejournal.com]

Посчитал, получил ровно 1/2 :-)

[mirdin.livejournal.com]

Не. Неправильный ответ. И неправильная аналогия ;). Аналогия для нашей задачи - какова вероятность, что какой-то человек через 2000 лет встретит динозавра. Вот там будет вероятность 1/2 согласно все той же центральной предельной теореме (много независимых распределений приведут к тому, что распределение финального события будет гауссовым, а крайние вероятности 0 - не встретил и 1 - встретил, в результате центр Гауссианы (и матожидание) будут на 1/2)

[getman.livejournal.com]

У последнего пассажира нет выбора, он сядет на последнее оставшееся место, У правильного места 1/100 вероятность остаться свободным.

[kinad.livejournal.com]

Задача милая, когда мне дали ее первый раз, я угадал, что должно быть 1/2, проверил для n=2,3,4, но когда написал суммы для вероятностей, затруднился их посчитать напрямую. Простое решение - рекурсивное, второй оказывается в такой же ситуации, как первый, только для n-1 места etc.

[alef-grizley.livejournal.com]

Действительно, 1/2 для любого количество больше 1. Но совсем не из-за ЦПТ.
Pn+1 = (P1+...Pn)/(n+1)
P1=1

[mirdin.livejournal.com]

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

[flaass.livejournal.com]

> У правильного места 1/100 вероятность остаться свободным.
Хе-хе :)

[mirdin.livejournal.com]

А кто вам сказал, что ваше решение единственное верное? Вы перебираете вероятности, а я использую доказанную теорему.

[mihhon.livejournal.com]

1/100

[mirdin.livejournal.com]

Эта задачка не интересна. Более интересна задача про дуэль на троих:
Три человека решили устроить странную дуэль: бросают жребий, кто каким стреляет и дальше стреляют по очереди. При этом один из стрелков попадает всегда, второй попадает с вероятностью 2/3, а 3-й с вероятностью 1/2. У кого больше всех шансов выжить? :)

[alef-grizley.livejournal.com]

между прочим первый пассажир с вероятностью 1/100 садится и на свое место и тогда все сидят на своих местах - так что вероятность в любом случае > 1/100.
А с вероятностью 1/100 садится на место Х и тогда мы имеем ту же задачу для 100-Х+1 пассажиров.

[flaass.livejournal.com]

Дык, работать надо в выходные, а не задачки решать :)

[getman.livejournal.com]

У всех кресел равная вероятность остаться свободными, а их 100.

[kpoxa-e.livejournal.com]

центральную предельную теорему, которая даст нам ответ 1/2

Какова вероятность встретить динозавра на Ленинском проспекте? 1/2. Или встретишь, или не встретишь :)

неправильная аналогия

[kpoxa-e.livejournal.com]

Да прям :)
А если все пассажиры законопослышны, они вообще по определению сядут на свои места :о)

[imenno.livejournal.com]

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

[kidd79.livejournal.com]

А я думаю, все же не взлетит™ :))))