|
|
 |
Условие
В каждую жвачку вложен один из n вкладышей, причём каждый вкладыш встречается с вероятностью 1/n.
Сколько в среднем надо купить жвачек, чтобы собрать полную коллекцию вкладышей?
Подсказка
В ситуации, когда уже собрано k вкладышей, вычислите среднее количество жвачек, которое нужно купить, чтобы последняя жвачка добавляла новый вкладыш.
Решение
Пусть у нас уже собрано k вкладышей. Посчитаем, сколько ждать следующего вкладыша. Назовем жвачку новой, если вложенный в нее вкладыш не встречается среди k уже собранных вкладышей. Обозначим через Mk среднее количество жвачек, которое нужно купить, чтобы последняя купленная жвачка была новой. Рассмотрим следующую купленную жвачку. Она с вероятностью n–k/n новая (и при этом ожидание (k+1)-й жвачки в коллекции заканчивается), и с вероятностью k/n не является новой (в этом случае мы, купив одну жвачку, снова оказываемся в состоянии, когда среднее число жвачек, которые нужно купить до покупки новой, равно Mk). Следовательно, Mk = n–k/n·1 + k/n·(Mk + 1), откуда Mk = n/n–k. Значит, среднее число жвачек, которое необходимо купить для полной коллекции вкладышей, равно M0 + M1 + ... + Mn–1 = n/n + n/n–1 + ... + n/1 = n(1 + 1/2 + 1/3 + ... + 1/n).
Ответ
n(1 + 1/2 + 1/3 + ... + 1/n).
Источники и прецеденты использования
| web-сайт | |
| задача |
