Индукционные головоломки - Induction puzzles

Часть серии по
Загадки
Типы Гадание Загадка Ситуация Логика Рассечение Индукция Логическая сетка Самостоятельная ссылка Механический Комбинация строительство Распутывание Замок Идти проблемы Складной Придерживаться Плитка Тур Раздвижной Шахматы Лабиринт  (Логический лабиринт ) слово и Число Кроссворд Судоку Головоломки видеоигры Лабиринты Метапазлы
Темы Логические Дилемма Оптическая иллюзия Проблемы с упаковкой Парадокс Решение проблем Puzzlehunt Силлогизм мыслить творчески
Списки Невозможные головоломки Лабиринт видеоигры Типы пазлов Николи Головоломки видеоигры Темы-головоломки

Индукционные головоломки находятся логические головоломки, которые являются примерами многоагентное рассуждение, где решение развивается вместе с принципом индукция.^[1][2]

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

Типичные характерные особенности этих головоломок включают любую головоломку, в которой каждый участник имеет определенную часть информации обо всех других участниках, но не о себе. Также обычно дается какая-то подсказка, чтобы предположить, что участники могут доверять разуму друг друга - они способны теория разума.^[3]

Загадка грязных детей является наиболее часто встречающейся загадкой для индукции в научной литературе по эпистемическая логика.^[4][5] В феврале 2020 года 437 просмотров Google ученый упомянул загадку грязных детей.^[6] Пазл «Грязные дети» - это вариант хорошо известных пазлов «Мудрецы или изменщики жен / мужей».^[7]

Пазлы шляпа это вариации головоломки на индукцию, появившиеся еще в 1961 году.^[8] Во многих вариантах головоломки со шляпами описываются в контексте заключенных.^[9][10] В других случаях загадки со шляпами описываются в контексте мудрецов.^[11][12]

Загадка грязных детей

Описание

Есть набор внимательных ребят. Они думают совершенно логично. Дети считают возможным иметь мутное лицо. Ни один из детей не может сам определить состояние своего лица. Но каждый ребенок знает состояние лиц всех остальных детей. Опекун сообщает детям, что по крайней мере у одного из них грязное лицо. После этого смотритель начинает считать, и после каждого удара каждый грязный ребенок имеет возможность выйти вперед.^[4][5][13]

Логическое решение

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

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

Можно доказать, что ${ displaystyle X}$ грязные дети выйдут вперед после ${ displaystyle X}$ удары.^[4][14]

Теоретико-игровое решение

Представление Muddy Children Puzzle для двух игроков в обширная форма. Предварительный двигаться по природе окрашен в зеленый цвет. Алиса окрашена в красный цвет, а Боб - в синий. В этой игре всего один сингл равновесие по Нэшу. Действия, предсказываемые этим равновесием, окрашены в черный цвет.

Загадку грязных детей также можно решить с помощью обратная индукция из теория игры.^[13] Загадку Muddy kids можно представить в виде игра расширенной формы из несовершенная информация. У каждого игрока есть два действия - отступить и шагнуть вперед. Существует двигаться по природе в начале игры, который определяет детей с мутными лицами и без них. Дети не общаются как в некооперативные игры. Каждый удар - это одновременное движение детей. Это последовательная игра неограниченной длины. Теоретико-игровое решение требует некоторых дополнительных предположений:

1. Все дети рациональны, и вся детская рациональность всем известный факт. Это означает, что Алиса рациональна, Алиса знает, что Боб рациональный, а Алиса знает, что Боб знает, что Чарли рациональна, и так далее, и наоборот.
2. Если вы сделаете шаг вперед без грязного лица, вы получите большой штраф.
3. Если вы сделаете шаг вперед с грязным лицом, вы получите награду.
4. Каждый удар приводит к небольшому отрицательному штрафу, известному как коэффициент дисконтирования за каждого ребенка, пока кто-нибудь из них не выйдет вперед. Любое кратное меньшему наказанию всегда меньшее зло, чем большое наказание.

Если только Алиса непонятна, последнее предположение лишает ее колебаний. Если Алиса и Боб мутные, Алиса знает, что единственная причина, по которой Боб отступает после первого удара, - это опасение получить большое наказание за шаг вперед без мутного лица. В случае с ${ displaystyle X}$ грязные дети, принимающие ${ displaystyle X}$ раз меньшее наказание все же лучше, чем большое.

