снова гномоед и 100 гномов, не про шапочки Опции

[svetlana]

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


Поймал гномоед 100 гномов, но решил не сразу суп из них сварить, а сначала поглумиться. Собрал он их в одой комнате, и говорит:

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

Ящики различаются между собой, скажем, пронумерованы. Ясно, что если гномы будут открывать наугад, то вероятность спастись 1/2^100, что ничтожно мало. Задача придумать хорошую стратегию, которая обеспечит значимую вероятность спастись.


P. S. Моргоюзверям, которые знают решение задачи от меня или из других источников, просьба не портить другим удовольствие от решения задачки.

[Eyeless Watcher]

Гномы могут как-то повлиять на исходное расположение имен в ящиках?
Имена гномов фиксированы?
Гномам разрешается переговариваться между заходами?

[svetlana]

Гномы могут как-то повлиять на исходное расположение имен в ящиках?
Имена гномов фиксированы?
Гномам разрешается переговариваться между заходами?

нет
да, фиксированы и все различны
не разрешается, конечно, а то первый бы всем все рассказал

[Либерал]

А гном должен сказать свое имя перед тем, как будет открывать ящики?

[svetlana]

А гном должен сказать свое имя перед тем, как будет открывать ящики?

Гномоед выучил имена гномов заранее.

[Eyeless Watcher]

Порядок следования гномов известен?

Кстати, итоговая вероятность не может быть больше 50% - первому-то точно отталкиваться не о чего.

Охохо. Нашел решение в гугле. Красиво

[svetlana]

Порядок следования гномов известен?

Кстати, итоговая вероятность не может быть больше 50% - первому-то точно отталкиваться не о чего.

Охохо. Нашел решение в гугле. Красиво

Порядок неизвестен.

Верно. Но она может быть гораздо больше 1/2^100.

А сколько удовольствия потеряли, оттого что полезли в гугл, вместо того чтобы самостоятельно порешать

[жора]

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

В условии не говорится, что ящики будут перетасованы перед испытанием. Поэтому они подготавливаясь в ЭТОЙ комнате тупо выучивают где лежит их имя.
Задача решена.

Кроме того, из условия однозначно следует что гномам всё равно пипец.

Поймал гномоед 100 гномов, но решил не сразу суп из них сварить, а сначала поглумиться.

Т.е. даже в случае решения задачи гномами - их съедят.

[Eyeless Watcher]

А сколько удовольствия потеряли, оттого что полезли в гугл, вместо того чтобы самостоятельно порешать

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

[p4w3l]

А они могут на ящиках царапать?) Если да, то задача весьма проста.

[svetlana]

2 p4w3l, жора: задачка честная, никаких царапаний, словесных ловушек и пр, решение чисто математическое.

[Eyeless Watcher]

Я вот только не увидел в этом решении обоснования его оптимальности

[p4w3l]

2 p4w3l, жора: задачка честная, никаких царапаний, словесных ловушек и пр, решение чисто математическое.

переставлять ящики можно? Достаточно ли большое помещение, чтобы их в ряд ставить?

[Analyt]

Если какой-нибудь гном не нашёл имени, их сразу в суп ведут или продолжают глумиться?
Другими словами, гномы как-то могут понять нашёл вышедший своё имя или нет?

И значимая вероятность -- это сколько?

[svetlana]

Я вот только не увидел в этом решении обоснования его оптимальности

Я не знаю доказательства оптимальности решения (моего решения, точнее, нашего, решали вдвоем). Равно как не знает его и человек, который, собственно, дал нам эту задачку.

переставлять ящики можно? Достаточно ли большое помещение, чтобы их в ряд ставить?

Давайте считать, что ящики расставлены в ряд и прибиты к полу.

Если какой-нибудь гном не нашёл имени, их сразу в суп ведут или продолжают глумиться?
Другими словами, гномы как-то могут понять нашёл вышедший своё имя или нет?
И значимая вероятность -- это сколько?

Гномов сразу всех в суп.

Значимая - это не очень хорошая формулировка, но я не знаю, как сформулировать лучше, чтобы не подсказать или не дать ответ, подсказывать вроде еще рано. Реальная вероятность спастись, а не 2^{-100}.