Введение

Логическая головоломка

Индуктивные головоломки — это логические головоломки, являющиеся примерами рассуждений с участием нескольких агентов, где решение формируется вместе с принципом индукции. Сценарий головоломки всегда включает в себя нескольких игроков с одинаковыми способностями к рассуждению, которые выполняют одни и те же логические шаги. Согласно принципу индукции, решение простейшего случая делает очевидным решение следующего, более сложного случая. Как только простейший случай индуктивной головоломки решен, вся головоломка считается решенной. Типичными признаками таких головоломок являются любые головоломки, в которых каждый участник обладает определенной информацией (обычно известной всем) о других участниках, но не о себе. Также, как правило, дается намек, указывающий на то, что участники могут доверять интеллекту друг друга – они способны к теории разума (то есть, общеизвестно, что "каждый участник знает modus ponens"). Кроме того, бездействие участника является невербальным сигналом об отсутствии у него знаний, что затем становится общеизвестным для всех участников, наблюдавших это бездействие. Головоломка о грязных детях – наиболее часто встречающаяся индуктивная головоломка в научной литературе по эпистемической логике. Головоломка о грязных детях является вариантом хорошо известных головоломок о мудрецах или неверных супругах. Головоломки со шляпами – это вариации индуктивных головоломок, которые появились еще в 1961 году. Во многих вариантах головоломки со шляпами описываются в контексте заключенных, а в других – в контексте мудрецов.

Описание

Группе внимательных детей сообщают, что у некоторых из них грязные лица. Каждый ребенок может видеть лица других, но не может определить, грязное ли его собственное лицо. Детям говорят, что те, у кого грязные лица, должны выйти вперед, но любой ребенок с чистым лицом, который выйдет вперед, будет наказан. По счету три каждый ребенок, который полагает, что его лицо грязное, должен одновременно выйти вперед; любой ребенок, который каким-либо образом подаст сигнал другому, будет наказан. Если хотя бы один ребенок с грязным лицом не выйдет вперед, процедура будет повторена.

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

Предполагая, что каждый ребенок обладает — и знает, что каждый из остальных обладает — безупречной логикой, все дети с грязными лицами выйдут вперед одновременно на первом ходу. У детей разная информация, в зависимости от того, грязно ли их собственное лицо или нет. Каждый член группы видит *n-1* грязных лиц и знает, что эти дети выйдут вперед на первом ходу, если они будут единственными с грязными лицами. Если этого не происходит, каждый член группы понимает, что он или она также является членом группы, и выходит вперед на втором ходу. Каждый, не входящий в группу, видит *n-1* грязных лиц и не ожидает, что кто-либо выйдет вперед до, по крайней мере, второго хода. Предположим, есть два ребенка, Алиса и Боб, и только Алиса грязная. Алиса знает, что "некоторые" дети имеют грязные лица, но ничье другое лицо не грязное, что означает, что ее собственное лицо должно быть грязным, и она выходит вперед на первом ходу. Боб, видя грязное лицо Алисы, не может узнать на первом ходу, грязно ли его собственное лицо, пока Алиса не выйдет вперед (что указывает на то, что его собственное лицо должно быть чистым). Если и Алиса, и Боб грязные, каждый оказывается в положении Боба: ни один из них не может выйти вперед на первом ходу. Однако, на втором ходу Боб понимает, что Алиса должна была видеть, что его лицо грязное (потому что она не вышла вперед на первом ходу), и поэтому он выходит вперед на втором ходу. Используя ту же логику, Алиса также выходит вперед на втором ходу. Предположим, есть третий ребенок, Чарли. Если только Алиса грязная, она не увидит грязных лиц и выйдет вперед на первом ходу. Если и Алиса, и Боб грязные, ни один из них не может выйти вперед на первом ходу, но каждый узнает к второму ходу, что другой видел грязное лицо — которое они могут видеть, не принадлежит Чарли — следовательно, их собственное лицо должно быть грязным, и оба выйдут вперед на втором ходу. Чарли, видя два грязных лица, не знает на втором ходу, грязно ли его собственное лицо, пока Алиса и Боб не выйдут вперед (что указывает на то, что его собственное лицо чисто). Если все трое грязные, каждый оказывается в положении Чарли: когда два человека не выходят вперед на втором ходу, каждый понимает, что другой видит два грязных лица, что означает, что его собственное лицо должно быть грязным, и каждый выходит вперед на третьем ходу. Можно доказать, что *n* детей с грязными лицами выйдут вперед на *n*-м ходу.

