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

3) А – шпион, и он солгал.

В первом случае А скажет «да», во втором – «нет», в третьем– «да». Поэтому по его ответу можно делать вывод только во втором случае. Итак, А – шпион, зачем-то сказавший правду.

Д42. 1) Если бы на вопрос «Вы шпион?» А ответил «нет», то он мог бы быть рыцарем или шпионом, а если «да», то он мог бы быть лжецом или шпионом. В первом случае то, что А сказал правду про В, не позволило бы судье понять, кто В, а во втором позволило бы. Значит, А сказал «да», и он шпион.

Ответ. А – шпион.

2) Мы уже выяснили, что А сказал «Да». Если бы Б сказал «Нет», то судья не понимал бы еще, что В – не шпион, а должен был допускать три возможности: 1) А – лжец, Б – рыцарь, В – шпион; 2) А – лжец, Б – шпион (сказавший правду), В – рыцарь; 3) А – шпион (сказавший правду), Б – лжец, В – рыцарь. Но судья понял, что В – не шпион. Значит, Б тоже сказал «Да». В таком случае судья должен допускать две возможности: 1) А – лжец, а Б – шпион (солгавший); 2) А – шпион (сказавший правду), а Б – рыцарь. В обоих случаях он действительно понимает, что В – не шпион. А когда А сказал, что В – не шпион, судья понимает и то, что А – не лжец, и реализуется второй из двух случаев: А – шпион, Б – рыцарь, В – лжец.

Ответ. «Да».

Д43. Обсуждение. Чтобы лучше почувствовать задачу, попробуем для начала действовать наугад. Предположим, например, что дураков и умных в думе по 100. Тогда умные дадут ответы от 98 до 100 (в зависимости от скромности и от того, кто именно уехал), а все дураки скажут «Один», и премьер-министр легко отличит умного от дурака. Почему же он не смог понять ответ? Потому что умные отвечали так же, как дураки, то есть их было мало.

Решение. Заметим, что все дураки дадут ответ: «Один». Если бы умных в думе было три или больше, то они дали бы ответ: «Два (или больше)» и премьер-министр всё бы понял. Значит, умных могло быть 0, 1 или 2.

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

Таким образом, возможны три неразличимых варианта: нет умных, один уверенный умный и два скромных умных. Во всех этих случаях все участники опроса ответят: «Один».

Посмотрим, какие ответы даст опоздавший думец в каждой из этих ситуаций в зависимости от его ума и скромности:

Видно, что ответы «1» и «2» встречаются в нескольких клетках, т. е. такие ответы не помогли бы различить ситуации. Зато ответы «О» и «3» встречаются в таблице по одному разу и позволяют сделать однозначный вывод. Значит, опоздавший дал один из этих ответов. В первом случае в думе один умный, во втором – три.

Ответ. 1 или 3.

Д44. 1) Занумеруем карты от 0 до 6. Можно считать, что у Гриши карты 1, 2 и 3. Пусть он скажет: «У меня либо набор 1, 2, 3, либо набор 4, 5, 6». Поскольку у Леши на руках как минимум две карты из набора 4, 5, 6, он понимает, что у Гриши набор 1, 2, 3, и знает, какая карта спрятана. Теперь Леша должен сообщить Грише свои карты. Возможны два случая.

1. У Леши набор 4, 5, 6 (а спрятана карта 0). Леша говорит: «У меня либо набор 4, 5, 6, либо 1, 2, 0».

2. У Леши другой набор, скажем, 4, 5, 0 (а спрятана карта 6). Леша говорит: «У меня либо набор 4, 5, 0, либо 1, 2, 3».

В обоих случаях названный Лешей «не свой» набор пересекается с Гришиным как минимум по двум картам, поэтому Гриша тоже узнает, какой на самом деле набор у Леши. Докажем, что Коле ничего не ясно. Действительно, и в том, и в другом случае названо три набора карт: А, В и С. Наборы В и С пересекаются по двум картам, Гриша сказал: «У меня либо А, либо В», Леша сказал: «У меня либо А, либо С». Это означает, что либо у Гриши набор А, а у Леши – С, либо у Гриши – В, а у Леши – А. Поэтому три карты из набора А и две карты из пересечения наборов В и С могут оказаться как у Гриши, так и у Леши (в нашем примере это карты 1, 2, 3, 4 и 5). А из остальных двух карт наборов В и С (в нашем примере 6 и 0) одна закрытая, другая – у одного из игроков. Поэтому местоположение никакой из карт Коля вычислить не может.

2) Заметим, что предыдущий способ не работает: зная закрытую карту, Коля может всё определить.

Пусть Гриша занумерует карты числами от 0 до 6 (и объявит об этом вслух). Затем пусть Гриша и Леша по очереди назовут остатки от деления суммы номеров своих карт на 7. Тогда они узнают расклад: ведь остаток суммы Гриши плюс остаток суммы Леши плюс номер спрятанной карты должны давать 0 + 1 + 2 + 3 + 4 + 5 + 6 = 0 (mod 7). Так, например, если у Леши карты 1, 3, 4, а Гриша назвал остаток 4, то спрятана карта —4 – (1 + 3 + 4) = 2 (mod 7), значит, у Гриши карты 0, 5, 6.

Проверим, что Коля ничего не узнал. Его информация исчерпывается Гришиной суммой g и Колиной картой к (а Лешину сумму теперь Коля и сам может вычислить). Рассмотрим любую другую карту, пусть ее номер х. Покажем, что она входит в какой-нибудь набор из трех карт с суммой g, не содержащий к. Для этого дополним х парой карт с суммой номеров g – х. Таких пар ровно три при любом значении g – х (доказательство см. ниже). Из них две, возможно, не подходят из-за того, что туда входит карта с номером s или к, но как минимум одна пара остается. С ее помощью мы и создадим набор для Гриши (а набор для Леши получится автоматически). Например, если х = 3, то в нашем случае при g = 4 надо найти пару с суммой 4–3 = 1. Таких пар три: 1 = 0 + 1 = 2 + 6 = 3 + 5 (mod 7). Из них подходит только (0, 1}, то есть у Гриши мог быть набор 0, 1, 3.