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

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

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

Типичные контрольные особенности этих головоломок включают в себя любую головоломку, в которой каждый участник имеет определенную информацию (обычно как общеизвестную ) обо всех других участниках, но не о себе. Кроме того, обычно дается своего рода намек на то, что участники могут доверять интеллекту друг друга — они способны к теории разума (то, что «каждый участник знает modus ponens », общеизвестно). ^[3] Кроме того, бездействие участника — это невербальное сообщение об отсутствии у этого участника знаний, которое затем становится общеизвестным для всех участников, наблюдавших за бездействием.

Головоломка «грязные дети» — наиболее часто встречающаяся в научной литературе по эпистемической логике индукционная головоломка . ^[4]^[5]^[6] Головоломка «грязные дети» — это вариант известных головоломок о мудрецах или изменах жен/мужей. ^[7]

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

Головоломка для мутных детей [ править ]

Описание [ править ]

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

Логическое решение [ править ]

Если предположить, что каждый ребенок обладает идеальной логикой (и знает, что она есть у каждого из остальных), то все дети с грязными лицами ( $X$ ) вместе сделают шаг вперед в свой ход $X$ . Информация у детей разная, в зависимости от того, мутное у них лицо или нет. Каждый член $X$ видит $X-1$ мутные лица, и знает, что эти дети в свою очередь выйдут вперед $X-1$ если они единственные мутные лица. Когда этого не происходит, каждый член $X$ знает, что он или она также является членом $X$ , и делает шаг вперед при повороте $X$ . Каждый не член $X$ видит $X$ мутные лица, и не будет ожидать, что кто-нибудь выйдет вперед, пока хотя бы не повернется $X$ .

Предположим, что есть двое детей, Алиса и Боб, и что только Алиса грязная ( $X=1$ ). Алиса знает, что у «некоторых» детей лица грязные, но ни у кого другого лицо не грязное, а это означает, что ее собственное лицо должно быть грязным, и она делает шаг вперед на первом ходу. Боб, видя грязное лицо Алисы, на первом ходу не может узнать, грязное ли его собственное лицо или нет, пока Алиса не выйдет вперед (указывая, что его собственное лицо должно быть чистым). Если и Алиса, и Боб грязные ( $X=2$ ), каждый находится в положении Боба, когда $X=1$ : ни один из них не может сделать шаг вперед на первом ходу. Однако ко второму ходу Боб знает, что Алиса, должно быть, увидела, что его лицо грязное (потому что она не сделала шаг вперед на первом ходу), и поэтому он делает шаг вперед на втором ходу. Используя ту же логику, Алиса также делает шаг вперед на втором ходу.

Предположим, что есть третий ребенок, Чарли. Лишь бы Алиса мутная( $X=1$ ), она не увидит грязных лиц и на первом повороте выйдет вперед. Если и Алиса, и Боб мутные ( $X=2$ ), ни один из них не может сделать шаг вперед на первом ходу, но ко второму ходу каждый будет знать, что другой видел грязное лицо (которое, как они видят, не принадлежит Чарли), поэтому их собственное лицо должно быть грязным, и оба сделают шаг вперед на втором ходу. Чарли, видя два грязных лица, на втором ходу не знает, грязное ли его собственное лицо или нет, пока Алиса и Боб оба не выйдут вперед (указывая, что его собственное лицо чистое). Если все три мутные( $X=3$ ), каждый находится в положении Чарли, когда $X=2$ : когда два человека не могут сделать шаг вперед на втором повороте, каждый знает, что другой видит два грязных лица, а это означает, что их собственное лицо должно быть грязным, и каждый делает шаг вперед на третьем повороте.

Можно доказать, что $X$ грязные дети будут выходить вперед при повороте $X$ . ^[4]^[14]

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

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

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

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

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

Шляпа королевских мудрецов » Головоломка «

Описание [ править ]

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

Решение [ править ]

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

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

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

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

Проблема Жозефины [ править ]

Описание [ править ]

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

Решение [ править ]

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

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

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

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

