задачка

[avva]

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

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

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

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

Comments

[iliat.livejournal.com]

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

[flaass.livejournal.com]

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