Гномы и сундуки

Логические задачи

Модераторы: Азарапетыч, Администрация

Аватара пользователя
team55
Популярный автор
Популярный автор
Сообщения: 1086
Зарегистрирован: 18 апр 2006, 16:49

Сообщение team55 »

Инна, решение-то расскажешь? ;)

Аватара пользователя
Инна
Популярный автор
Популярный автор
Сообщения: 1434
Зарегистрирован: 18 июл 2006, 18:44
Пол: Женский
Откуда: Калифорния

Сообщение Инна »

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

Ответить

Вернуться в «Задачки»