100 узников

[VAL]

arseniiv в сообщении #430000 писал(а):

(Оффтоп)

Ой, а мне показалось, что хотя бы одному надо найти!

Боюсь при такой трактовке 30% обеспечить не удастся. Всяко больше будет :)

-- 01 апр 2011, 17:30 --

Привожу решение.

Каким-нибудь образом пронумеруем коробки (например, слева направо) и
узников (например, по алфавиту или по возрасту). При этом возникнет
одна из 100! перестановок множества {1, 2,...,100}.
Напомню, что каждая перестановка единственным образом разлагается в
произведение независимых циклов.

Стратегия узников заключается в следующем:
Каждый узник открывает коробку с присвоенным ему номером.
Если ему повезет, то он обнаружит там записку со своим именем.
В противном случае он открывает коробку с номером того узника,
чье имя он обнаружил в первой коробке. И т.д.
До тех пор, пока не найдет коробку со своим именем или не исчерпает
50 попыток.
Легко видеть, что все узники уложатся в 50 попыток в том и только в том
случае, когда в циклической записи перестановки не будет цикла, длина
которого превысит 50.
Посчитать вероятность этого не слишком сложно. Действительно, если в
перестановке есть цикл длины $k$, причём $k>50$, то такой цикл один. Есть
$\frac{n!}{k!(n-k)!}$ способов выбрать множество элементов этого цикла, $(n-k)!$
способов задать перестановку на остальных, и $(k-1)!$ способов выстроить
выбранные элементы в цикл (достаточно поставить на первое место,
скажем, наименьший из них, после чего останется $(k-1)!$ способов
выстроить по порядку остальные). Таким образом, перестановок с циклом
длины $k$ ровно $\frac{n!}k$, а вероятность нарваться на такую перестановку
равна $\frac1k$. Поэтому, искомая вероятность равна
$1-\frac1{51}-\frac1{52}-\frac1{53}-\dots-\frac1{100}$, что больше 0.3.

В пределе же получаем $1-ln(2)$ (как и отмечал sup), что, кстати, тоже больше 0.3

[arseniiv]

(Оффтоп)

VAL в сообщении #430002 писал(а):

Боюсь при такой трактовке 30% обеспечить не удастся. Всяко больше будет :)

Вот и удивился, что даже для двух получалось! Тогда бы работал тривиальнейший алгоритм: каждому открывать первые 50 коробок и всё. Обычно такие задачи не раскусываю, и интуиция не подвела!

[Null]

Хорошая задача, только сложность непонятная.

(Оффтоп)

Если ученых не посадить они разбегутся.

[AlexDem]

VAL в сообщении #430002 писал(а):

Легко видеть, что все узники уложатся в 50 попыток в том и только в том
случае, когда в циклической записи перестановки не будет цикла, длина
которого превысит 50.

А что гарантирует то, что узник войдёт в свой, а не чужой цикл, даже если циклы мелкие? Допустим, циклы переставляют чётные с нечётными элементами, узник №100 открывает коробку №1, видит в ней №2, открывает №2, а там - №1.

[venco]

AlexDem в сообщении #430118 писал(а):

VAL в сообщении #430002 писал(а):

Легко видеть, что все узники уложатся в 50 попыток в том и только в том
случае, когда в циклической записи перестановки не будет цикла, длина
которого превысит 50.

А что гарантирует то, что узник войдёт в свой, а не чужой цикл, даже если циклы мелкие? Допустим, циклы переставляют чётные с нечётными элементами, узник №100 открывает коробку №1, видит в ней №2, открывает №2, а там - №1.

Начинает всегда со своего номера.

[AlexDem]

VAL в сообщении #430002 писал(а):

Стратегия узников заключается в следующем:
Каждый узник открывает коробку с присвоенным ему номером.
Если ему повезет, то он обнаружит там записку со своим именем.
В противном случае он открывает коробку с номером того узника,
чье имя он обнаружил в первой коробке. И т.д.

Вот на первом шаге ему не повезло, он переходит ко второму - тоже не повезло, и там цикл. Всё, не нашёл.

-- Пт апр 01, 2011 22:11:20 --

(Как и в случае с двумя игроками - там ведь тоже был шанс не попасть. Просто ведь эту вероятность здесь тоже нужно учитывать)

[VAL]

AlexDem в сообщении #430134 писал(а):

VAL в сообщении #430002 писал(а):

Стратегия узников заключается в следующем:
Каждый узник открывает коробку с присвоенным ему номером.
Если ему повезет, то он обнаружит там записку со своим именем.
В противном случае он открывает коробку с номером того узника,
чье имя он обнаружил в первой коробке. И т.д.

Вот на первом шаге ему не повезло, он переходит ко второму - тоже не повезло, и там цикл. Всё, не нашёл.

-- Пт апр 01, 2011 22:11:20 --

(Как и в случае с двумя игроками - там ведь тоже был шанс не попасть. Просто ведь эту вероятность здесь тоже нужно учитывать)

Надеюсь, это первоапрельская шутка?
Но на всякий случай: элемент не может не находиться в том цикле, в котором находится этот элемент :)

[AlexDem]

Да, я сообразил уже, что хотя изначальное сопоставление узников и коробок случайно, но от этого выбора меняются сами циклы. Нет, не шутка

[TOTAL]

Узники давно на свободе

[VAL]

TOTAL в сообщении #430994 писал(а):

Узники давно на свободе

Я в курсе, что задача не нова И изначально размещал ее, в теме, где обсуждались потрясающие математические факты, а не здесь.
Так что, нет вопросов. Кроме одного. Ваше участие в нынешнем решении - это первоапрельский розыгрыш или где?