Головоломки на индукцию

Головоломки на индукцию — это логические головоломки, которые являются примерами , где решение разворачивается по принципам индукции.

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

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

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

Задачи о шляпах — это разновидности индуктивных головоломок, которые появились ещё в 1961 году. В различных вариациях головоломки о шляпах рассказываются на примере заключенных. В других случаях, головоломки с шляпами описываются в контексте мудрецов.

Головоломка о грязных детях

Описание

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

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

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

Представим, что имеется двое детей, Алиса и Боб, и только у Алисы грязное лицо (). Алиса знает, что «некоторые» дети имеют грязные лица, но, поскольку ни у кого другого лицо не грязное, означает, что её собственное значение должно быть грязным и она шагнёт на первой итерации игры. Боб, видя грязное лицо Алисы, не имеет возможности знать, грязное ли его лицо или нет, пока Алиса не шагнёт вперёд (что указывает, что его собственное лицо чистое). Если оба лица, как у Алисы, так и у Боба, грязные (), каждый из них находится в позиции Боба при — никто из них не шагнёт вперёд на первой итерации. Однако, на второй итерации Боб знает, что Алиса должна видеть его грязное лицо (поскольку она не шагнула вперёд на первой итерации), так что он шагнёт вперёд на второй итерации. Используя ту же логику Алиса также шагнёт вперёд на второй итерации.

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

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

Решение, основанное на теории игр

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

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

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

Описание

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

Решение

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

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

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

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

Задача Джозефины

Описание

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

Решение

Задача Джозефины является другим хорошим примером общего случая.

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

Эта задача известна также как «Задача о неверных мужьях», «Задача о неверных жёнах» и «Задача о грязных детях». Логически задача идентична задаче о голубых глазах.

Эта задача присутствует как задача с белыми и чёрными шляпами в классической книге Льюиса «Элементы дискретной математики».

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

Описание