Хабр Курсы для всех
РЕКЛАМА
Большая витрина: от крупнейших школ до частных авторов. Сравнивайте по цене, длительности, формату и выбирайте самый подходящий курс!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 57
Задавать такую задачку и в ПЯТНИЦУ это верх кощунства :)
Им надо договориться открывать коробки с 1 по 15 и, если меня не подводит «пятничный мозг», выживет ровно 50% узников.
хм
— узники не получают никакой дополнительной информации после того, как очередной из них посетил комнату
— для каждого следующего узника комната выглядит точно также как и раньше
получается, просто 30 раз повторяется опыт «выживание узника в 50% случаев»… Задачу решить нельзя?
— узники не получают никакой дополнительной информации после того, как очередной из них посетил комнату
— для каждого следующего узника комната выглядит точно также как и раньше
получается, просто 30 раз повторяется опыт «выживание узника в 50% случаев»… Задачу решить нельзя?
Они знают, как действовали предыдущие в случае «для узника N в коробке M лежит ключ K». Плюс они могут верить в то, что все предыдущие свой ключ нашли (надо просто посчитать соответствующую вероятность)… Так что все не так просто.
Плюс они могут верить в то, что все предыдущие свой ключ нашли
У меня в голове борются две в меру противоположные мысли:
1) мне всё-таки не зря поставили тройку на экзамене по терверу за один из семестров
2) задача составлена в полном соответствии с принципами третего вида лжи.
наверное, я не совсем удачно выразился. мы рассматриваем случай, что все нашли свои ключи, и считаем вероятность этого случая. поэтому логично, что в нашем, «хорошем» случае, мы полагаемся на благоприятный исход всех предыдущих (с некоторой вероятностью, конечно).
Если меня не подводит логика, то задача эквивалентна случаю, когда мы имеем 30 одинаковых комнат и 30 узников с разными номерами от 1 до 30, которые одновременно заходят в эти комнаты.
Таким образом, фраза про предположения узников про предыдущие случаи звучит немного бессмысленно.
Таким образом, фраза про предположения узников про предыдущие случаи звучит немного бессмысленно.
боюсь, что подводит. узники не только «заходят в комнаты», но имеют 15 попыток и в зависимости от своего номера и обнаруженного номера в комнате могут решить, куда идти дальше. алгоритм знают все, т.е. каждый чувак знает, куда бы пошел дальше такой-то узник… и использует информацию о том, что в итоге каждый из 30 свой ключ нашел.
Эм-м… Про алгоритм они договариваются заранее, не так ли? Алгоритм, таким образом, у всех один. Отличается лишь единственный параметр этого алгоритма — номер узника. Нет?
Я правда не понимаю, чем отличается 30 параллельно работающих узников от 30 последовательно работающих узников в условиях этой задачи.
Я правда не понимаю, чем отличается 30 параллельно работающих узников от 30 последовательно работающих узников в условиях этой задачи.
м… я не понял вас, а вы, похоже, меня, и мы спорим ни о чём :) да, 30 одинаковых комнат. да, 30 узников. да, одновременно. НО. каждый из них, открыв коробку, знает, к какой бы коробке пошел бы любой другой, если бы открыл эту же коробку. именно это я неудачно и назвал предыдущим случаем.
Мне почему то кажется что ему это знание ничего не даст. Или удачливый узник забирает свой ключ?
ключ конечно остаётся на месте. возможно, это знание ничего не даст. но то, что они могут договориться, кто и куда смотрит, явно полезно, например, в совсем-совсем примитивном случае: два ящика, два узника, одна попытка.
если не договариваться — вероятность 1/2 * 1/2 = 1/4.
если договориться, что первый всегда смотрит первую коробку, а второй вторую — то 1/2.
если не договариваться — вероятность 1/2 * 1/2 = 1/4.
если договориться, что первый всегда смотрит первую коробку, а второй вторую — то 1/2.
да ну…
> Ключи по коробкам распределены совершенно случайно
следовательно, если первый будет всегда смотреть первую коробку, у него вероятность выжить 1/2, так же как и у второго со второй коробкой.
1/2 * 1/2 = 1/4, собственно, никуда не денешся
> Ключи по коробкам распределены совершенно случайно
следовательно, если первый будет всегда смотреть первую коробку, у него вероятность выжить 1/2, так же как и у второго со второй коробкой.
1/2 * 1/2 = 1/4, собственно, никуда не денешся
Если ключ никуда не перемещается, им достаточно всем открыть коробки с первой по пятнадцатую. Вероятность для всей кучи будет 0.5 — ключ во всех вариантах будет либо в первой половине коробок, либо во второй.
А не придумать ли вам алгоритм того, как соединить три колодца и три дома непересекающимися тропинками так, что каждый дом соединён с каждым колодцем? :-)
Ещё одна задача про узников. На этот раз не такая теоретическая.Да уж, террористы при захвате заложников обычно действуют так, как описано в задаче. Так что в жизни точно может пригодиться!
А какой смысл о чем-то договариваться, если все коробки постоянно приводят в изначальное состояние и о судьбе того, кто был в комнате ничего не известно?
Мне пока только один вариант алгоритма приходит в голову: каждый из них первой открывает коробку со своим номером, а в дальнейшем открывает коробку с номером ключа, который он нашел в предыдущей.
Вот только ума не приложу, как посчитать вероятность для этого алгоритма.
Вот только ума не приложу, как посчитать вероятность для этого алгоритма.
Набросал скриптик прогоняющий этот алгоритм и считающий вероятность.
Судя по его результатам алгоритм верный, вот только обосновать его вечером в пятницу не получается :) Попробуем завтра с утра
Судя по его результатам алгоритм верный, вот только обосновать его вечером в пятницу не получается :) Попробуем завтра с утра
Достаточно просто смоделировать. К такой модели я сам пришёл, ещё до прочтения вашего комментария.
Строим ориентированный граф. Каждая вершина — коробка, дуга — ключ в коробке. То есть, если у нас в коробке №1 ключ №2, то у нас есть дуга 1->2. Можно даже перейти к неориентированному графу, тут не важно, как я сейчас подумал. В итоге получим псевдограф (могут быть петли, вида 1-1, если ключ лежит в соответствующей коробке). Кто-то гибнет, если у нас есть цикл длиннее 15. Если все циклы короче или равны 15, то человек изначально находится в компоненте связности своего ключа и доходит по дугам до него. Теперь нужно оценить их число, а для этого я хотя бы бумагу возьму и подумаю, я же не Чарли Эппс, чтобы в голове сразу и это смоделировать :)
Строим ориентированный граф. Каждая вершина — коробка, дуга — ключ в коробке. То есть, если у нас в коробке №1 ключ №2, то у нас есть дуга 1->2. Можно даже перейти к неориентированному графу, тут не важно, как я сейчас подумал. В итоге получим псевдограф (могут быть петли, вида 1-1, если ключ лежит в соответствующей коробке). Кто-то гибнет, если у нас есть цикл длиннее 15. Если все циклы короче или равны 15, то человек изначально находится в компоненте связности своего ключа и доходит по дугам до него. Теперь нужно оценить их число, а для этого я хотя бы бумагу возьму и подумаю, я же не Чарли Эппс, чтобы в голове сразу и это смоделировать :)
Итак, продолжаем. Так как мы бьём на компоненты связности, то задача сводится к подсчёту вариантов разбиения множества из 30 элементов на подмножества. Это полное множество вариантов. «Несчастливое» множество — это те разбиения, где есть подмножество мощности > 15. Полное число я смог оценить, а вот «несчастливое» — пока не получилось, то есть — не получилось доказать, что я по ходу решения не теряю варианты. Продолжаю думать, если у кого есть идеи — сообщайте. Алгоритм кажется максимально достоверным, так как только такой вариант может зацепляться за номера и их соответствие.
Это для каждого вероятность выжить должна быть 0.9606622132952272. Честно говоря, даже не знаю как бы это провернуть.
Как уже сказал «Buben» выше, им нужно договорится открывать коробки с номерами с 1 по 15 (или любой другой одинаковый для всех набор из 15-ти коробок), тогда вероятность выживания будет 50% для всех узников.
причём, открывая очередную коробку, он может сначала посмотреть, какой в ней ключ, а потом решить, какую открывать следующей.
имеем номер текущей коробки — номер ключа в текущей коробке. свой собственный номер. следующий выбор должен основываться только на этих данных.
надо чайку попить, а то совсем не соображаю что-то
Каждый четный узник открывает каждую первую коробку
Каждый нечетный узник открывает каждую вторую коробку
Вероятность открытия каждым узником нужной коробки — 50%
Так что есть вероятность 50% что выживут все
А те кто не выжили — ЖАЛКИЕ НЕУДАЧНИКИ
:)
Каждый нечетный узник открывает каждую вторую коробку
Вероятность открытия каждым узником нужной коробки — 50%
Так что есть вероятность 50% что выживут все
А те кто не выжили — ЖАЛКИЕ НЕУДАЧНИКИ
:)
А туплю сильно, но мне кажется, если переформулировать задачу таким образом:
«Если хоть один заключенный не находит свой ключ, то расстреливают всех. Доказать, что при правильной стратегии вероятность выжить всем = не менее 30%, и найти эту стратегию.» то суть остаётся той же, но условие — более законченным. Теперь буду думать.
«Если хоть один заключенный не находит свой ключ, то расстреливают всех. Доказать, что при правильной стратегии вероятность выжить всем = не менее 30%, и найти эту стратегию.» то суть остаётся той же, но условие — более законченным. Теперь буду думать.
Кажется вы очень странно сформулировали условие.
Если узники не получают никакой информации о судьбе предыдущего, а нахождение ключа во всех коробках равновероятно, то конечно же это 50% для каждого узника
Если узники не получают никакой информации о судьбе предыдущего, а нахождение ключа во всех коробках равновероятно, то конечно же это 50% для каждого узника
Итак решение.
(первым алгоритм предложил Sandrique, ближе всего к правильной оценке подобрался 0leGG, но всё-таки не доказал, что алгоритм работает правильно)
Алгоритм такой: каждый узник открывает коробку со своим же номером, смотрит какой ключ там и открывает коробку с номером этого ключа, достаёт новый ключ и открывает коробку с номером нового ключа, и так далее. Если ему в какой-то момент надо будет открыть коробку, которую он уже открывал, это значит, что он уже обошёл весь цикл, и значит (т.к. начинал со своего номера), нашёл и свой ключ.
Доказательство корректности:
Действительно, как правильно заметил 0leGG, кто-то из узников умрёт, только если в перестановке ключей в коробках есть цикл длинее 15. Подсчитаем вероятность этого. Для этого найдём количество (и вероятность) перестановок из n элементов (n=30) с циклом длины k (k>n/2=15). Элементы для цикла можно выбрать Cnk способами, составить из них цикл можно (k-1)! способами, остальные элементы можно переставить (n-k)! способами. Всего перестановок n!.. Значит, вероятность таких перестановок равна
Cnk * (k-1)! * (n-k)! / n! = n! / (k! * (n-k)!) * (k-1)! * (n-k)! / n! = 1/k.
Теперь для подсчёта суммарной вероятности надо просуммировать по k от 16 до 30 и (воспользовавшись калькулятором или ещё чем-нибудь) оценить сумму:
1/16 + 1/17 +… + 1/30 < 0.7
Значит, с вероятность больше 30% никто не умрёт.
(первым алгоритм предложил Sandrique, ближе всего к правильной оценке подобрался 0leGG, но всё-таки не доказал, что алгоритм работает правильно)
Алгоритм такой: каждый узник открывает коробку со своим же номером, смотрит какой ключ там и открывает коробку с номером этого ключа, достаёт новый ключ и открывает коробку с номером нового ключа, и так далее. Если ему в какой-то момент надо будет открыть коробку, которую он уже открывал, это значит, что он уже обошёл весь цикл, и значит (т.к. начинал со своего номера), нашёл и свой ключ.
Доказательство корректности:
Действительно, как правильно заметил 0leGG, кто-то из узников умрёт, только если в перестановке ключей в коробках есть цикл длинее 15. Подсчитаем вероятность этого. Для этого найдём количество (и вероятность) перестановок из n элементов (n=30) с циклом длины k (k>n/2=15). Элементы для цикла можно выбрать Cnk способами, составить из них цикл можно (k-1)! способами, остальные элементы можно переставить (n-k)! способами. Всего перестановок n!.. Значит, вероятность таких перестановок равна
Cnk * (k-1)! * (n-k)! / n! = n! / (k! * (n-k)!) * (k-1)! * (n-k)! / n! = 1/k.
Теперь для подсчёта суммарной вероятности надо просуммировать по k от 16 до 30 и (воспользовавшись калькулятором или ещё чем-нибудь) оценить сумму:
1/16 + 1/17 +… + 1/30 < 0.7
Значит, с вероятность больше 30% никто не умрёт.
Эта задача выносит мой мозг. Вот не понимаю я, как работает это решение.
Если узник, войдя в комнату, заранее решает, какие 15 коробок он намеревается открыть, вероятность найти свой ключ для него одного, очевидно, будет 1/2. Приведённый алгоритм, однако, даёт способ выжить всем c вероятностью 0.6767581376913977, а значит вероятность отдельного взятого узника найти свой ключ ещё больше. Значит информация о номере ключа в только что открытой коробке позволяет скорректировать маршрут, выбрать более выгодный, иначе говоря узник каким-то образом при этом узнаёт, в каких из оставшихся коробок нахождение нужного ключа более вероятно. Вот тут наступает когнитивный диссонанс и полное несоответствие с тем, как я себе представляю отношения между вероятностью и информацией. Ведь номера ключей и коробок по условию никак между собой не коррелируют, и ключ может сообщить узнику только то, что в других коробках его нет!
ЗЫ: Привет.
Если узник, войдя в комнату, заранее решает, какие 15 коробок он намеревается открыть, вероятность найти свой ключ для него одного, очевидно, будет 1/2. Приведённый алгоритм, однако, даёт способ выжить всем c вероятностью 0.6767581376913977, а значит вероятность отдельного взятого узника найти свой ключ ещё больше. Значит информация о номере ключа в только что открытой коробке позволяет скорректировать маршрут, выбрать более выгодный, иначе говоря узник каким-то образом при этом узнаёт, в каких из оставшихся коробок нахождение нужного ключа более вероятно. Вот тут наступает когнитивный диссонанс и полное несоответствие с тем, как я себе представляю отношения между вероятностью и информацией. Ведь номера ключей и коробок по условию никак между собой не коррелируют, и ключ может сообщить узнику только то, что в других коробках его нет!
ЗЫ: Привет.
Привет.
Для начала, вероятность выжить всем не 0.6767581376913977, а 1 — 0.6767581376913977 < 0.5. Дело в том, что если считать смерти узников независимыми событиями, то общая вероятность получилась бы 2-30. А такая стратегия делает эти события сильно зависимыми, отчего и получается такой результат.
Для начала, вероятность выжить всем не 0.6767581376913977, а 1 — 0.6767581376913977 < 0.5. Дело в том, что если считать смерти узников независимыми событиями, то общая вероятность получилась бы 2-30. А такая стратегия делает эти события сильно зависимыми, отчего и получается такой результат.
Знаю задачку :)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Узники и коробки