Алиса на съезде логиков [ править ]

Описание [ править ]

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

Решение [ править ]

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

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

Базовая головоломка со шляпами [ править ]

Описание [ править ]

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

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

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

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

Решение [ править ]

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

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

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

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

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

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

Случай R < B аналогичен.

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

Описание [ править ]

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

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

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

Решение [ править ]

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

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

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

Вариант с тремя шляпами [ править ]

Описание [ править ]

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

Решение [ править ]

В этой головоломке нет 100% выигрышной стратегии, но ее можно выиграть с вероятностью 75%. Если рассматривать цвета шляп как биты, то эту проблему можно решить с помощью теории кодирования , например, с помощью кодов Хэмминга . ^[21]

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

Описание [ править ]

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

Решение [ править ]

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

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

Описание [ править ]

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

Решение [ править ]

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

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

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

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

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

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

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

Вариант десяти шляп [ править ]

Описание [ править ]

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

Решение [ править ]

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

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

Описание [ править ]

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

Решение [ править ]

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

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

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

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

Описание [ править ]

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

Решение [ править ]

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

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

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

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

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

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

Описание [ править ]

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

Решение [ править ]

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

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

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

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

Описание [ править ]

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

Решение [ править ]

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

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

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

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

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

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

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

См. также [ править ]

Ссылки [ править ]

^ Штульмюллер, А.; Гудман, Северная Дакота (июнь 2014 г.). «Рассуждения о рассуждениях с помощью вложенных условий: моделирование теории разума с помощью вероятностных программ». Исследование когнитивных систем . 28 : 80–99. CiteSeerX 10.1.1.361.5043 . дои : 10.1016/j.cogsys.2013.07.003 . S2CID 7602205 .
^ Луччи, Стивен; Копец, Дэнни (2015). Искусственный интеллект в XXI веке . Стилус Паблишинг, ООО. ISBN 978-1-944534-53-0 .
^ Тагиев, Рустам (2008). «Простейший сценарий взаимного вложенного моделирования при взаимодействии человека и машины». КИ 2008: Достижения в области искусственного интеллекта . Конспекты лекций по информатике. Том. 5243. Спрингер. стр. 364–371. дои : 10.1007/978-3-540-85845-4_45 . ISBN 978-3-540-85844-7 .
^ Перейти обратно: ^а ^б ^с Феджин, Рональд ; Халперн, Джозеф Ю .; Моисей, Йорам; Варди, Моше Ю. (март 1999 г.). «Возвращение к общеизвестным знаниям». Анналы чистой и прикладной логики . 96 (1–3): 89–105. arXiv : cs/9809003 . дои : 10.1016/S0168-0072(98)00033-5 . S2CID 59551 .
^ Перейти обратно: ^а ^б ван дер Хук, Вибе; ван Дитмарш, Ганс (2007). Динамическая эпистемическая логика . Спрингер. ISBN 978-1-4020-5838-7 .
^ «Google Scholar «Загадка для грязных детей» » . ученый.google.com . Проверено 11 февраля 2020 г.
^ Феджин, Рональд ; Халперн, Джозеф Ю .; Моисей, Иорам; Варди, Моисей (2004). Рассуждения о знаниях МТИ Пресс. ISBN 978-0262562003 .
^ Хардин, Кристофер; Тейлор, Алан Д. (2008). «Введение в проблемы с бесконечными шляпами» (PDF) . Математический интеллект . 30 (4): 20–25. дои : 10.1007/BF03038092 . S2CID 24613564 . Архивировано из оригинала (PDF) 5 апреля 2012 г.
^ «Шляпы узников – ребусы и загадки» . www.puzzlesandriddles.com .
^ «Загадка о заключенных и шляпах» . CrazyforCode . 13 августа 2013 г.
^ «Роботы разгадывают «головоломку мудрецов», чтобы продемонстрировать определенную степень самосознания» . techxplore.com .
^ Лейте, Жуан (2005). Вычислительная логика в многоагентных системах: 5-й международный семинар, CLIMA V, Лиссабон, Португалия, 29–30 сентября 2004 г., переработанные избранные и приглашенные статьи . Springer Science & Business Media. ISBN 978-3-540-28060-6 .
^ Перейти обратно: ^а ^б Тагиев, Рустам (2011). Стратегическое взаимодействие реальных агентов. Целостная концептуализация и программные компоненты междисциплинарной исследовательской инфраструктуры (на немецком языке). Юго-западное немецкое издательство университетских публикаций. стр. 90–95. ISBN 978-3838125121 .
^ Вебер, Роберто А. (1 декабря 2001 г.). «Поведение и обучение в игре «Грязные лица». Экспериментальная экономика . 4 (3): 229–242. дои : 10.1023/А:1013217320474 . ISSN 1573-6938 . S2CID 123369018 .
^ Моисей, Йорам; Долет, Дэнни; Хаперн, Джозеф Ю. (1985). «Измены мужей и другие истории (Предварительная версия)» (PDF) . Материалы четвертого ежегодного симпозиума ACM по принципам распределенных вычислений - PODC '85 . стр. 215–223. дои : 10.1145/323596.323616 . ISBN 0897911687 . S2CID 2519017 .
^ Харатоник, Влодзимеж Ю. (2010). «Алиса на съезде логиков» (PDF) . Миссурийский университет науки и технологий . Архивировано из оригинала (PDF) 5 июля 2010 г. Проверено 31 июля 2015 г.
^ Браун, Эзра; Тантон, Джеймс (апрель 2009 г.). «Дюжина проблем со шляпами» (PDF) . Математические горизонты . 16 (4): 22–25. дои : 10.1080/10724117.2009.11974827 . S2CID 123345434 . Архивировано из оригинала (PDF) 17 июля 2017 г. Проверено 8 октября 2011 г.
^ Винклер, Питер (2004). Математические головоломки: Сборник знатоков . АК Петерс. стр. 125–126 . шляпа-головоломка Тодд.
^ Биография Тодда Эберта в Калифорнийском государственном университете, Лонг-Бич
^ Гарднер, Мартин (1978). Ага! Понимание . Научный американец. п. 102. ИСБН 0-89454-001-7 . Проверено 8 октября 2011 г.
^ Го, Венге; Касала, Субраманьям; Рао, М. Бхаскара; Такер, Брайан. «Проблема шляпы и некоторые ее варианты» (PDF) .
^ Хэвил, Джулиан (2008). Невозможный? Неожиданные решения парадоксальных головоломок . Издательство Принстонского университета. стр. 50–59. ISBN 9780691131313 . Проверено 8 октября 2011 г.

