100 узников, 100 коробок

Тюремщик предлагает 100 узникам сыграть в следующую игру. В одной из комнат он поставит в ряд 100 коробок и случайным образом распределит по коробкам бумажки с именами узников (имена всех 100 узников различны, каждое имя попадёт ровно в одну из коробок).

Узники будут по одному заходить в комнату под присмотром тюремщика. После этого узник получает 50 попыток для того, чтобы найти в одной из коробок своё имя. Это означает, что он открывает любую коробку, читает имя на бумажке, кладёт бумажку обратно, закрывает коробку, выбирает следующую и так далее. После этого, независимо от результата, он возвращается к себе в камеру.

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

Оставлять какие бы то ни было знаки в комнате с коробками нельзя, тюремщик строго за этим следит. Можно даже считать, что тюремщик подготовил 100 идентичных комнат с коробками (с одинаковым распределением бумажек по коробкам).

Если каждый узник будет выбирать очередную коробку случайным образом, он найдёт своё имя с вероятностью 1/2. Вероятность того, что все 100 узников найдут своё имя, равна 1/(2^100), т.е. ничтожно мала. Могут ли они увеличить вероятность выигрыша, выбрав правильную стратегию?

3 дочери

Встретились два математика, и между ними произошёл такой разговор:
- У меня три дочери.
- Здорово! А сколько им лет?
- Произведение их возрастов равно 72, а сумма возрастов равна номеру того трамвая.
- Мне всё равно не хватает данных.
- Старшая любит мороженое.
- Тогда всё понятно.

Сколько лет дочерям?

Дмитрий Медведев и машина

Дмитрий Медведев привык возвращаться с работы домой на электричке. Каждый день ровно в 7 часов вечера он прибывает на электричке на свою станцию. Его жена каждый вечер выезжает из дома на машине с таким расчётом, чтобы ровно в 7 часов встретить мужа на станции и отвезти его домой.

Однажды, устав после бадминтона, Дмитрий Медведев отпросился с работы немного пораньше и приехал на свою станцию в 18:05, то есть на 55 минут раньше, чем обычно. Чтобы не ждать жену на станции, он пошёл пешком ей навстречу. Встретив жену по дороге, он сел в машину, и они вместе вернулись домой на 10 минут раньше обычного.

Во сколько раз скорость машины выше скорости Дмитрия Медведева?

12 монет, 3 взвешивания

Есть 12 монет, одна из которых фальшивая. При этом неизвестно, в какую сторону она отличается от настоящих, т.е. она может быть как легче, так и тяжелее. В вашем распоряжении чашечные весы без гирь, как в аптеке. Нужно за три взвешивания найти фальшивую монету, а также выяснить, тяжелее она или легче.

Две старушки

Рано утром одновременно из пункта А в пункт Б и из пункта Б в пункт А навстречу друг другу вышли две старушки. Они встретились в полдень и пришли в пункты назначения в 4 часа и в 9 часов вечера того же дня соответственно. Во сколько они вышли утром?

Очередь - 2

На этот раз я немного отойду от темы блога и опубликую алгоритмическую задачу.

Как и в предыдущей задаче, Штирлиц и Мюллер по очереди стреляют по очереди. На этот раз в очереди N человек. Нужно написать программу, которая для каждого из чисел 0 <= N < 1000 вычислит, кто выиграет при оптимальной игре обоих игроков.

Сразу скажу, что решить эту задачу прямолинейным поиском в глубину не получится. Мой вариант на Java тратил больше 10 минут уже при сравнительно небольших N в пределах 40.

Очередь

Штирлиц и Мюллер играют в игру, стреляя по очереди. В очереди 999 человек, и каждым своим ходом Штирлиц или Мюллер убивают одного из них. Если у человека в очереди не осталось соседей, он в ужасе убегает. Проигрывает тот, кто не может сделать очередной ход. Кто выиграет при правильной игре обоих участников?