Математический факультетИнформация для студентовЭлектронная библиотека
Карта сайтаКарта сайта
Недавние измененияНедавние изменения
ПоискПоиск
  
Вы посетилиВы посетили
История страницыИстория страницы
  
Вход/выходВход


Содержание

ММ43

Конкурсная задача ММ43 (3 балла)

Эта задача предложена для марафона Владиславом Франком.

В вагоне экспресса Дакс-Бордо n мест.
Человек заходит в вагон, имея билет без места. Он знает, что в вагоне свободно ровно одно место. Садится на произвольное. Потом начинают заходить пассажиры, знающие, где они должны сидеть. Иногда его сгоняют и он пересаживается на произвольное оставшееся место. И так пока вагон не заполнится. Найти матожидание числа пересадок.

Решение

Пусть M(n) - матожидание числа пересадок. Если зашел первый пассажир, имеющий билет с местом, то с вероятностью 1/n он сгонит нашего бедолагу, а вероятностью (n-1)/n не тронет. В любом случае после этого возникнет ситуация, аналогичная предыдущей, но для вагона с количеством мест - n-1.
Значит, M(n) = (n-1)/n*M(n-1) + 1/n*(M(n-1)+1) = ((n-1)/n + 1/n)*M(n-1) + 1/n = M(n-1) + 1/n.
Поскольку M(1), очевидно, равно 0, то M(n) = 1/2 + 1/3 +…+ 1/n.

Обсуждение

Многие участники марафона высказали недовольство тем, что задача №43 слишком проста. Вопреки этому мнению некоторые другие марафонцы (успешно решившие ряд предыдущих задач) не справились с этой задачкой.

Влад Франк нашел не только матожидание, но и дисперсию числа пересадок: D(n) = Σ (1/i - 1/i2), где i изменяется от 2 до n.

Награды

За правильное решение задачи №43 Олег Полубасов, Андрей Богданов, Владимир Марунин, Андрей Винокуров и Юрий Шеляженко получают по три призовых балла. Алексей Бурдин, приславший решение правильное по подходу, но не по результату, получает два призовых балла. Андрей Бежан, «стрелявший (и промахнувшийся) из пушек по воробьям» получает один призовой балл.
Влад Франк, предложивший эту задачу, паолучает 5 призовых баллов.

 

 


Страница: [[marathon:problem_43]]

marathon/problem_43.txt · Последние изменения: 2016/03/04 11:39 — letsko
Powered by DokuWiki  ·  УКЦ ВГПУ 2006