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

Ответ. Два рыцаря.

9.9. Оба загадали делители числа 2002 (иначе кто-то понял бы, что 2002 – сумма загаданных чисел, и определил бы второе число). Однако, даже зная, что Саша загадал делитель, Маша не может исключить, что 2002 – сумма. Но сумма делителей равна 2002 только в случае 1001 + 1001 (другие делители равны 2002 либо меньше 1001). Значит, Маша загадала 1001 (а Саша – 2 или 1001, и тогда оба действительно не могли узнать числа друг друга).

Ответ. 1001

9.10. 1) Василиса может найти последнюю цифру суммы цифр на своих карточках. Прибавив к ней 7, она узнает последнюю цифру суммы цифр на всех карточках, кроме карточки Бабы-Яги. Остается вычесть результат из 5 (или из 15), так как сумма цифр на всех карточках равна 45.

Ответ. Знает.

2) Выпишем все суммы четырех ненулевых чисел, оканчивающиеся на 7:

1 + 2 + 5 +9, 1 + 2 + 6 +8, 1 + 3 + 4 +9, 1 + 3 + 5 +8,

1 + 3 + 6 + 7, 1 + 4 + 5 + 7, 2 + 3 + 4 + 8, 2 + 3 + 5 + 7,

2 + 4 + 5 + 6, 3 + 7 + 8 + 9, 4 + 6 + 8 + 9, 5 + 6 + 7 + Э.

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

Ответ. Не знает.

3) Пусть, скажем, у Бабы-Яги карточка 1. Тогда цифры Ивана образуют одну из сумм, не содержащих 1:

2 + 3 + 4 +8, 2 + 3 + 5 +7, 2 + 4 + 5 +6,

3 + 7 + 8 +9, 4 + 6 + 8 + 9, 5 + 6 + 7 + 9.

Для любой цифры, отличной от 0 и 1, среди выписанных найдется как сумма, содержащая эту цифру, так и сумма, не содержащая ее. Аналогично разбираются случаи всех остальных карточек Бабы-Яги.

Ответ. Не может.

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

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

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

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

Занятие 10

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

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

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

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

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

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

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

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

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

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

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

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