Головоломка Королевские мудрецы со шляпой

Описание

Король призвал к своему двору троих мудрейших людей страны, чтобы решить, кто станет его новым советником. Он надел шляпу каждому из них так, чтобы каждый мудрец мог видеть все остальные шляпы, но никто из них не мог видеть свою собственную. Каждая шляпа была белой или синей. Король дал слово мудрецам, что хотя бы один из них носит синюю шляпу; другими словами, синих шляп может быть одна, две или три, но не ноль. Король также объявил, что поединок будет справедливым для всех троих. Мудрецам также было запрещено разговаривать друг с другом. Король объявил, что тот, кто первым встанет и правильно объявит цвет своей шляпы, станет его новым советником. Мудрецы очень долго сидели, прежде чем один из них встал и правильно объявил ответ. Что он сказал и как у него получилось?

Решение

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

• Предположим, что была одна синяя шляпа. Человек в этой шляпе увидит две белые шляпы, и, поскольку король указал, что есть по крайней мере одна синяя шляпа, этот мудрец сразу узнает цвет своей шляпы. Однако двое других увидят одну синюю и одну белую шляпы и не смогут сразу вывести какую-либо информацию из своих наблюдений. Следовательно, этот сценарий нарушит указание короля о том, что состязание будет справедливым для каждого. Значит, должно быть как минимум две синих шляпы.
• Предположим, что есть две синих шляпы. Каждый мудрец в синей шляпе видел одну синюю и одну белую шляпу. Предположим, что они уже поняли, что не может быть только одной (используя предыдущий сценарий), они будут знать, что должно быть как минимум две синих шляпы, и, следовательно, сразу узнают, что на каждой из них синяя шляпа. Однако человек в белой шляпе увидит две синие шляпы и не сможет сразу вывести какую-либо информацию из своих наблюдений. Таким образом, этот сценарий также нарушит спецификацию, согласно которой конкурс будет справедливым по отношению к каждому. Значит, должно быть три синих шляпы.

Поскольку должно быть три синих шляпы, первый мужчина, который это поймет, встанет и скажет «синяя».

Альтернативное решение: это не требует правила, чтобы конкурс был справедливым по отношению к каждому. Скорее, он основан на том факте, что все они мудрые люди, и что требуется некоторое время, прежде чем они придут к решению. Может быть только 3 сценария: одна синяя шляпа, две синие шляпы или 3 синие шляпы. Если бы была только одна синяя шляпа, то владелец этой шляпы увидел бы две белые шляпы и быстро понял, что у него должна быть синяя шляпа, поэтому он бы встал и сразу объявил об этом. Поскольку этого не произошло, значит, должно быть как минимум две синих шляпы. Если бы было две синие шляпы, то любой из тех, кто носил синюю шляпу, посмотрел бы поперек и увидел бы одну синюю шляпу и одну белую шляпу, но не знал бы цвета своей шляпы. Если бы первый носитель синей шляпы предположил, что у него белая шляпа, он бы знал, что другой носитель синей шляпы увидит две белые шляпы, и, таким образом, второй носитель синей шляпы уже встал бы и объявил, что он был в синей шляпе. Таким образом, поскольку этого не произошло, первый носитель синей шляпы знал бы, что он носит синюю шляпу, и мог бы встать и объявить об этом. Так как одну или две синие шляпы так легко решить и никто не встал быстро, значит, все они должны быть в голубых шляпах.

Проблема Жозефины

Описание

В Королевстве Жозефины каждая женщина должна сдать экзамен по логике, прежде чем ей разрешат выйти замуж.^[15] Каждая замужняя женщина знает о верности каждого мужчины в Королевстве Кроме для собственного мужа, а этикет требует, чтобы ни одна женщина не рассказывала о верности мужа. Кроме того, выстрел из любого дома в Королевстве будет слышен в любом другом доме. Королева Жозефина объявила, что по крайней мере один неверный мужчина был обнаружен в Королевстве, и что любая женщина, знавшая, что ее муж неверен, должна была застрелить его в полночь на следующий день после того, как она обнаружила его неверность. Как женам это удалось?

Решение

Проблема Жозефины еще один хороший пример общего случая.

