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

К оглавлению

21

Задача 8.6. Иа-Иа считает, что у Винни-Пуха хорошее настроение бывает тогда и только тогда, когда Винни-Пух хорошенько подкрепился. Съев всё, что было у Кролика,

Винни-Пух застрял в норе, и его настроение сразу испортилось. Прав ли Иа-Иа?

Задача 8.7. Будем считать, что трава зеленая, а небо голубое. Определите, какие из данных высказываний истинны, а какие ложны:

1) Если трава зеленая, то небо голубое.

2) Если трава зеленая, то небо оранжевое.

3) Если трава оранжевая, то небо зеленое.

4) Если трава оранжевая, то небо голубое.

5) Трава зеленая тогда и только тогда, когда небо голубое.

6) Трава зеленая тогда и только тогда, когда небо оранжевое.

7) Трава оранжевая тогда и только тогда, когда небо зеленое.

8) Трава оранжевая тогда и только тогда, когда небо голубое.

Задача 8.8. В лесу живут только ляпусики и мордасики. Равносильны ли для обитателей леса три утверждения:

(1) все ляпусики кузявые;

(2) если кто-то некузяв, то он мордасик;

(3) никто, кроме мордасиков, не может быть некузявым?

Задача 8.9. Объект охраняют пятеро часовых: А, Б, В, Г и Д. При этом справедливы следующие утверждения:

1) Если А спит, то и Б спит.

2) Хотя бы один из Г и Д спит.

3) Ровно один из Б и В спит.

4) В спит тогда и только тогда, когда спит Г.

5) Если Д спит, то А и Г тоже спят.

Перечислите всех спящих часовых.

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

Указание. Докажите равносильность трех утверждений по кругу: 1 ⇒ 2 ⇒ 3 ⇒ 1.

Задача 8.11*. У профессора есть n утверждений А,…, А. О том, что все эти утверждения равносильны, знает только он. Профессор по очереди дает ученикам для доказательства такие теоремы: A ⇒ A. Нельзя давать теорему, если она следует из ранее доказанных. Какое наибольшее число теорем могут доказать ученики, если: 1) n = 3; 2) n = 4; 3) в общем случае?

Занятие 9
Метаголоволомки

Ничего не найдено, – опять говорил себе Пьер, – ничего не придумано. Знать мы можем только то, что ничего не знаем. И это высшая степень человеческой премудрости.

Лев Толстой. «Война и мир»

В большинстве задач для школьников требуется найти ответ на вопрос, пользуясь данными задачи. В современных задачах теории информации ставится вопрос о вопросе: возможно ли по имеющейся информации ответить на данный вопрос?

С такой постановкой задачи мы встречаемся при определении минимального количества взвешиваний (вопросов), необходимых для нахождения фальшивой монеты (задуманного числа). Интерес в таких задачах обычно представляет конструктивная часть, а для доказательства минимальности найденного числа взвешиваний достаточно сравнить количество возможных вариантов ответа (монет, пар монет и т. п.) с количеством информации, полученной в результате определенного числа взвешиваний. Задачам на взвешивание посвящен отдельный выпуск нашей серии.

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

Большинство метаголоволомок довольно сложны. Как к ним подступаться? Для начала можно поставить себя на место решающего головоломку и поразбираться с частными случаями. В обсуждении задачи 9.3 явно описано, с какими именно; в задаче 9.7 можно как попало поставить рыцарей и лжецов и записать их ответы и т. п. А затем полезно задать себе вопросы: «Почему имевшейся информации оказалось (не)достаточно? Что нового в такой-то информации?» Если вариантов немного, бывает проще всего полностью их перебрать (в задаче 9.2 рассмотрены все разложения числа 36 на три множителя, в задаче 9.6 – все возможности племенной принадлежности двух островитян, в задаче 9.8 – все возможные ответы на вопрос).

К метаголоволомкам можно отнести и задачи о мудрецах, поочередно сообщающих, могут ли они определить цвет своего колпака, число на карточке и т. п. Дополнительная сложность этих задач заключается в возрастающей с каждым высказыванием глубине рекурсии (А знает, что Б знает, что В не знает…), им посвящено следующее занятие. Задача 9.4 их напоминает лишь сюжетом, так как мудрец в ней высказался всего один раз. А вот мирные жители в задаче 9.11 хоть и не названы мудрецами, ими являются, и сложность именно в том, что приходится анализировать, кто что знает в момент произнесения очередной реплики.

Две последние задачи занятия не являются метаголоволомками. Задача 9.10 служит мостиком от задачи 9.1 к задачам с неоднозначными данными, в которых предлагается определить, можно ли по имеющейся информации однозначно ответить на некоторый вопрос. Подборку таких задач, составленную А. В. Шаповаловым для подготовки московских школьников к заключительному этапу Всероссийской олимпиады, можно найти по ссылке . Задача 9.11 – мостик к следующему занятию о мудрецах.


Задача 9.1. Из чисел 1,2, 3,4, 5, 6, 7 Незнайка задумал два числа и сообщил Знайке их произведение. Знайка не смог отгадать задуманные числа. Какое произведение мог сообщить Незнайка?

21