[1] Штульмюллер, А.; Гудман, Северная Дакота (июнь 2014 г.). «Рассуждения о рассуждениях с помощью вложенных условий: моделирование теории разума с помощью вероятностных программ». Исследование когнитивных систем . 28 : 80–99. CiteSeerX 10.1.1.361.5043 . дои : 10.1016/j.cogsys.2013.07.003 . S2CID 7602205 .

[2] Луччи, Стивен; Копец, Дэнни (2015). Искусственный интеллект в XXI веке . Стилус Паблишинг, ООО. ISBN 978-1-944534-53-0 .

[3] Тагиев, Рустам (2008). «Простейший сценарий взаимного вложенного моделирования при взаимодействии человека и машины». КИ 2008: Достижения в области искусственного интеллекта . Конспекты лекций по информатике. Том. 5243. Спрингер. стр. 364–371. дои : 10.1007/978-3-540-85845-4_45 . ISBN 978-3-540-85844-7 .

[halpern-4] Перейти обратно: ^а ^б ^с Феджин, Рональд ; Халперн, Джозеф Ю .; Моисей, Йорам; Варди, Моше Ю. (март 1999 г.). «Возвращение к общеизвестным знаниям». Анналы чистой и прикладной логики . 96 (1–3): 89–105. arXiv : cs/9809003 . дои : 10.1016/S0168-0072(98)00033-5 . S2CID 59551 .

