?

Log in

задачка - Поклонник деепричастий [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: 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: liksu
2007-05-19 01:12 pm
А такое решение — правильное? ;)

perl -e "$summ += (101-$_)/100 foreach (2..100); print $summ"

Результат 49.5 ;)
(Ответить) (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)
(Удалённый комментарий)
[User Picture]From: avva
2007-05-20 06:11 am
Это немного безграмотное "разъяснение".
(Ответить) (Parent) (Thread)
[User Picture]From: rakshas
2007-05-19 04:05 pm
Одна вторая. Доказательство по индукции. Случай со 100 креслами сводится к множеству равновероятных вариантов с меньшим количеством кресел, каждый из которых сводится к множеству равновероятных вариантов еще меньшим количеством кресел, и т.д.

В результате каждая из ветвей остановится на вероятности 1/2.
(Ответить) (Thread)
[User Picture]From: syarzhuk
2007-05-19 08:05 pm
50%
(Ответить) (Thread)
[User Picture]From: angerona
2007-05-20 05:35 am
по-моему эта задачка у вас уже раньше была. во всяком случае в ЖЖ она была точно (и я ее у себя потом, кажется, перепечатывала). В прошлом варианте первой пассажиркой была сумашедшая бабка, которая садилась куда угодно :)
(Ответить) (Thread)
[User Picture]From: avva
2007-05-20 06:11 am
Кажется, не у меня, но все может быть :)
(Ответить) (Parent) (Thread)
[User Picture]From: biglebowsky
2007-05-20 09:58 am

P=49/99

Задача очень красивая!!!
Полностью согласен, что 49/99 ~ 1/2
(Ответить) (Thread)
[User Picture]From: biglebowsky
2007-05-20 11:30 am

Re: P=49/99 - ошибка. Ответ 1/2

Я был неправ. Невнимательно прочитал условие. Оказывается, первый пассажир занимает не чужое место, а произвольное из 100, т.е., в том числе, возможно, и свое.
Тогда ответ, естественно, 1/2.

Совершенно зря усложнил свои расчеты и liksu глупый комментарий написал.
(Ответить) (Parent) (Thread)
[User Picture]From: azzo27
2007-05-20 06:14 pm
1/2 ровно.
Предлагаю обобщение:
Первыми входят 20 сумасшедших пассажиров и садятся на любые места, затем 80 нормальных.
Какова вероятность, что 60-й нормальный сядет на свое место?
(Ответить) (Thread)
[User Picture]From: flaass
2007-05-22 10:35 am
А у меня другой вопрос: когда все сели, образовался ровно один цикл (скажем, если случайно все попали на свои места, то цикл длины 1). Каково матожидание его длины?
(Ответить) (Parent) (Thread) (Развернуть)
From: qaraabayna
2007-05-20 11:23 pm

1/2

1/2
(Ответить) (Thread)
[User Picture]From: iliat
2007-05-21 12:29 am
На малых числах 1/2. Потом можно показать, что любое взоможное рассаживание однозначно описывается знанием сел или не сел конкретный номер (кроме первого) на свое место. Итого имеем 2^(н-1) вариантов, половина - если последний не сел.

(Ответить) (Thread)
[User Picture]From: flaass
2007-05-22 08:29 pm
Не работает. Так бы получилось, что каждый сядет на свое место с вероятностью 1/2, а это неверно.
На вариантах "сел/не сел" процесс задает не равномерное распределение.
(Ответить) (Parent) (Thread)
[User Picture]From: aburachil
2007-05-21 04:31 pm
вероятность 50%, доказывается по индукции.
(Ответить) (Thread)
From: kum_tykva
2007-05-22 01:00 am
По индукции -- можно, но зачем?
Куда, собственно, вообще может попасть последний? На к-е(к > 1) место может? Нет, не может, потому что если оно его дождалось, то было свободным все это время, а значит, и когда вошел к-й пассажир -- но тогда он бы его и занял.
Значит, остаются всего два варианта -- свое собственное или первое. Пока они оба свободны -- мы ответа не знаем, идет розыгрыш, и они -- соврешенно равноправные кандидаты попасть под задницу(особенно очевидно это, по-моему, если заменить запудривающие мозги номера на, скажем, картинки -- типа там, на одном кресле цветочек, на другом грибочек -- ну совершенно понятно, что оба равноправны). Значит -- пополам.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: lom
2007-05-22 08:38 pm
Самое забавное, что для решения этой задачи даже не нужна индукция - достаточно просто здравого смысла... легко заметить, что "отрицательный" и "положительный" исход абсолютно симметричны.

Когда в самолет входит первый пассажир - у него равные шансы сесть на собственное место ( положительный исход дальше гарантирован) и на место #100 ( отрицательный исход гарантирован). Далее: если первый вошедший занял чужое место, то для всякого следующего входящего всегда равные шансы занять то единственное из кресел, которое замкнет цепочку "неправильных посадок" ( а значит все следующие заведомо сядут на свои места --- гарантированный положительный исход) -- и единственное кресло #100 ( отрицательный исход)... Вот, собственно, и все. Полная симметрия гарантирует вероятность 1/2.
(Ответить) (Thread)
From: (Anonymous)
2007-05-31 11:15 am

размышления

Пусть для простоты у 1-го пассажира билет на место номер 1, у второго - билет на место номер 2, ..., у n-го - билет на место номер n. Пусть Pn - вероятность n-му пассажиру сесть на своё место. n- количество мест и пассажиров (n=100)
Вероятногсть первому пассажиру сесть на одно из n мест - 1/n. Если первый пассажир сел на место номер 1 то исход для 100-го положительный (вероятность =1/n)
если на место номер 2 то исход для 100-го 1/n*(P"n-1"), так как второй пассажир в этой ситуации находится в положении первого, и может с равными шансами занять 1-ое место и окончить цепочку, либо любое другое место.
если на место номер 3, то тогда второй пассажир садится на место номер 2, а третий находится в положении первого, вероятность для 100-го 1/n*(P"n-2")
и так далее.
Получается Pn=1/n(1+P"n-1"+P"n-2"+P"n-3"...+p2)
p2=1/2
p3=1/2
p4=1/2
p5=1/2
...

Первый пассажир может с равными шансами сесть на своё место (место номер 1) и на место номер 100. Если он садится любое другое место, например место номер 50, то 50-ый пассажир находится в положении первого, и может с равной вероятностью сесть на место номер 1 (которое ещё не занято, так как все пассажиры начиная с 2 по 49 садились на свои положенные места) либо на место номер 100. Поэтому полная симметрия, вероятность 1/2.
(Ответить) (Parent) (Thread) (Развернуть)
Страница 1 из 2
<<[1] [2] >>