• Если неверный муж только один, то каждая женщина в Царстве знает это, кроме его жены, которая считает, что все верны. Таким образом, как только она слышит от королевы, что существуют неверные мужчины, она понимает, что ее муж, должно быть, неверен, и стреляет в него.
• Если неверных мужей двое, то обе их жены считают, что неверный муж только один (другой). Таким образом, они будут ожидать, что приведенный выше случай применим и что жена другого мужа застрелит его в полночь на следующий день. Когда не будет слышно ни одного выстрела, они поймут, что в случае выше нет применяются, таким образом, должно быть более одного неверного мужа и (поскольку они знают, что все остальные верны) дополнительный муж должен быть их собственным мужем.
• Если неверных мужей трое, каждая из их жен считает, что их всего двое, поэтому они будут ожидать, что приведенный выше случай применим, и оба мужа будут застрелены на второй день. Когда они не услышат выстрела, они поймут, что в приведенном выше случае нет Подать заявку, следовательно, неверных мужей должно быть более 2-х, и, как и прежде, их собственный муж является единственным кандидатом на роль лишнего.
• В общем, если есть п неверных мужей, каждая из их жен поверит, что п-1 и будет ожидать услышать выстрел в полночь на п-1-й день. Когда они этого не делают, они знают, что их собственный муж был птыс.

Эта проблема также известна как проблема неверных мужей, проблема неверных жен, проблема грязных детей. Логически идентичен Проблема с голубыми глазами.

Эта проблема также появляется как проблема с черными и белыми шляпами в классическом учебнике К. Л. Лю «Элементы дискретной математики».^{[нужна цитата ]}

Алиса на съезде логиков

Описание

На Тайном съезде логиков Мастер-логик надел ленту на голову каждого участника так, чтобы все остальные могли ее видеть, а сам человек - нет. Было много разных цветов ленты. Все логики сели в круг, и Учитель приказал им звонить в лес через определенные промежутки времени: в тот момент, когда логик узнал цвет на своем собственном лбу, он должен был уйти по следующему звонку. Им было сказано не разговаривать, пользоваться зеркалом или фотоаппаратом или иным образом избегать использования логики для определения цвета полосы. В случае, если на съезд проникнут самозванцы, любой, кто не уйдет вовремя, будет грубо удален в нужное время. Точно так же любого, кто попытается уйти раньше, жестоко удерживают на месте и убирают в нужное время. Учитель успокоил группу, заявив, что головоломка не будет невозможной для любого присутствующего Истинного Логика. Как они это делают?^[16]

Решение

Алиса на съезде логиков это общая индукция плюс логический скачок.

• Скачок логики: Каждый цвет должен появляться как минимум дважды по кругу. Это потому, что Мастер заявил, что ни один логик не сможет решить головоломку. Если бы какой-либо цвет существовал только один раз вокруг круга, логик, который его переносил, не имел бы возможности узнать, что этот цвет вообще существует в задаче, и они не смогли бы ответить.
• Каждый из Логиков может оглянуться по кругу и подсчитать, сколько раз они видели каждый цвет. Предположим, вы один из Логиков и видите другой цвет только один раз. Поскольку вы знаете, что каждый цвет должен существовать по крайней мере дважды по кругу, единственное объяснение одноэлементного цвета состоит в том, что это цвет вашей собственной полосы. По той же причине может быть только один такой одноэлементный цвет, поэтому вы уйдете при первом звонке.
• Точно так же любые логики, которые видят другой цвет только один раз, должны иметь возможность определить свой собственный цвет и либо уйдут с достоинством, либо будут выброшены как лазутчик. Точно так же любой цвет, для которого есть только две полосы этого цвета, будет удален после первого звонка. После этого должно остаться не менее трех полос любого оставшегося цвета.
• Предположим, вы не видите ни одного цвета один раз, но видите цвет дважды. Если бы это были единственные полосы этого цвета, то этим двум логикам следовало бы уйти при первом звонке. Поскольку они этого не сделали, это может быть только потому, что ваша собственная полоса такого же цвета, поэтому вы можете уйти после второго звонка.
• Следовательно, каждый логик будет наблюдать, пока группа определенного цвета, которую они ожидали покинуть, не уйдет. Тогда они узнают, что у них этот цвет, и уйдут по следующему звонку.
• Когда останется только один цвет, весь этот цвет уйдет на следующий колокол, потому что они будут знать, что у них не может быть другого цвета (поскольку тогда для них было бы невозможно узнать свой цвет).