Теоретическое решение игры

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

Решение

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

Описание

На Тайном Собрании Логиков, Главный Логик надел на голову каждого участника повязку, так что все остальные могли видеть её, но сам участник – нет. Повязки были разных цветов. Логики сели в круг, и Мастер объявил, что в лесу будет регулярно звонить колокол. Как только логик узнает цвет своей повязки, он должен покинуть собрание при следующем звонке. Им было запрещено разговаривать, использовать зеркала, камеры или любые другие средства, кроме логики, для определения цвета своей повязки. В случае, если среди собравшихся окажутся самозванцы, тех, кто не покинет собрание вовремя, грубо выпроводят в нужный момент. Аналогично, тех, кто попытается уйти раньше, грубо удержат и выпроводят в нужный момент. Мастер заверил всех, что головоломка не окажется неразрешимой для настоящего логика. Как им это удалось?

Решение

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

Описание

Ряд игроков носит шляпу, которая может быть одного из нескольких заданных цветов. Игроки видят цвета шляп хотя бы некоторых других игроков, но не своей собственной. При крайне ограниченном или полном отсутствии общения, некоторым игрокам необходимо угадать цвет своей шляпы. Задача состоит в том, чтобы найти стратегию, позволяющую игрокам определить цвет своей шляпы, основываясь на видимых шляпах других игроков и их действиях. В некоторых вариантах игроки соревнуются, чтобы первыми правильно угадать; в других они могут заранее разработать стратегию для сотрудничества и максимизации вероятности правильных ответов. Одна из вариаций получила новую известность благодаря диссертации Тодда Эберта 1998 года, защищенной в Калифорнийском университете в Санта-Барбаре. Это стратегическая задача, связанная с кооперативной игрой, имеющая связь с алгебраической теорией кодирования. Троих игроков предупреждают, что каждому из них будет надета либо красная, либо синяя шляпа. Они должны поднять руку, если увидят красную шляпу на другом игроке, стоя в кругу лицом друг к другу. Первый, кто правильно назовет цвет своей шляпы, выигрывает. Все трое игроков поднимают руки. После нескольких минут наблюдения друг за другом без попыток угадать, один из игроков объявляет: "Красная!" и выигрывает. Как победитель пришел к этому выводу, и какого цвета шляпы у всех?

Решение

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

Подсчитайте количество синих шляп b и красных шляп r, которые вы видите. Подождите b секунд или r секунд, в зависимости от того, что наступит раньше. Если никто еще не высказался, предположите, что ваша шляпа синяя, если вы видите меньше синих шляп, чем красных, или красная, если вы видите меньше красных шляп, чем синих. Если вы еще не высказались, догадайтесь, что ваша шляпа имеет цвет, противоположный цвету шляпы одного из первых высказавшихся. Предположим, что всего есть B синих шляп и R красных шляп. Возможны три случая. Если B = R, то игроки в синих шляпах видят B-1 синих шляп и R красных шляп, поэтому подождите B-1 секунды, а затем правильно угадайте, что на вас синяя шляпа. Аналогично, игроки в красных шляпах будут ждать R-1 секунды, прежде чем правильно угадать, что на них красная шляпа. Таким образом, все игроки делают правильные предположения одновременно. Если B < R, то игроки в синих шляпах видят B-1 синих шляп и R красных шляп, а игроки в красных шляпах видят B синих шляп и R-1 красных шляп. Поскольку B-1 < B ≤ R-1, игроки в синих шляпах первыми выскажутся, правильно предположив, что на них синяя шляпа. Остальные игроки затем правильно угадают, что на них красная шляпа. Случай, когда R < B, аналогичен.

Описание

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

Решение

Заключенные знают, что есть всего по две шляпы каждого цвета. Если С видит, что у А и В шляпы одного цвета, он сделает вывод, что на нем самом шляпа другого цвета. Однако, если у А и В шляпы разных цветов, С не сможет ничего сказать. Суть в том, что заключенный В, выждав некоторое время и зная, что сделает С, сможет заключить: если С молчит, значит, шляпы у А и В разных цветов. Увидев шляпу А, он сможет определить цвет своей собственной шляпы. Как и во многих подобных головоломках, решение основано на предположении, что все участники абсолютно рациональны и достаточно умны, чтобы сделать необходимые выводы. Разгадав эту головоломку, можно поразмышлять о природе коммуникации и о том, нарушает ли значимое молчание заключенного С правило "никакой коммуникации" (учитывая, что коммуникация обычно определяется как "передача информации").

