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

[Инна]

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

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

[Antananarivu]

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

[Dendr]

Подсказки таки прозвучали.

В связи с вышесказанным можно проверить такую стратегию. Пронумеруем гномов, скажем по алфавитному принципу. Гном номер i открывает первым ящик i. Находит там имя гнома j. Открывает дальше ящик i + j (если i + j больше n, то i + j - n). Там имя номера x. Открываем i + x и т.д. Что-то не знаю, как посчитать вероятность попроще.

Хорошее предложение!
Осталось только его... упростить.
Именно, что просто до гениальности и гениально до простоты. Выиграть на "зеро" в рулетке и то труднее.

Поподробнее - завтра (ибо пишу с КПК в электричке...).
Но если не ошибаюсь, стратегия дает гигантский шанс гномам.
По предварительным прикидкам:
n=2 (4 гнома) 10/24=41%
n=3 (6 гнома) 346/720=48%
(Почти половину - ого )
Формулу для произвольного числа n вывести, похоже, довольно сложно (биномиальные коэффициенты никогда моим коньком не были). Но чисто физически можно понять, почему при больших n ответ должен быть конечен.

[Atson]

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

[Dendr]

n=3 (6 гнома) 346/720=48%
(Почти половину - ого :))

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

Итак. Идея простая, как круг.
Гномы, посовещавшись, нумеруют себя по порядку (как угодно - по росту, возрасту, алфавиту, размеру пуза, количеству золота в кармане...).
1. Шмякли
2. Брякли
...
2n. Звякли

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

Пусть зашел гном с номером K. Алгоритм:
1) Он отсчитывает слева сундук с этим же номером и открывает его.
2) Если там лежит табличка с его именем - он радостно выходит в комнату 3. Ну, для проформы, открыв любые остальные сундуки, положенные ему.
3) Иначе - там лежит табличка с именем другого гнома. Пусть, его номер - Р.
4) Гном открывает сундук с номером Р.
5) Безусловный переход в пункт (2).

Как мы видим, получаются "кольца" из сундуков.
Т.е., перейдем к такому примеру: в сундуках лежат шарики с номерами. Открываем, допустим, первый, там лежит семерка. Открываем седьмой - там шарик с числом 18. И так далее. Рано или поздно мы откроем сундук с единичкой. Это и есть кольцо.
Очевидно, что колец - конечное число. Минимальное кольцо - из одного сундука - в нем лежит его же номер. Маскимум - все сундуки в одном кольце.

Итак. Вернемся к гному с номером К. Его номер входит в какое-то кольцо. Пусть размер кольца - R(K). Значит, гном будет открывать сундуки, пока не увидит свое имя. Понятно, что это имя должно быть ссылкой на сундук K. Т.е. кольцо замыкается. Следовательно, гному К надо открыть R сундуков.
Чтобы все гномы выжили, для всех них R(K) должно быть не больше n (половины их числа).

Гномы погибают, соответственно, если хотя бы для одного из них R(K)>n. Точнее, так будет для R гномов. Другими словами, если среди сундуков будет большое кольцо.
Очевидно, что такое кольцо в неудачном для гномов случае будет ровно одно. Попробуем оценить, какова вероятность появления среди сундуков больших колец.
Ясно, что большая. Покажем, что она отличается от единицы на конечную величину, т.е. не малую, макроскопическую.

Грубую оценку можно сделать так. Рассмотрим набор из 2n бусин в коробочке. Трясем коробочку, бусины как-то случайно слепляются в цепочки. Какова вероятность того, что мы найдем "длинную" цепочку, из больше чем половины бусин? Какова вероятность того, что таких цепочек нет? Сравнимы ли эти вероятности? Это будет вам домашнее задание ;=) Но можно уже сейчас понять, что эти вероятности одного порядка.

Теперь перейдем к сундукам и гномам.
Подсчитаем вероятность того, что гномы погибнут.
Они погуибнут, если среди 2n сундуков будет кольцо (единственное) из n+1, n+2,... или 2n сундуков.
Какова вероятность того, что есть кольцо из k сундуков?
Подсчитаем число наборов с таким кольцом.
Сначала отберем сундуки вне кольца (2n-k) штук и расставим их слева направо. У нас получатся кольца, может быть, но не будем на них обращать внимания.
Таких наборов наберется, очевидно, (2n)!/k!. Разных наборов, ибо порядок тут очень важен.
Остальные сундуки дают большое кольцо.
Чтобы не запутаться, ставим их пока на свои места, а затем на оставшиеся ставим отобранные ранее сундуки, слева направо, в том же порядке.
Теперь переставляем сундуки кольца. Самый левый из них убираем пока в сторону. На его место ставим любой из (k-1) сундуков. На пустое место нельзя ставить отодвинутый сундук, иначе получится маленькое кольцо. Ставим сундук из (k-2) остальных... И т.д.
Т.е. вариантов перестановки кольцо у нас (k-1)!
Итого. Вариантов наборов сундуков с кольцом из k сундуков будет (2n)!/k, т.е. доля (или вероятность появления) таких сундуков от общего числа (2n)! равна 1/k.