Головоломка с простой шляпой

Описание

Некоторые игроки носят шляпы, которые могут быть разных цветов. Игроки могут видеть цвета, по крайней мере, шляп некоторых других игроков, но не свои собственные. С сильно ограниченным общением или без него некоторые игроки должны угадывать цвет своей шляпы. Проблема состоит в том, чтобы найти стратегию, позволяющую игрокам определять цвета своих шляп в зависимости от шляп, которые они видят, и действий других игроков. В некоторых версиях они соревнуются, чтобы первыми правильно угадать; в других случаях они могут заранее разработать стратегию сотрудничества и максимизировать вероятность правильных догадок.^[17]

Один вариант получил некоторую новую известность в результате публикации Тодда Эберта 1998 г. Кандидат наук. Тезис на Калифорнийский университет в Санта-Барбаре.^[18] Это стратегический вопрос о кооперативная игра, который связан с алгебраическая теория кодирования.^[19]

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

Все три игрока поднимают руки. После того, как игроки увидели друг друга несколько минут, не догадавшись, один игрок объявляет «красный» и побеждает. Как это сделал победитель и какого цвета у всех шляпы?

Решение

Во-первых, если бы у двоих были синие шляпы, не у всех поднялась бы рука. Затем, если бы игрок 1 видел синюю шляпу у игрока 2 и красную шляпу у игрока 3, то игрок 1 сразу знал бы, что его собственная шляпа должна быть красной. Таким образом, любой игрок, увидевший синюю шляпу, может сразу угадать. Наконец, победитель понимает, что, поскольку никто не угадает сразу, не должно быть синих шляп, поэтому каждая шляпа должна быть красной.^[20]

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

1. Подсчитайте числа б черных шляп и ш белых шляп, которые вы видите.
2. Подождите б секунд или ш секунд, в зависимости от того, что наступит раньше.
3. Если никто еще не сказал, угадайте, что ваша шляпа черная, если вы видите меньше черных шляп, чем белых, или белого, если вы видите меньше белых шляп, чем черных.
4. Если вы еще не говорили, угадайте, что ваша шляпа имеет цвет, противоположный цвету шляпы одного из первых, кто заговорил.

Предположим, что всего есть B черные шляпы и W белые шляпы. Есть три случая.

Если B = W тогда игроки в черных шляпах видят В − 1 черные шляпы и B белые шляпы, так что подождите B-1 секунда, то правильно угадайте, что они носят черную шляпу. Точно так же игроки в белой шляпе будут ждать W-1 секунда, прежде чем правильно угадать, что они носят белую шляпу. Таким образом, все игроки делают правильное предположение одновременно.

Если B < W тогда те, кто носит черную шляпу, увидят B-1 черные шляпы и W белые шляпы, а те, кто носит белую шляпу, увидят B черные шляпы и W-1 белая шляпа. С B−1 < B ≤ W−1, игроки в черной шляпе заговорят первыми, правильно угадав, что их шляпа черная. Остальные игроки правильно угадывают, что их шляпа белая.

Случай, когда W < B похож.

Вариант с двумя шляпами

Описание

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

[1]

Тюремщик сажает троих мужчин в очередь. B смотрит в стену, C смотрит на B, а D смотрит на C и B. Четвертого человека, A, помещают за ширму (или в отдельную комнату). Тюремщик дает всем четверым праздничные шляпы. Он объясняет, что есть две черные шляпы и две белые шляпы, что каждый заключенный носит одну из шляп, и что каждый из заключенных видит только шляпы перед собой, но ни на себе, ни позади него. Четвертый мужчина за ширмой не может видеть и быть невидимым для других заключенных. Общение между заключенными не допускается.

Если какой-либо заключенный может определить, какого цвета шляпа у него на голове со 100% уверенностью (без предположений), он должен объявить об этом, и все четверо заключенных выходят на свободу. Если какой-либо заключенный предлагает неправильный ответ, всех четырех заключенных казнят. Загадка состоит в том, чтобы узнать, как заключенным сбежать.

Решение

Заключенные знают, что шляп каждого цвета всего по две. Итак, если D заметит, что у B и C шляпы одного цвета, D сделает вывод, что его собственная шляпа противоположного цвета. Однако, если у B и C шляпы разного цвета, то D ничего не может сказать. Ключевым моментом является то, что заключенный C, выдержав соответствующий интервал и зная, что будет делать D, может сделать вывод, что если D ничего не говорит, шляпы на B и C должны быть разными; видя шляпу B, он может определить цвет своей шляпы.

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

