Гномы и сундуки
Модераторы: Азарапетыч, Администрация
- Инна
- Популярный автор
- Сообщения: 1434
- Зарегистрирован: 18 июл 2006, 18:44
- Пол: Женский
- Откуда: Калифорния
Так Дендр всё подробно и абсолютно точно написал. То же самое более кратко: Гномы пронумеровались по порядку. Считаем, что у них не имена, а номера (так как есть взаимо-однозначное соответствие)team55 писал(а):Инна, решение-то расскажешь?
Тактика: Каждый, заходя, открывает сундук под своим номером. Затем - под номером числа (соответствующего имени), увиденного в первом сундуке, и т.д.. - всего П раз (или когда увидит свое число).
Рассмотрим перестановку : номера сундуков - номера гномов, указанные в них.
Гномы выживают, если эта перестановка не содержит циклов длины больше П.
Посчитаем вероятность обратного, она складывается из вероятностей наличия циклов длины П+1, П+2, ..., 2П.
Вероятность наличия цикла длины П+к равна если не ошиблась
С(п+к, 2п)*(п-к)!*(п+к-1)! /(2п)!=1/(п+к)
Сумма 1/(п+к) при к от 1 до п приблизительно равна ln(2).