Видно тогда, что вероятность гибели гномов равна сумме обратных величин от (n+1) до 2n.

В частности, для разных n:
n=1 => 1/2
n=2 => 1/3+1/4 = 7/12
n=3 => 1/4+1/5+1/6 = 37/60

При больших n суммирование, как обычно, заменяем интегрированием, получаем что вероятность гибели в таком случае составляет ln(2n)-ln(n+1)=ln(2).
Ну а вероятность выживания, соответственно, 1-ln(2).

Покажем на простейшем примере, как это работает. n=2. 4 гнома:
1 - Брякли
2 - Звякли
3 - Стукли
4 - Шмякли
Всего 24 варианта лежания табличек. Используем для краткости первые буквы имен. Вероятность, как показано выше, 5/12, т.е. должно быть 10 успешных варианта (ранее я уже нашел "лучшую" тактику - она давала лишь 4 хороших варианта)
Будем писать в таком виде:
ШЗСБ. Б:1-Ш->4-Б! З:2-З! С:3-С! Ш:4-Б->1-Ш!
ШЗСБ - набор табличек,
Б:1 - Брякли открывает 1-й сундук
1-Ш - гном открыл первый сундук, нашел имя "Шмякли"
Ш->4 - "Шмякли" дает ссылку на 4-й сундук
Б! - Брякли нашел свое имя.
Б* - Брякли открыл два сундука, но не нашел своего имени. Другим гномам проверять нечего.

БЗСШ Б:1-Б! З:2-З! С:3-С! Ш:4-Ш! (1)
БЗШС Б:1-Б! З:2-З! С:3-Ш->4-С! Ш:4-С->3-Ш! (2)
БСШЗ Б:1-Б! З:2-С->3-Ш*
БСЗШ Б:1-Б! З:2-С->3-З! С:3-З->2-С! Ш:4-Ш! (3)
БШЗС Б:1-Б! З:2-Ш->4-С*
БШСЗ Б:1-Б! З:2-Ш->4-З! С:3-С! Ш:4-З->2-Ш! (4)
ЗБСШ Б:1-З->2-Б! З:2-Б->1-З! С:3-С! Ш:4-Ш! (5)
ЗБШС Б:1-З->2-Б! З:2-Б->1-З! С:3-Ш->4-С! Ш:4-С->3-Ш! (6)
ЗСБШ Б:1-З->2-С*
ЗСШБ Б:1-З->2-С*
ЗШБС Б:1-З->2-Ш*
ЗШСБ Б:1-З->2-Ш*
СБЗШ Б:1-С->3-З*
СБШЗ Б:1-С->3-Ш*
СШЗБ Б:1-С->3-З*
СШБЗ Б:1-С->3-Б! З:2-Ш->4-З! С:3-Б->1-С! Ш:4-З->2-Ш! (7)
СЗБШ Б:1-С->3-Б! З:2-З! С:3-Б->1-С! Ш:4-Ш! (8 )
СЗШБ Б:1-С->3-Ш*
ШЗБС Б:1-Ш->4-С*
ШЗСБ Б:1-Ш->4-Б! З:2-З! С:3-С! Ш:4-Б->1-Ш! (9)
ШБСЗ Б:1-Ш->4-З*
ШБЗС Б:1-Ш->4-С*
ШСЗБ Б:1-Ш->4-Б! З:2-С->3-З! С:3-З->2-С! Ш:4-Б->1-Ш! (10)
ШСБЗ Б:1-Ш->4-З*

Ну вот - такая стратегия дает 10 из 24, ч.т.д.

[Antananarivu]

Dendr
Решение верное.
Можешь мне объяснить на пальцах, почему так получается? Ведь вероятность у каждого отдельного гнома найти свое имя все равно (ИМХО) составляет 50%, так?

[team55]

Наконец понял, за счёт чего гномы могут повысить вероятность выживания:

1 каждый гном знает стратегию предыдущих (и последующих) гномов
2 каждый гном оперативно меняет порядок открывания в зависимости от имени, найденного в очередном сундуке
3 на основе этого при открывании сундука гном:
а)- видя имя гнома прошедшего комнату, получает доп. инфу о местонахождении своего имени (о сундуках, в которых его нет) и о том, что предыдущий гном жив/расстрелян
б)- видя имя последующего гнома, косвенно даёт ему инфу о нахождении его имени
в)- видя своё имя, повышает шанс гномов спастись.

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

Для 2 гномов вероятность выживания - 0.5

[Antananarivu]

а)- видя имя гнома прошедшего комнату, получает доп. инфу о местонахождении своего имени (о сундуках, в которых его нет) и о том, что предыдущий гном жив/расстрелян
б)- видя имя последующего гнома, косвенно даёт ему инфу о нахождении его имени
Не согласен, как то что он видет имя гнома уже прошедшего комнату помогает ему в определении местонахождения своего имени? И какая косвенная инфа в имени последующего гнома? Не понимаю.
Как раз-таки наоборот, нашел предыдущий гном свою табличку, не нашел, для последующего гнома абсолютно не важно - он будет действовать по ранее разработанной стратегии.
И вот этого я не понимаю - для каждого из n гномов вероятность нахождения своего имени все равно 50 на 50, а в итоге для всех n получаем такую хорошую вероятность.. вернее, я понимаю, но как-то уж очень смутно, мне бы кто на пальцах показал в чем такая прелесть этой стратегии.

[Antananarivu]

Dendr
Да нет, вроде (по крайней мере, в том месте, где я нашел решение говорилось именно так) вероятность для каждого конкретного = 50%. А для всех вместе 1-ln(2). А вот почему при данной стратегии вероятность так удачно (для гномов) суммируется я никак не могу что называется "прощупать".
На том форуме кстати, так и не доказали, что это оптимальная стратегия, они там что-то пытались доработать, в общем тут вроде как вопрос еще открыт. Хотя я думаю что доказательство идеальности данной стратегии это уже вопрос скорее докторской диссертации.

[Dendr]

Dendr
Решение верное.
Можешь мне объяснить на пальцах, почему так получается? Ведь вероятность у каждого отдельного гнома найти свое имя все равно (ИМХО) составляет 50%, так?

Писал одно, но удалил, понял, что чушь несусветную написал.

Вероятность для одного гнома действительно 50%. И для второго. И для первого, и для восемьдесят четвертого.
Но кто сказал, что это независимые события?
Это даже и не условная вероятность. Это не пойми что.

А вот на пальцах... хм. Аналогия с бусами не годится?

[Antananarivu]

Dendr
Решение верное.
Можешь мне объяснить на пальцах, почему так получается? Ведь вероятность у каждого отдельного гнома найти свое имя все равно (ИМХО) составляет 50%, так?

Писал одно, но удалил, понял, что чушь несусветную написал.

Вероятность для одного гнома действительно 50%. И для второго. И для первого, и для восемьдесят четвертого.
Но кто сказал, что это независимые события?
Это даже и не условная вероятность. Это не пойми что.

А вот на пальцах... хм. Аналогия с бусами не годится?

Да я согласен, что это отнюдь не независимые события - ведь все гномы действуют по одному алгоритму. А вот "пошупать"... не знаю остается какое-то чувство недосказанности... то ли просто стереотипы мышления, то ли вот "Это даже и не условная вероятность. Это не пойми что".. я тоже не понимаю что это за вероятность такая получается? Надо будет еще попривыкнуть...
Кстати, в связи с этим, интересно для каких-нибудь игр (открытие чемоданов в одном из которых миллион, например) можно что нибудь из этого извлечь? То есть не случайно открыть чемоданы, а как-нибудь лихо... хотя нет, там же один игрок, не получится, видимо.

[Dendr]

Исправляюсь. Поспешил. Все таки условная вероятность. Просто она высокая. В частности, если первая половина гномьей команды успешно прошла испытание, то очевидно, что вторая (100%) тоже пройдет испытание.

[Dendr]

Да... что-то с объяснением "на пальцах" ничего не выходит.

Докатился в рассуждениях по поиску аналогий до Бозе-конденсата... А это... немножно не совсем на пальцах

[Versus]

Дендр - браво!

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

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

Вероятность для каждого гнома теперь равна сумме по к от 1 до n

P(n+k)*k/2n

где P(n+k) - вероятность образования цепочки длиной (n+k).


Вроде так.

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

[Antananarivu]

Не согласен! Вероятность для каждого отдельного гнома = 50%