Решив эту головоломку, мы сможем понять природу коммуникация можно получить, подумав, не нарушает ли осмысленное молчание заключенного D правило «Запрет на общение» (учитывая, что общение обычно определяется как «передача информации»).

Вариант с тремя шляпами

Описание

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

У этой головоломки нет 100% выигрышной стратегии, поэтому возникает вопрос: какая стратегия лучше? Какая стратегия имеет наибольшую вероятность выигрыша?

Если вы думаете о цветах шляп как о битах, у этой проблемы есть несколько важных приложений в теория кодирования.

Решение

Решение и обсуждение этой головоломки можно найти Вот (также решение аналогичной головоломки с 7 шляпами) и другие 3 варианта доступны на этом Логические головоломки страницы (их называют Мастерами логики I-IV).

Вариант с четырьмя шляпами

Описание

В варианте этой головоломки заключенные знают, что есть 3 шляпы одного цвета и только 1 шляпа другого цвета (например, 3 черных и 1 белая), и 3 заключенных могут видеть друг друга, т.е. D видит B и C, B видит D и C, а C видит D и B. (A снова не виден, и он должен носить последнюю шляпу.)

Решение

Есть два случая: в тривиальном случае один из трех заключенных носит единственную шляпу другого цвета. Каждый из двух других заключенных может видеть, что один из заключенных носит шляпу другого цвета. В нетривиальном случае все трое заключенных носят шляпы одного цвета, а А. - шляпу другого цвета. трое заключенных должны быть в состоянии сделать вывод, что, поскольку ни один из других не мог назвать цвет своей шляпы, А должен носить шляпу другого цвета.

Вариант с пятью шляпами

Описание

В другом варианте задействованы всего три заключенных и пять головных уборов (предположительно, два черных и три белых). Трем заключенным приказывают встать прямой линией лицом вперед, А впереди и С сзади. Им говорят, что будет две черные шляпы и три белые шляпы. Затем на голову каждого заключенного надевают по одной шляпе; каждый заключенный может видеть только шляпы людей перед собой, а не сам по себе. Первый заключенный, который сможет правильно объявить цвет своей шляпы, будет освобожден. Никакое общение между заключенными не допускается.

Решение

Предположим, что А носит черную шляпу:

• Если B также носит черную шляпу, C может сразу сказать, что он носит белую шляпу, посмотрев на две черные шляпы перед ним.
• Если B носит белую шляпу, C не сможет определить цвет его шляпы (потому что есть черный и белый). Таким образом, B может быстро сделать вывод из черной шляпы A и отсутствия реакции C, что он (B) носит белую шляпу.

Так что, если А носит черную шляпу, Б или С. ответят довольно быстро.

Предположим, что А носит белую шляпу:

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

В этом случае A, B и C будут хранить молчание в течение некоторого времени, пока A, наконец, не придет к выводу, что у него должна быть белая шляпа, потому что C и B молчали некоторое время.

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

Вариант с десятью шляпами

Описание

В этом варианте есть 10 заключенных и 10 головных уборов. Каждому заключенному назначается случайная шляпа, красная или синяя, но количество шляп каждого цвета заключенным не известно. Заключенные будут выстроены в одну линию, где каждый сможет видеть шляпы перед собой, но не сзади. Начиная с заключенного в конце очереди и продвигаясь вперед, каждый по очереди должен произнести только одно слово, которое должно быть «красным» или «синим». Если слово соответствует цвету их шляпы, их отпускают, если нет, их убивают на месте. Сочувствующий охранник предупреждает их об этом испытании за час до этого и говорит им, что они могут сформулировать план, согласно которому, следуя установленным правилам, 9 из 10 заключенных обязательно выживут, и у 1 будет шанс на выживание 50/50. Каков план достижения цели?

Решение

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

Вариант с десятью шляпами без слуха

Описание