Описание

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

Решение

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

Описание

В одном из вариантов этой головоломки заключённые знают, что есть 2 чёрные шляпы и 2 белые шляпы, и между заключёнными А и В находится стена. Однако заключённые В, С и Д могут видеть тех, кто стоит перед ними: Д видит В, С и стену, В видит только стену, а С видит В и стену. (Заключённого А снова нельзя увидеть, и он нужен только для того, чтобы носить одну из чёрных шляп.) Как им можно определить цвет шляпы каждого, не общаясь?

Решение

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

Описание

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

Описание

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

Решение

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

Описание

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

Решение

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

Описание

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

Решение

Если принять аксиому выбора и предположить, что каждый заключенный обладает (нереалистичной) способностью запоминать несчетно бесконечное количество информации и выполнять вычисления с несчетно бесконечной вычислительной сложностью, ответ – да. На самом деле, даже если мы допустим несчетное количество различных цветов для шляп и несчетное количество заключенных, аксиома выбора предоставляет решение, которое гарантирует, что умрет лишь конечное число заключенных, при условии, что каждый заключенный может видеть шляпы всех остальных заключенных (а не только тех, кто стоит перед ним в очереди), или, по крайней мере, что каждый заключенный может видеть все шляпы, кроме конечного числа. Решение для двух цветов выглядит следующим образом, а решение для несчетно бесконечного числа цветов по существу то же самое: заключенные, стоящие в очереди, образуют последовательность из 0 и 1, где 0 обозначает синий цвет, а 1 – красный. Перед тем, как их построить в линию, заключенные определяют следующее отношение эквивалентности для всех возможных последовательностей, в которые они могут быть помещены: две последовательности эквивалентны, если они совпадают после конечного числа элементов. На основе этого отношения эквивалентности заключенные получают набор классов эквивалентности. Предполагая аксиому выбора, существует множество представительных последовательностей – по одной из каждого класса эквивалентности. (Почти каждое конкретное значение невозможно вычислить, но аксиома выбора подразумевает существование некоторого набора значений, поэтому мы предполагаем, что у заключенных есть доступ к оракулу.) Когда заключенных выстраивают в линию, каждый из них может видеть все шляпы, кроме конечного числа, и, следовательно, может определить, к какому классу эквивалентности принадлежит фактическая последовательность шляп. (Это предполагает, что каждый заключенный может выполнить несчетное количество сравнений для нахождения соответствия, причем каждое сравнение классов требует несчетного количества индивидуальных сравнений шляп.) Затем они начинают угадывать цвет своей шляпы, как если бы они находились в представительной последовательности из соответствующего класса эквивалентности. Поскольку фактическая и представительная последовательности принадлежат одному и тому же классу эквивалентности, их элементы совпадают после некоторого конечного числа N заключенных. Все заключенные, стоящие после этих первых N заключенных, будут спасены. Поскольку заключенные не имеют информации о цвете своей собственной шляпы и делают одно и то же предположение независимо от цвета, у каждого заключенного есть 50% шанс быть убитым. Может показаться парадоксальным, что бесконечное число заключенных имеет равные шансы быть убитым, но при этом точно известно, что умрет лишь конечное число. Разрешение этого парадокса заключается в том, что функция, используемая для определения предположения каждого заключенного, не является измеримой. Чтобы понять это, рассмотрим случай, когда ни один заключенный не будет убит. Это происходит тогда и только тогда, когда фактическая последовательность является одной из выбранных представительных последовательностей. Если последовательности из 0 и 1 рассматривать как двоичные представления действительного числа между 0 и 1, то представительные последовательности образуют неизмеримое множество. (Этот набор похож на множество Витали, единственное отличие заключается в том, что классы эквивалентности формируются для чисел с конечными двоичными представлениями, а не для всех рациональных чисел.) Следовательно, нельзя присвоить вероятность событию, при котором ни один заключенный не будет убит. Аналогичен аргумент и для других конечных чисел убитых заключенных, соответствующих конечному числу вариаций каждого представителя.

Описание

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

Решение

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

Описание

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