задачка

[avva]

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

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

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

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

Comments

[flaass.livejournal.com]

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

[mirdin.livejournal.com]

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

[mirdin.livejournal.com]

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

[ahaxopet.livejournal.com]

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

[airatburganov.livejournal.com]

1/100

[mirdin.livejournal.com]

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

[krimsky.livejournal.com]

polovina

[(Anonymous)]

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

[mirdin.livejournal.com]

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

[getman.livejournal.com]

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

[mirdin.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]

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

[mihhon.livejournal.com]

1/100

[mihhon.livejournal.com]

нда, не 1/100
не учёл кое-что

[alef-grizley.livejournal.com]

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

[tobe-determined.livejournal.com]

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

[imenno.livejournal.com]

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

[flaass.livejournal.com]

А вот можно ли аналогичное решение, через биекцию, найти для моей задачки (см. вверху комментов)?
Там ответ тоже 100/2.

[kidd79.livejournal.com]

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

[liksu.livejournal.com]

А такое решение — правильное? ;)

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

Результат 49.5 ;)

Не совсем

[biglebowsky.livejournal.com]

Если мое решение задачи правильно, то 0.495 соответствует 101 пассажиру.
Примечание. А зачем Вам потребовалось записывать сумму арифметической прогрессии через perl ?

[arish.livejournal.com]

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

[v743.livejournal.com]

Вот!
Прочитав условие задачи, сразу автоматом подумал, что 1/2, и только увидев этот комментарий, понял почему я так подумал :)

[avva.livejournal.com]

Это немного безграмотное "разъяснение".

[rakshas.livejournal.com]

Одна вторая. Доказательство по индукции. Случай со 100 креслами сводится к множеству равновероятных вариантов с меньшим количеством кресел, каждый из которых сводится к множеству равновероятных вариантов еще меньшим количеством кресел, и т.д.

В результате каждая из ветвей остановится на вероятности 1/2.

[syarzhuk.livejournal.com]

50%

[angerona.livejournal.com]

по-моему эта задачка у вас уже раньше была. во всяком случае в ЖЖ она была точно (и я ее у себя потом, кажется, перепечатывала). В прошлом варианте первой пассажиркой была сумашедшая бабка, которая садилась куда угодно :)

[avva.livejournal.com]

Кажется, не у меня, но все может быть :)

P=49/99

[biglebowsky.livejournal.com]

Задача очень красивая!!!
Полностью согласен, что 49/99 ~ 1/2

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

[biglebowsky.livejournal.com]

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

Совершенно зря усложнил свои расчеты и liksu глупый комментарий написал.

[azzo27.livejournal.com]

1/2 ровно.
Предлагаю обобщение:
Первыми входят 20 сумасшедших пассажиров и садятся на любые места, затем 80 нормальных.
Какова вероятность, что 60-й нормальный сядет на свое место?

[flaass.livejournal.com]

А у меня другой вопрос: когда все сели, образовался ровно один цикл (скажем, если случайно все попали на свои места, то цикл длины 1). Каково матожидание его длины?

1/2

[qaraabayna.livejournal.com]

1/2

[iliat.livejournal.com]

На малых числах 1/2. Потом можно показать, что любое взоможное рассаживание однозначно описывается знанием сел или не сел конкретный номер (кроме первого) на свое место. Итого имеем 2^(н-1) вариантов, половина - если последний не сел.

[flaass.livejournal.com]

Не работает. Так бы получилось, что каждый сядет на свое место с вероятностью 1/2, а это неверно.
На вариантах "сел/не сел" процесс задает не равномерное распределение.

[aburachil.livejournal.com]

вероятность 50%, доказывается по индукции.

[kum-tykva.livejournal.com]

По индукции -- можно, но зачем?
Куда, собственно, вообще может попасть последний? На к-е(к > 1) место может? Нет, не может, потому что если оно его дождалось, то было свободным все это время, а значит, и когда вошел к-й пассажир -- но тогда он бы его и занял.
Значит, остаются всего два варианта -- свое собственное или первое. Пока они оба свободны -- мы ответа не знаем, идет розыгрыш, и они -- соврешенно равноправные кандидаты попасть под задницу(особенно очевидно это, по-моему, если заменить запудривающие мозги номера на, скажем, картинки -- типа там, на одном кресле цветочек, на другом грибочек -- ну совершенно понятно, что оба равноправны). Значит -- пополам.

[lom.livejournal.com]

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

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

размышления

[(Anonymous)]

Пусть для простоты у 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.