?

Log in

No account? Create an account
задачка - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

задачка [май. 19, 2007|02:45 am]
Anatoly Vorobey

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

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

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

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

СсылкаОтветить

Comments:
Страница 1 из 2
<<[1] [2] >>
[User Picture]From: flaass
2007-05-19 10:03 am
Я добавлю задачку, у которой знаю ответ, но не знаю правильного решения.
Каждый из 100 ковбоев наугад прицелился в одного из остальных. Потом они начинают по очереди стрелять: на К-м шаге К-тый ковбой стреляет, если он еще жив и мишень еще жива. Убивает, конечно.
Каково матожидание числа оставшихся в живых?
(Ответить) (Thread)
[User Picture]From: mirdin
2007-05-19 10:39 am
Эта задачка не интересна. Более интересна задача про дуэль на троих:
Три человека решили устроить странную дуэль: бросают жребий, кто каким стреляет и дальше стреляют по очереди. При этом один из стрелков попадает всегда, второй попадает с вероятностью 2/3, а 3-й с вероятностью 1/2. У кого больше всех шансов выжить? :)
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: mirdin
2007-05-19 10:04 am
Если не ошибаюсь, то благодаря большому коричеству пассажиров, у каждого из которых практически независимое распределение вероятностей, можно применить центральную предельную теорему, которая даст нам ответ 1/2 сразу и без долгих размышлений.
ЗЫ: с теорией вероятности у меня не очень хорошие отношения, поэтому могу и ошибаться.
(Ответить) (Thread)
[User Picture]From: ahaxopet
2007-05-19 10:20 am
Ответ правильный, но он будет таким даже при небольшом количестве пассажиров :-)
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: airatburganov
2007-05-19 10:08 am
1/100
(Ответить) (Thread)
[User Picture]From: mirdin
2007-05-19 10:09 am
А можно решение?
(Ответить) (Parent) (Thread)
[User Picture]From: krimsky
2007-05-19 10:15 am
polovina
(Ответить) (Thread)
From: (Anonymous)
2007-05-19 10:19 am
-Какова вроятность того, что вы сейчас на улице встретите живого динозавра?
-Одна вторая: либо встречу - либо не встречу.
(Ответить) (Thread)
[User Picture]From: mirdin
2007-05-19 10:27 am
Не. Неправильный ответ. И неправильная аналогия ;). Аналогия для нашей задачи - какова вероятность, что какой-то человек через 2000 лет встретит динозавра. Вот там будет вероятность 1/2 согласно все той же центральной предельной теореме (много независимых распределений приведут к тому, что распределение финального события будет гауссовым, а крайние вероятности 0 - не встретил и 1 - встретил, в результате центр Гауссианы (и матожидание) будут на 1/2)
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: getman
2007-05-19 10:27 am
У последнего пассажира нет выбора, он сядет на последнее оставшееся место, У правильного места 1/100 вероятность остаться свободным.
(Ответить) (Thread)
[User Picture]From: mirdin
2007-05-19 10:29 am
Это не правильное решение. откуда вы взяли вероятность 1/100 правильному креслу остаться свободным? Не забыли что цепочка неправильных кресел может прерваться уже на втором пассажире, если он сядет на место первого пассажира?
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: kinad
2007-05-19 10:29 am
Задача милая, когда мне дали ее первый раз, я угадал, что должно быть 1/2, проверил для n=2,3,4, но когда написал суммы для вероятностей, затруднился их посчитать напрямую. Простое решение - рекурсивное, второй оказывается в такой же ситуации, как первый, только для n-1 места etc.
(Ответить) (Thread)
[User Picture]From: alef_grizley
2007-05-19 10:29 am
Действительно, 1/2 для любого количество больше 1. Но совсем не из-за ЦПТ.
Pn+1 = (P1+...Pn)/(n+1)
P1=1
(Ответить) (Thread)
[User Picture]From: mirdin
2007-05-19 10:34 am
А кто вам сказал, что ваше решение единственное верное? Вы перебираете вероятности, а я использую доказанную теорему.
(Ответить) (Parent) (Thread)
[User Picture]From: mihhon
2007-05-19 10:39 am
1/100
(Ответить) (Thread)
[User Picture]From: mihhon
2007-05-20 09:55 pm
нда, не 1/100
не учёл кое-что
(Ответить) (Parent) (Thread)
[User Picture]From: alef_grizley
2007-05-19 10:39 am
между прочим первый пассажир с вероятностью 1/100 садится и на свое место и тогда все сидят на своих местах - так что вероятность в любом случае > 1/100.
А с вероятностью 1/100 садится на место Х и тогда мы имеем ту же задачу для 100-Х+1 пассажиров.
(Ответить) (Thread)
(Удалённый комментарий)
From: tobe_determined
2007-05-19 02:07 pm
все верно. вероятность того, что первый пассажир сядет на свое место 1/2, а значит вероятность того что все остальные пассажиры сядут на свои места тоже 1/2.
(Ответить) (Parent) (Thread)
[User Picture]From: imenno
2007-05-19 11:41 am
Красивая задачка. Когда понимаешь, в чём дело (решив для малых N), можно найти взаимно однозначное соответствие между множеством "хороших" и "плохих" вариантов. Ответ, естественно, такой же, какой дал господин государственный прокурор на вопрос Максима Каммерера касательно шансов последнего остаться в живых при захвате Центра.
(Ответить) (Thread)
[User Picture]From: flaass
2007-05-19 12:39 pm
А вот можно ли аналогичное решение, через биекцию, найти для моей задачки (см. вверху комментов)?
Там ответ тоже 100/2.
(Ответить) (Parent) (Thread)
(Удалённый комментарий)
[User Picture]From: kidd79
2007-05-19 11:44 am
А я думаю, все же не взлетит™ :))))
(Ответить) (Thread)
[User Picture]From: biglebowsky
2007-05-20 10:14 am

Не совсем

Если мое решение задачи правильно, то 0.495 соответствует 101 пассажиру.
Примечание. А зачем Вам потребовалось записывать сумму арифметической прогрессии через perl ?
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: arish
2007-05-19 02:36 pm
Красивая задачка. Мне кажется, чтобы поверить в правильное решение легче считать, что первого сумасшедшего пассажира сгоняет с места тот, кто должен там сидеть, и он опять садится на случайное место.
(Ответить) (Thread)
[User Picture]From: v743
2007-05-19 03:58 pm
Вот!
Прочитав условие задачи, сразу автоматом подумал, что 1/2, и только увидев этот комментарий, понял почему я так подумал :)
(Ответить) (Parent) (Thread)
Страница 1 из 2
<<[1] [2] >>