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


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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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


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


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

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

Тогда надо как-то хитро договориться о том, кто какие ящики проверяет. С каждым угадавшим гномом шансы остальных найти своё имя повышаются.
Но подробности я сейчас так сразу ниасилю, пожалуй.

По условию как только ОДИН гном не находит свое имя, в суп сразу ВСЕХ. Так что, кажется, и неважно, сразу их в суп после ошибки или только после того как остальные пооткрывают ящики.

Если гном находит своё имя, значит оно точно в каком из ящиков, которые он открывал и все остальные знают, какие именно ящики он открывал, они могли ведь ночью об этом договориться, кому какие достанутся. Значит, в каком-то ящике именно из этих ящиков с какой-то-там вероятностью нет имени ещё не зашедших. Согласно этому знанию, следующий заходящий гном имеет свою стратегию открывания ящиков, причём все остальные знают, какую.

Это я к тому, что условие "сразу в суп" существенное, без него задачка, похоже, не решается.

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

Это потому, что у очередного входящего в комнату гнома без этого условия не будет вообще никакой инфы, кроме того, что его имя где-то в ящиках.

Вот можно как-то так:


Начнём с пары гномов .
Если гномики договорятся, что первый входящий открывает первый ящик, и после выхода из комнаты гномоед никого не поведёт на обед, то наверняка во втором ящике -- имя второго и последнего гнома. Вероятность спасения всех -- половина .
Для четырёх гномов так:
первая пара входящих открывает первые два ящика, у них верятность найти своё имя такая же, как и при отсутствии стратегии выбора ящиков. Зато, если после выхода второго все всё ещё не в в супе, вторая пара гномов точно знает, что их имена во второй паре ящиков, так что текущая ситуация сводится к предыдущей и вероятность второй пары найти свои имена очень приятная.
Для 2N гномов.
Первые N роются в первой половине ящиков, остальные N, если живы -- во второй. У первых верятность найти имя обычная, у вторых -- выше в пару раз.

Analyt, итоговая вероятность получится порядка 30%. Если это подсказка - удалю.

Я не считала, какая тут вероятность получается.
И не уверена, что такая стратегия единственная, но она точно значимо © повышает вероятность спасения.

Так себе вероятность получается
То, что у первых 50, которые всегда открывают первые 50 ящиков, вероятность 1/2 - неверно. Как минимум рассмотрим последнего из них. Он знает, что среди 50 ящиков, которые он будет открывать только один в котором может быть его имя (49 из них заняты именами предыдущих). А всего ящиков, где может быть его имя - 51. Итого получаем не 1/2, а 1/51. И так со всеми остальными. Сдается мне, ничего вы не повысили, тем более значимо ©

я нигде такого не утверждала. Наоборот, у каждого из первой половины открывающих вероятность найти имя -- такая же как вообще без стратегии. Половина -- это вероятность спасения всех (а не нахождения имени) только когда гномов двое.

Насчёт ничего не повысила -- это Вы погорячились. Прочитайте внимательнее. А значимо или нет -- пусть svetlana скажет, это её термин.

Хорошо, не совсем понятно выразился.
Неверно то, что у каждого из первых 50, кто открывает только первые 50 ящиков, вероятность найти имя 1/2. Как минимум у последнего хуже.
Кстати, порядок следования гномов в биореактор комнату неизвестен, так что первых 50 гномов у нас просто нет.

Конечно, нет. Вероятность найти имя пока для первой половины ровно такая же, как и при отсутствии стратегии. Для второй -- иначе.

Есть первая половина входящих, их имена абсолютно не важны.

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

Ну неверно это, елки-палки. При отсутствии стратегии, то есть при случайном выборе ящиков вероятность попасть в свое имя - 1/2 для каждого.
В вашем же случае уже второй зашедший будет открывать один ящик, который ему заведомо не нужен, и таким образом будет иметь не 50 из 100, а 49 из 99, что меньше 1/2.

Какой ужас. Бедные гномы. Тогда да, глупость какая-то получается.

Кстати, вероятность вы слегка повысили
В вашем случае гномы выживают, если все имена первой половины попадут в первую половину, а второй - соответственно во вторую. Таких исходов 50! * 50!. Всего возможных исходов 100!. Итоговая вероятность равна 9.91 x 10^-30, что больше, чем 2^(-100) в 12 с половиной раз
Однако сдается мне, что 10^-29 не является хоть сколь-нибудь значимой вероятностью...

Так...то есть следом зашеший гном не знает, какой он по счету и не знает в каких ящиках имена тех, кто свои нашел?

Именно так.

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

То, что не знает, какой по счету - это точно И в задаче не двое, а сто гномов
Как их можно знать приблизительно, если не знаешь, кто до тебя ходил? Порядок неизвестен, об этом svetlana говорила.

