Логика для всех. От пиратов до мудрецов

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

9.11. Участник А не может быть мирным жителем, так как в этом случае он ничего не знал бы про Д. Если бы Б был мирным жителем, то к моменту своего высказывания он знал бы только то, что А не мирный житель, и свою роль в игре. Этого недостаточно, чтобы утверждать, что Д – мафиози. Если В – мирный житель, то у него нет оснований исключать, что А и Б – мафиози, а Д – комиссар, и тогда Д знает, кто он. Поэтому и В не мирный житель. Получается, что мирные жители – Г и Д. Они оба это к моменту высказывания Г понимают, так что Г говорит правду. Участник Б лжет, поэтому он – мафиози. Кто из А и В комиссар, а кто второй мафиози, определить невозможно, оба варианта не противоречат высказываниям всех игроков.

Ответ. Б – мафиози, Г и Д – мирные жители.

Занятие 10

10.6. Если белых колпаков по-прежнему два, а черных более трех (например, 4 или 5), то все рассуждения останутся в силе. А вот если мудрецам принести три белых и три черных колпака и надеть на каждого черный колпак, третий мудрец тоже не сможет определить цвет своего колпака, но доказать это непросто. Заметим, что в таком случае после того, как все три мудреца по очереди скажут «не знаю», первый уже сможет определить цвет своего колпака.

10.7. Сначала сформулируем общую задачу.

По кругу сидят n мудрецов, они могут видеть и слушать друг друга. Им принесли n — 1 белый и n черных колпаков. Затем завязали глаза, надели всем черные колпаки, а белые спрятали. После этого мудрецам развязали глаза и стали поочередно спрашивать: «Знаешь ли ты цвет своего колпака?» Почти все ответили: «Не знаю», а последний сказал: «Знаю. Черный». Как он рассуждал?

Приведем рассуждения четвертого мудреца для n = 4. «Если на мне белый колпак, то остались два белых и четыре черных колпака. Но в таком случае третий мудрец смог бы определить, что у него черный колпак (для этого ему пришлось бы всего лишь решить предыдущую задачу). Раз он сказал, что не знает, на мне черный колпак».

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

10.8. Подсказка. Решите сначала задачу для одного мудреца, затем постепенно увеличивайте их количество.

Решение. 1) Если бы грязный мудрец был один, он вышел бы на первой станции.

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

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

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

2) Снова начнем с простых случаев. Если мудрец один, то от проводника он узнал, что кто-то испачкался. Если мудрецов двое, то каждый и без проводника знал, что кто-то испачкался. Но из слов проводника он понял, что и другой знает, что кто-то испачкался.

Пусть мудрецов трое. Третий видел грязные лица первого и второго и понимал, что первый и второй знают, что кто-то испачкался. Но вот знает ли второй, что первый знает, что кто-то испачкался? Знает, но это стало известно третьему лишь после слов проводника. Это же можно сказать и о других мудрецах. Итак, все мудрецы узнали, что все знают, что все знают, что кто-то испачкался.

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

10.9. «Среди вас есть испачкавшиеся» означает, что на ком-то надет черный колпак. Никто не сообщал это мудрецам словами. Но зато они видели, что белых колпаков на один меньше, чем мудрецов.

Комментарий. А если бы их было на два меньше? Тогда как минимум на двух мудрецах были бы черные колпаки. Это бы соответствовало словам проводника «Среди вас как минимум двое испачкались». В таком случае мудрецы бы вышли на одну станцию раньше (а в задаче про колпаки цвет своего колпака назвал бы предпоследний мудрец).