Как и прежде, есть 10 заключенных и 10 головных уборов. Каждому заключенному назначается случайная шляпа, красная или синяя, но количество шляп каждого цвета заключенным не известно. Заключенных распределяют по комнате таким образом, чтобы они могли видеть шляпы других, но не свои. Теперь каждый из них должен одновременно произнести только одно слово, которое должно быть «красным» или «синим». Если слово соответствует цвету их шляпы, их отпускают, и если достаточное количество заключенных вернутся на свободу, они могут спасти остальных. Сочувствующий охранник предупреждает их об этом испытании за час до этого. Если они смогут сформулировать план в соответствии с установленными правилами, 5 из 10 заключенных обязательно будут освобождены и смогут спасти остальных. Каков план достижения цели?

Решение

Заключенные разделяются на пары. В паре (A, B) заключенных A говорит цвет, который он видит на голове B, который говорит противоположный цвет, который он видит на голове A. Тогда, если оба носят шляпы одного цвета, A является выпущен (а B нет), если цвета разные, B выпущен (а A нет). Всего правильно ответили 5 заключенных и нет. Это предполагает, что пара может сообщать, кто является A, а кто B, что может быть запрещено.

В качестве альтернативы заключенные строят две группы по 5. Одна группа предполагает, что количество красных шляп четное, а другая предполагает, что количество красных шляп нечетное. Как и в случае со слухом, они могут определить цвет своей шляпы из этого предположения. Право будет ровно одна группа, значит, правильно ответят 5 заключенных, а 5 нет.

Обратите внимание, что заключенные не могут найти стратегии, гарантирующей освобождение более 5 заключенных.Действительно, для одного заключенного существует столько же цветов шляп, когда он говорит правильный ответ, чем там, где он этого не делает. Следовательно, существует столько же распределений цветов шляп, когда 6 или более заключенных говорят правильный ответ, чем когда 4 или меньше делают это.

Счетный вариант бесконечной шляпы без слуха

Описание

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

Решение

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

Заключенные, стоящие в очереди, образуют последовательность из нулей и единиц, где 0 означает синий цвет, а 1 - красный. Прежде чем их посадят в очередь, заключенные определяют следующее: отношение эквивалентности по всем возможным последовательностям, в которые они могут быть помещены: две последовательности эквивалентны, если они идентичны после конечного числа записей. Из этого отношения эквивалентности заключенные получают набор классов эквивалентности. Предполагая аксиому выбора, существует набор репрезентативных последовательностей - по одной от каждого класса эквивалентности. (Почти каждое конкретное значение невозможно вычислить, но из выбранной аксиомы следует, что немного набор значений существует, поэтому мы предполагаем, что заключенные имеют доступ к оракул.)

Когда их помещают в свою очередь, каждый заключенный может видеть все шляпы, кроме конечного числа, и, следовательно, может видеть, какой класс эквивалентности соответствует действительный последовательность шляп принадлежит. (Это предполагает, что каждый заключенный может выполнить бесчисленное множество количество сравнений, чтобы найти совпадение, причем для каждого сравнения классов требуется счетно бесконечный количество индивидуальных сравнений шляп). Затем они продолжают угадывать цвет своей шляпы, как если бы они представитель последовательность из соответствующего класса эквивалентности. Поскольку фактическая последовательность и репрезентативная последовательность находятся в одном классе эквивалентности, их записи одинаковы после некоторого конечного числа N заключенных. Все заключенные после этих первых N заключенные спасены.

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

Чтобы убедиться в этом, рассмотрим случай с нулевым количеством убитых заключенных. Это случилось если и только если фактическая последовательность является одной из выбранных репрезентативных последовательностей. Если последовательности нулей и единиц рассматривать как двоичные представления действительного числа от 0 до 1, репрезентативные последовательности образуют неизмеримое множество. (Этот набор похож на Виталий набор с той лишь разницей, что классы эквивалентности формируются по отношению к числам с конечным двоичным представлением, а не ко всем рациональным числам.) Следовательно, никакая вероятность не может быть присвоена событию, когда будет убито ноль заключенных. Аргумент аналогичен для другого конечного числа убиваемых заключенных, что соответствует конечному количеству вариантов каждого представителя.

Счетно бесконечная шляпа Проблема со слухом

Описание

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

Решение

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

Для этого мы определяем то же отношение эквивалентности, что и выше, и снова выбираем репрезентативную последовательность из каждого класса эквивалентности. Теперь мы помечаем каждую последовательность в каждом классе либо 0, либо 1. Сначала мы помечаем репрезентативную последовательность нулем. Затем мы маркируем любую последовательность, которая отличается от репрезентативной последовательности в четном количестве мест, с помощью 0, и любая последовательность, которая отличается от репрезентативной последовательности на нечетное количество мест, на единицу. Таким образом, мы пометили каждую возможную бесконечную последовательность цифрой 0 или 1 с тем важным свойством, что любые две последовательности, которые отличаются только одной цифрой имеют противоположные метки.