Хочу дождаться ответа svetlana. Не, я понимаю, что Вы решение знаете, но вдруг оно не единственое. И вообще, интересно было бы таки найти приличное решение для таких вот условий.
Удобнее 2N гномов.
Неважно, кто именно ходил, может быть важно сколько. При этом условии в моём типа решении вторая половина знает даже не приблизительно, а точно, что их имён нет в первой половине ящиков.

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

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

а) каждый такой список должен быть уникален (если допустить, что в ходе эксперимента, какой-то из гномов использует тот же список что и его удачливый предшественник, тогда имя этого удачливого предшественника в списке с вероятностью единица и вновь выбирающий имеет реально не 50 шансов, а 49 или меньше если в точности этим списком пользовались до него более одного раза)

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

построить такие списки можно с помощью квадратной матрицы размерности 100. Строки представляют номера ящиков, столбцы - именные списки (гномов можно тоже пронумеровать для удобства, если ночь длинная). на пересечении строки i и столбца j стоит единичка если в j-том списке есть i-тый ящик. По нашему условию в каждой строке должно быть в точности 50 единиц и 50 нулей, аналогично для столбцов. Искомая матрица - 49-диагональная у которой в позициях в областях (i>75, j<25) и (j>75, i< 25) дополнительные единицы, а в остальных ячейках нули.

Да вы изначально не поняли: не знает гном, сколько до него было, каким по счету он заходит. Он может быть и 1 и 50 и 100.

Мы говорим, похоже, о разных моментах времени для этого знания.
Можно предположить, что гномы могут видеть входную дверь в комнату с ящиками. Какой из них пойдёт первым, вторым и последним, до начала угадывания они не знают. Но в тот момент, когда гном подходит к двери, он знает, какой он по счёту, потому что видел, сколько гномов из этой комнаты уже вышло.
В условии задачи никаких уточнений по этому поводу нет, в комментах svetlana пока тоже.

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

То самое решение не требует приобретения гномами инфы в процессе.

Всякие вероятностные игрушки? Я тогда пас.

Там действительно весьма нетривиальная математика, как до такого додумываться, я не знаю. Если хотите, могу в ЛС скинуть ссылку на решение.

Да, пришлите, пожалста.
Беглый поиск дал только формулировку этой задачи как задачи про заключённых и коробки. В разделе "Детские задачи".

http://math.nw.ru/~pozharsky/Other/Tasks/T...01_20.html#_top

упд. Спасибо, красиво.

заключенные могут априори писать на коробках перед осматриванием, гномы - нет. это две разные задачи таки.

Один может писать, самый первый и непосредственно перед осмотром. У гномов пронумерованы коробки. Здесь это одно и то же, в том смысле, что решение для ЗК сводится к решению для гномов, и обратно.

Ваша правда, невнимательно посмотрел.

Можно и мне ссылку в ЛС на правильное решение?

Я тоже хочу увидеть)

Это, конечно, подсказка (номер 1), но, видимо, без нее все равно никак, так что пусть висит.

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

Otouto, не увидела решения и ответа, признаться, только какие-то общие соображения. Часть посылок неверная (типа что все ящики должны открываться одинаковое количество раз).

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

Подсказка номер 2 для тех, кто еще не сдался. Ящики можно открывать не сразу, а поочереди. Соответственно, появляется возможность как-то использовать информацию о том, что написано внутри уже открытых ящиков.

P. S. Извиняюсь за задержку с ответом, воскресенье прошло без интернета и компьютера.

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

Я бы сказал, чтобы придти к правильному ответу осознанно, нужно заниматься эффективной вычислимостью, компьютерсайнс или чем-то в таком духе, в общем, чтобы адженда была правильная. Иначе такое решение можно найти разве что методом удачных тыков. Чисто логических соображений к нему приводящих не вижу. Даже для среднего выпускника нашего мехмата эта задачка - издевательство (:

Это форма записи некоторого решения, но вероятность-то какая?

Да ладно Вам, оно выглядит гораздо неберучее, чем есть на самом деле. Ну, непростая, конечно, может скорее на "замкнет в голове - не замкнет".
То, что ничего хорошего не получится, если открывать все ящики сразу, становится интуитивно ясно довольно быстро. Дальше уже проще.

И, потом, я же подсказки даю

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

svetlana, а много ли народу у которых "замкнуло"?

Вероятность считается как отношение квадрата числа перестановок длины 100 (число матриц получаемых из исходной перестановками строк и столбцов), к (100!/50!)^(100) (мощность множества всех способов открываний 100 гномами 5000 ящиков, при условии, что никакой гном не открывает в свою попытку один и тот же ящик дважды). Сколько это в точности не знаю - калькулятор дома забыл

Меня в решении по ссылке найденном Eyeless Watcher одно смутило - правильное-то решение там приводится, но то, что оно правильное мы принимаем на веру. Там нет доказательства, что не существует более эффективной стратегии - сказано лишь, что это доказательство существует. А это еще одна, подозреваю, не совсем простая часть этой задачи.