Comments 57
Задавать такую задачку и в ПЯТНИЦУ это верх кощунства :)
+3
UFO just landed and posted this here
Им надо договориться открывать коробки с 1 по 15 и, если меня не подводит «пятничный мозг», выживет ровно 50% узников.
0
хм
— узники не получают никакой дополнительной информации после того, как очередной из них посетил комнату
— для каждого следующего узника комната выглядит точно также как и раньше
получается, просто 30 раз повторяется опыт «выживание узника в 50% случаев»… Задачу решить нельзя?
— узники не получают никакой дополнительной информации после того, как очередной из них посетил комнату
— для каждого следующего узника комната выглядит точно также как и раньше
получается, просто 30 раз повторяется опыт «выживание узника в 50% случаев»… Задачу решить нельзя?
0
Они знают, как действовали предыдущие в случае «для узника N в коробке M лежит ключ K». Плюс они могут верить в то, что все предыдущие свой ключ нашли (надо просто посчитать соответствующую вероятность)… Так что все не так просто.
0
Плюс они могут верить в то, что все предыдущие свой ключ нашли
У меня в голове борются две в меру противоположные мысли:
1) мне всё-таки не зря поставили тройку на экзамене по терверу за один из семестров
2) задача составлена в полном соответствии с принципами третего вида лжи.
0
наверное, я не совсем удачно выразился. мы рассматриваем случай, что все нашли свои ключи, и считаем вероятность этого случая. поэтому логично, что в нашем, «хорошем» случае, мы полагаемся на благоприятный исход всех предыдущих (с некоторой вероятностью, конечно).
0
Если меня не подводит логика, то задача эквивалентна случаю, когда мы имеем 30 одинаковых комнат и 30 узников с разными номерами от 1 до 30, которые одновременно заходят в эти комнаты.
Таким образом, фраза про предположения узников про предыдущие случаи звучит немного бессмысленно.
Таким образом, фраза про предположения узников про предыдущие случаи звучит немного бессмысленно.
0
боюсь, что подводит. узники не только «заходят в комнаты», но имеют 15 попыток и в зависимости от своего номера и обнаруженного номера в комнате могут решить, куда идти дальше. алгоритм знают все, т.е. каждый чувак знает, куда бы пошел дальше такой-то узник… и использует информацию о том, что в итоге каждый из 30 свой ключ нашел.
0
Эм-м… Про алгоритм они договариваются заранее, не так ли? Алгоритм, таким образом, у всех один. Отличается лишь единственный параметр этого алгоритма — номер узника. Нет?
Я правда не понимаю, чем отличается 30 параллельно работающих узников от 30 последовательно работающих узников в условиях этой задачи.
Я правда не понимаю, чем отличается 30 параллельно работающих узников от 30 последовательно работающих узников в условиях этой задачи.
0
м… я не понял вас, а вы, похоже, меня, и мы спорим ни о чём :) да, 30 одинаковых комнат. да, 30 узников. да, одновременно. НО. каждый из них, открыв коробку, знает, к какой бы коробке пошел бы любой другой, если бы открыл эту же коробку. именно это я неудачно и назвал предыдущим случаем.
0
Мне почему то кажется что ему это знание ничего не даст. Или удачливый узник забирает свой ключ?
0
ключ конечно остаётся на месте. возможно, это знание ничего не даст. но то, что они могут договориться, кто и куда смотрит, явно полезно, например, в совсем-совсем примитивном случае: два ящика, два узника, одна попытка.
если не договариваться — вероятность 1/2 * 1/2 = 1/4.
если договориться, что первый всегда смотрит первую коробку, а второй вторую — то 1/2.
если не договариваться — вероятность 1/2 * 1/2 = 1/4.
если договориться, что первый всегда смотрит первую коробку, а второй вторую — то 1/2.
0
да ну…
> Ключи по коробкам распределены совершенно случайно
следовательно, если первый будет всегда смотреть первую коробку, у него вероятность выжить 1/2, так же как и у второго со второй коробкой.
1/2 * 1/2 = 1/4, собственно, никуда не денешся
> Ключи по коробкам распределены совершенно случайно
следовательно, если первый будет всегда смотреть первую коробку, у него вероятность выжить 1/2, так же как и у второго со второй коробкой.
1/2 * 1/2 = 1/4, собственно, никуда не денешся
0
Если ключ никуда не перемещается, им достаточно всем открыть коробки с первой по пятнадцатую. Вероятность для всей кучи будет 0.5 — ключ во всех вариантах будет либо в первой половине коробок, либо во второй.
0
А не придумать ли вам алгоритм того, как соединить три колодца и три дома непересекающимися тропинками так, что каждый дом соединён с каждым колодцем? :-)
+3
Ещё одна задача про узников. На этот раз не такая теоретическая.Да уж, террористы при захвате заложников обычно действуют так, как описано в задаче. Так что в жизни точно может пригодиться!
0
А какой смысл о чем-то договариваться, если все коробки постоянно приводят в изначальное состояние и о судьбе того, кто был в комнате ничего не известно?
0
Мне пока только один вариант алгоритма приходит в голову: каждый из них первой открывает коробку со своим номером, а в дальнейшем открывает коробку с номером ключа, который он нашел в предыдущей.
Вот только ума не приложу, как посчитать вероятность для этого алгоритма.
Вот только ума не приложу, как посчитать вероятность для этого алгоритма.
0
Достаточно просто смоделировать. К такой модели я сам пришёл, ещё до прочтения вашего комментария.
Строим ориентированный граф. Каждая вершина — коробка, дуга — ключ в коробке. То есть, если у нас в коробке №1 ключ №2, то у нас есть дуга 1->2. Можно даже перейти к неориентированному графу, тут не важно, как я сейчас подумал. В итоге получим псевдограф (могут быть петли, вида 1-1, если ключ лежит в соответствующей коробке). Кто-то гибнет, если у нас есть цикл длиннее 15. Если все циклы короче или равны 15, то человек изначально находится в компоненте связности своего ключа и доходит по дугам до него. Теперь нужно оценить их число, а для этого я хотя бы бумагу возьму и подумаю, я же не Чарли Эппс, чтобы в голове сразу и это смоделировать :)
Строим ориентированный граф. Каждая вершина — коробка, дуга — ключ в коробке. То есть, если у нас в коробке №1 ключ №2, то у нас есть дуга 1->2. Можно даже перейти к неориентированному графу, тут не важно, как я сейчас подумал. В итоге получим псевдограф (могут быть петли, вида 1-1, если ключ лежит в соответствующей коробке). Кто-то гибнет, если у нас есть цикл длиннее 15. Если все циклы короче или равны 15, то человек изначально находится в компоненте связности своего ключа и доходит по дугам до него. Теперь нужно оценить их число, а для этого я хотя бы бумагу возьму и подумаю, я же не Чарли Эппс, чтобы в голове сразу и это смоделировать :)
0
Итак, продолжаем. Так как мы бьём на компоненты связности, то задача сводится к подсчёту вариантов разбиения множества из 30 элементов на подмножества. Это полное множество вариантов. «Несчастливое» множество — это те разбиения, где есть подмножество мощности > 15. Полное число я смог оценить, а вот «несчастливое» — пока не получилось, то есть — не получилось доказать, что я по ходу решения не теряю варианты. Продолжаю думать, если у кого есть идеи — сообщайте. Алгоритм кажется максимально достоверным, так как только такой вариант может зацепляться за номера и их соответствие.
0
Это для каждого вероятность выжить должна быть 0.9606622132952272. Честно говоря, даже не знаю как бы это провернуть.
+1
Как уже сказал «Buben» выше, им нужно договорится открывать коробки с номерами с 1 по 15 (или любой другой одинаковый для всех набор из 15-ти коробок), тогда вероятность выживания будет 50% для всех узников.
0
причём, открывая очередную коробку, он может сначала посмотреть, какой в ней ключ, а потом решить, какую открывать следующей.
имеем номер текущей коробки — номер ключа в текущей коробке. свой собственный номер. следующий выбор должен основываться только на этих данных.
надо чайку попить, а то совсем не соображаю что-то
0
Каждый четный узник открывает каждую первую коробку
Каждый нечетный узник открывает каждую вторую коробку
Вероятность открытия каждым узником нужной коробки — 50%
Так что есть вероятность 50% что выживут все
А те кто не выжили — ЖАЛКИЕ НЕУДАЧНИКИ
:)
Каждый нечетный узник открывает каждую вторую коробку
Вероятность открытия каждым узником нужной коробки — 50%
Так что есть вероятность 50% что выживут все
А те кто не выжили — ЖАЛКИЕ НЕУДАЧНИКИ
:)
-4
А туплю сильно, но мне кажется, если переформулировать задачу таким образом:
«Если хоть один заключенный не находит свой ключ, то расстреливают всех. Доказать, что при правильной стратегии вероятность выжить всем = не менее 30%, и найти эту стратегию.» то суть остаётся той же, но условие — более законченным. Теперь буду думать.
«Если хоть один заключенный не находит свой ключ, то расстреливают всех. Доказать, что при правильной стратегии вероятность выжить всем = не менее 30%, и найти эту стратегию.» то суть остаётся той же, но условие — более законченным. Теперь буду думать.
0
Кажется вы очень странно сформулировали условие.
Если узники не получают никакой информации о судьбе предыдущего, а нахождение ключа во всех коробках равновероятно, то конечно же это 50% для каждого узника
Если узники не получают никакой информации о судьбе предыдущего, а нахождение ключа во всех коробках равновероятно, то конечно же это 50% для каждого узника
0
Итак решение.
(первым алгоритм предложил 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% никто не умрёт.
0
Эта задача выносит мой мозг. Вот не понимаю я, как работает это решение.
Если узник, войдя в комнату, заранее решает, какие 15 коробок он намеревается открыть, вероятность найти свой ключ для него одного, очевидно, будет 1/2. Приведённый алгоритм, однако, даёт способ выжить всем c вероятностью 0.6767581376913977, а значит вероятность отдельного взятого узника найти свой ключ ещё больше. Значит информация о номере ключа в только что открытой коробке позволяет скорректировать маршрут, выбрать более выгодный, иначе говоря узник каким-то образом при этом узнаёт, в каких из оставшихся коробок нахождение нужного ключа более вероятно. Вот тут наступает когнитивный диссонанс и полное несоответствие с тем, как я себе представляю отношения между вероятностью и информацией. Ведь номера ключей и коробок по условию никак между собой не коррелируют, и ключ может сообщить узнику только то, что в других коробках его нет!
ЗЫ: Привет.
Если узник, войдя в комнату, заранее решает, какие 15 коробок он намеревается открыть, вероятность найти свой ключ для него одного, очевидно, будет 1/2. Приведённый алгоритм, однако, даёт способ выжить всем c вероятностью 0.6767581376913977, а значит вероятность отдельного взятого узника найти свой ключ ещё больше. Значит информация о номере ключа в только что открытой коробке позволяет скорректировать маршрут, выбрать более выгодный, иначе говоря узник каким-то образом при этом узнаёт, в каких из оставшихся коробок нахождение нужного ключа более вероятно. Вот тут наступает когнитивный диссонанс и полное несоответствие с тем, как я себе представляю отношения между вероятностью и информацией. Ведь номера ключей и коробок по условию никак между собой не коррелируют, и ключ может сообщить узнику только то, что в других коробках его нет!
ЗЫ: Привет.
0
Привет.
Для начала, вероятность выжить всем не 0.6767581376913977, а 1 — 0.6767581376913977 < 0.5. Дело в том, что если считать смерти узников независимыми событиями, то общая вероятность получилась бы 2-30. А такая стратегия делает эти события сильно зависимыми, отчего и получается такой результат.
Для начала, вероятность выжить всем не 0.6767581376913977, а 1 — 0.6767581376913977 < 0.5. Дело в том, что если считать смерти узников независимыми событиями, то общая вероятность получилась бы 2-30. А такая стратегия делает эти события сильно зависимыми, отчего и получается такой результат.
0
Знаю задачку :)
0
Sign up to leave a comment.
Articles
Change theme settings
Узники и коробки