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

8.7. Истинны высказывания в пунктах 1, 3, 4, 5, 7. Ложны высказывания 2, 6, 8.

8.8. Все три высказывания означают, что некузявых ляпусиков не бывает.

Ответ. Равносильны.

8.9. Пусть Д спит. Тогда А и Г спят (из 5). Тогда Б спит (из 1), поэтому В не спит (из 3). Но это противоречит 4.

Значит, Д не спит. Тогда спят Г (из 2) и В (из 4), а Б не спит (из 3). Поэтому А не спит (из 1).

Ответ. В и Г.

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

Пусть при любой рассадке по кругу найдутся два мальчика рядом. Рассмотрим произвольную рассадку и занумеруем детей по кругу по часовой стрелке. А затем посадим детей в таком порядке: 1, 3, 5, 7, 9, 11, 13, 15, 17, 2, 4, 6, 8, 10, 12, 14, 16. По условию после этого найдутся два мальчика рядом. Но раньше они сидели через одного, т. е. в исходном положении был гость, сидевший между ними.

Пусть при любой рассадке по кругу найдется гость, сидящий между двумя мальчиками. Докажем от противного, что мальчиков больше, чем девочек. Действительно, если бы девочек было больше, детей можно было бы рассадить так: ДДГГДДГГДДГГДДГГД, где буква Д означает девочку, а буква Г – гостя любого пола, и никто бы не сидел между двумя мальчиками.

8.11. 1) Всего существует 6 теорем указанного вида. Если дать их все, то последняя будет следовать из предыдущих. А 5 можно дать в таком порядке: 1 ⇒ 2, 1 ⇒ 3, 2 ⇒ 3, 3 ⇒ 2, 3 ⇒ 1.

2) Всего существует 12 таких теорем. Как отмечено в предыдущем пункте, с участием утверждений 1, 2 и 3 нельзя давать все 6 возможных теорем. Без ограничения общности можно исключить теорему 2 ⇒ 1. Но с участием утверждений 2, 3 и 4, а также 1, 3 и 4 тоже нельзя давать все 6 возможных теорем. Если пытаться решить обе проблемы исключением лишь одной теоремы, исключать надо 3 ⇒ 4 или 4 ⇒ 3. В любом из случаев остается цепочка из восьми теорем 1 ⇒ 3 ⇒ 2 ⇒ 4 ⇒ 1, из которой придется исключить как минимум одну теорему, и останется не более 9 теорем. Пример на 9 теорем: 1 ⇒ 2, 1 ⇒ 3, 1 ⇒ 4, 2 ⇒ 3, 2 ⇒ 4, 3 ⇒ 4, 4 ⇒ 3, 4 ⇒ 2, 4 ⇒ 1.

3) Пример на  теорем:

1 ⇒ 2, 1 ⇒ 3…, 1 ⇒ n,

2 ⇒ 3, 2 ⇒ > 4…, 2 ⇒ n,

n — 1 ⇒ n,

n ⇒ n − 1, n ⇒ n − 2…, n ⇒ 1.

Доказательство максимальности удобно изложить на языке графов. Будем считать утверждения вершинами, а теоремы – ориентированными ребрами. Оставим только ребра, ориентированные в обе стороны. Если бы они образовали цикл, то последняя доказанная в этом цикле теорема следовала бы из предыдущих теорем цикла. Значит, циклов нет. Тогда «двойных» ребер – не более n — 1, поэтому всего доказано не более  теорем.

Ответ. 1) 5; 2) 9; 3)

Занятие 9

9.4. На семи карточках написаны три четных и четыре нечетных числа. Судить о четности суммы двух чисел из четырех можно лишь тогда, когда все четыре числа имеют одинаковую четность. Значит, все три четных числа на карточках первого мудреца.

Ответ. 6, 8, 10.

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

Ответ. Джон – второй.

Комментарий. Почему эта задача является метаголоволомкой? Потому что важным условием является тот факт, что судья смог определить, кто из братьев Джон.

9.6. Рассмотрим четыре случая:

1) оба рыцари;

2) говоривший – рыцарь, а его спутник – лжец;

3) говоривший – лжец, а его спутник – рыцарь;

4) оба лжецы.

Во втором случае на первый вопрос был бы ответ «Нет», а в остальных – «Да». Поскольку путешественник не смог сделать вывод, второй случай исключен. На второй вопрос ответ «Да» был бы в первом и третьем случае, и различить их нет никакой возможности. А ответ «Нет» – во втором и четвертом случаях. Путешественник уже исключил второй случай, остается только четвертый.

Ответ. Двух лжецов.

9.7. Всех стоящих в кругу жителей деревни можно мысленно разбить на группы стоящих подряд правдивых людей и группы стоящих подряд лжецов (возможно, состоящие из одного человека). Крайние справа в своих группах назовут своих правых соседей лжецами, а остальные жители назовут своих правых соседей правдивыми. Из ответов всех жителей следует, что выполняется один из двух вариантов: истинный и соответствующий ему «с точностью до наоборот». Если истинная доля лжецов равна х, то во втором варианте она равна 1-х. Так как путешественник смог определить долю лжецов, то х = 1 – х, откуда х = 1/2.

Ответ. 1/2.

9.8. Какую информацию можно извлечь из упоминания о дне рождения? Такую, что два соседа утверждают одно и то же, поэтому либо они оба рыцари, либо оба лжецы. Рассмотрим теперь все возможные ответы на вопрос «Кто твои соседи?». Если на него все ответили: «Два рыцаря», то все они могли быть как рыцарями, так и лжецами, и даже после упоминания о дне рождения нельзя эти ситуации различить. Если все ответили: «Рыцарь и лжец», то они могли быть все лжецами. А могли сидеть и так: РР-ЛРРЛ. Эти ситуации также нельзя различить после упоминания о дне рождения. Если все ответили «Два лжеца», то среди них был хотя бы один рыцарь (иначе лжецы сказали бы правду), вокруг которого действительно сидят два лжеца. Если рядом с лжецом сидит еще один рыцарь, то после него снова лжец, а шестой сидящий говорит правду, и поэтому является рыцарем. Но чередоваться рыцари и лжецы не могут из-за одинаковых высказываний двух соседей о дне рождения. Значит, рядом с лжецом сидит еще один лжец. После него может сидеть только рыцарь (иначе лжец говорил правду). Тогда после рыцаря сидит лжец. В расстановке РЛЛРЛЛ есть два соседа-лжеца, которые могли высказаться одинаково про день рождения. Она и является единственно возможной в этой задаче.

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

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