Теперь, когда надзиратель просит первого человека назвать цвет, или, в нашей новой интерпретации, 0 или 1, он просто называет название последовательности, которую видит. Учитывая эту информацию, каждый после него может определить, какого именно цвета его шляпа. Второй человек видит все, кроме первой цифры последовательности, которую видит первый человек. Таким образом, насколько ему известно, есть две возможные последовательности, которые мог бы обозначать первый человек: одна, начинающаяся с 0, и одна, начинающаяся с 1. Из-за нашей схемы маркировки эти две последовательности будут получать противоположные метки, поэтому на основе на основании того, что говорит первый человек, второй человек может определить, какую из двух возможных ниток увидел первый человек, и, таким образом, он может определить свой собственный цвет шляпы. Точно так же каждый последующий человек в очереди знает каждую цифру последовательности, кроме той, которая соответствует его собственному цвету шляпы. Он знает тех, кто был до него, потому что они были вызваны, и тех, кто после него, потому что он может их видеть. Обладая этой информацией, он может использовать метку, названную первым человеком, чтобы определить цвет своей шляпы. Таким образом, все, кроме первого, всегда угадывают правильно.

Версия Эберта и коды Хэмминга

Описание

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

Решение

Одна из стратегий решения этой версии проблемы шляпы предполагает использование Коды Хэмминга, которые обычно используются для обнаружения и исправления ошибок в передача данных. Вероятность выигрыша будет намного выше 50%, в зависимости от количества игроков в конфигурации головоломки: например, вероятность выигрыша 87,5% для 7 игроков.

Подобные стратегии могут быть применены к размеру команды N = 2^k−1 и достичь винрейта (2^k-1)/2^k. Таким образом, стратегия кода Хэмминга дает больший процент выигрышей для больших значений N.

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

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

Игроки могут гарантировать, что они выиграют в последних случаях (75% случаев), используя следующую стратегию:

1. Любой игрок, увидевший две шляпы двух разных цветов, молчит.
2. Любой игрок, увидевший две шляпы одного цвета, угадывает противоположный цвет.

В двух случаях, когда все три игрока имеют одинаковый цвет шляпы, все они угадывают неправильно. Но в остальных шести случаях только один игрок догадается, и правильно, что его шляпа противоположна шляпе других игроков.^[21]

Дома Снитчвилля

Описание

Снитчи - существа из знаменитого рассказа доктора Сьюза «Снитчи». Есть два типа Снитчей: звездно-пузатый и пузатый. Все Снитчи должны пройти тест на логику, чтобы жить в Снитчвилле, который имеет ограниченное количество домов и имеет строгий жилищный закон, согласно которому в каждом доме должно быть не более одного звездного Снетча и одного пузатого Снитча. Ни один Снитч не может видеть свой живот, но все еще может видеть животы всех других Снитчей. Чтобы предотвратить дальнейшие конфликты между Снитчами, существует закон, запрещающий Снитче обсуждать свои животы. Каждый Sneetch не может пропустить дом, пока не будет уверен, что он не может войти в него. Если Sneetch нарушает закон, он выполняется. Как Снитчи выбирают себе жилище?^[22]

Решение

Поскольку все Sneetches потенциально подвержены риску, одно решение для всех Sneetches - встретиться на улице; модель указывает дома, то есть дорогу, улицу или близко. Там они соглашаются двигаться в сторону Снитчей, которые выглядят похожими, и от Снитчей, которые выглядят непохожими; это избавляет от необходимости специально сообщать о физических характеристиках, то есть о состоянии живота. Движение Sneetch начинается с Броуновское движение но, как и в логике проблемы грязных детей, это превращается в скопление, например, когда один Sneetch движется к двум одинаковым ухищрениям, которые они принимают или отвергают, или наоборот, и в конечном итоге пространство состояний Результаты двух групп, пузатых и пузатых. Один Sneetch из первой группы идет сначала в каждый дом, затем один Sneetch из второй группы идет в каждый дом.

Смотрите также

• Эпистемическая логика
• Общие знания (логика)

Рекомендации