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

7.15. Слово «надо» употребляется в разных смыслах. Сначала подразумевается «нужное количество ленивых учеников», а потом – «нужное количество прилежных учеников».

Занятие 8

8.6. Обсуждение. Пусть А: «У Винни-Пуха хорошее настроение»; Б: «Винни-Пух хорошенько подкрепился». В какую строчку таблицы истинности надо посмотреть? Ответ. Не прав.

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