[wiebe-5] Перейти обратно: ^а ^б ван дер Хук, Вибе; ван Дитмарш, Ганс (2007). Динамическая эпистемическая логика . Спрингер. ISBN 978-1-4020-5838-7 .

[6] «Google Scholar «Загадка для грязных детей» » . ученый.google.com . Проверено 11 февраля 2020 г.

[7] Феджин, Рональд ; Халперн, Джозеф Ю .; Моисей, Иорам; Варди, Моисей (2004). Рассуждения о знаниях МТИ Пресс. ISBN 978-0262562003 .

[8] Хардин, Кристофер; Тейлор, Алан Д. (2008). «Введение в проблемы с бесконечными шляпами» (PDF) . Математический интеллект . 30 (4): 20–25. дои : 10.1007/BF03038092 . S2CID 24613564 . Архивировано из оригинала (PDF) 5 апреля 2012 г.

[9] «Шляпы узников – ребусы и загадки» . www.puzzlesandriddles.com .

[10] «Загадка о заключенных и шляпах» . CrazyforCode . 13 августа 2013 г.

[11] «Роботы разгадывают «головоломку мудрецов», чтобы продемонстрировать определенную степень самосознания» . techxplore.com .

[12] Лейте, Жуан (2005). Вычислительная логика в многоагентных системах: 5-й международный семинар, CLIMA V, Лиссабон, Португалия, 29–30 сентября 2004 г., переработанные избранные и приглашенные статьи . Springer Science & Business Media. ISBN 978-3-540-28060-6 .

[sira-13] Перейти обратно: ^а ^б Тагиев, Рустам (2011). Стратегическое взаимодействие реальных агентов. Целостная концептуализация и программные компоненты междисциплинарной исследовательской инфраструктуры (на немецком языке). Юго-западное немецкое издательство университетских публикаций. стр. 90–95. ISBN 978-3838125121 .

[14] Вебер, Роберто А. (1 декабря 2001 г.). «Поведение и обучение в игре «Грязные лица». Экспериментальная экономика . 4 (3): 229–242. дои : 10.1023/А:1013217320474 . ISSN 1573-6938 . S2CID 123369018 .

[15] Моисей, Йорам; Долет, Дэнни; Хаперн, Джозеф Ю. (1985). «Измены мужей и другие истории (Предварительная версия)» (PDF) . Материалы четвертого ежегодного симпозиума ACM по принципам распределенных вычислений - PODC '85 . стр. 215–223. дои : 10.1145/323596.323616 . ISBN 0897911687 . S2CID 2519017 .

[Charatonik2010-16] Харатоник, Влодзимеж Ю. (2010). «Алиса на съезде логиков» (PDF) . Миссурийский университет науки и технологий . Архивировано из оригинала (PDF) 5 июля 2010 г. Проверено 31 июля 2015 г.

[B&T-17] Браун, Эзра; Тантон, Джеймс (апрель 2009 г.). «Дюжина проблем со шляпами» (PDF) . Математические горизонты . 16 (4): 22–25. дои : 10.1080/10724117.2009.11974827 . S2CID 123345434 . Архивировано из оригинала (PDF) 17 июля 2017 г. Проверено 8 октября 2011 г.

[18] Винклер, Питер (2004). Математические головоломки: Сборник знатоков . АК Петерс. стр. 125–126 . шляпа-головоломка Тодд.

[19] Биография Тодда Эберта в Калифорнийском государственном университете, Лонг-Бич

[20] Гарднер, Мартин (1978). Ага! Понимание . Научный американец. п. 102. ИСБН 0-89454-001-7 . Проверено 8 октября 2011 г.

[21] Го, Венге; Касала, Субраманьям; Рао, М. Бхаскара; Такер, Брайан. «Проблема шляпы и некоторые ее варианты» (PDF) .

[22] Хэвил, Джулиан (2008). Невозможный? Неожиданные решения парадоксальных головоломок . Издательство Принстонского университета. стр. 50–59. ISBN 9780691131313 . Проверено 8 октября 2011 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]