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

Задача 8.11*. У профессора есть n утверждений А₂,…, А_n. О том, что все эти утверждения равносильны, знает только он. Профессор по очереди дает ученикам для доказательства такие теоремы: A_i ⇒ A_j. Нельзя давать теорему, если она следует из ранее доказанных. Какое наибольшее число теорем могут доказать ученики, если: 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 к задачам с неоднозначными данными, в которых предлагается определить, можно ли по имеющейся информации однозначно ответить на некоторый вопрос. Подборку таких задач, составленную А. В. Шаповаловым для подготовки московских школьников к заключительному этапу Всероссийской олимпиады, можно найти по ссылке http://www.ashap.info/Uroki/Mosbory/2014v/index.html. Задача 9.11 – мостик к следующему занятию о мудрецах.

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

Ответ. 6 или 12. Решение. Каждое из названных произведений можно получить двумя способами: 6 = 1 · 6 = 2 · 3, 12 = 2 · 6 = 3 · 4. Отсутствие других ответов проверяется перебором всевозможных произведений. Его можно сократить до минимума, если учесть, что простые множители 5 и 7 входят только в одноименные числа.

Задача 9.2. Встретились как-то два математика и разговорились:

А: «У меня трое сыновей».

Б: «Сколько им лет?»

А: «Произведение их возрастов равно 36. А сумма их возрастов равна номеру твоего дома».

Б: «Я все равно не знаю, сколько лет каждому».

А: «Мой старший сын рыжий».

После этого Б смог определить, сколько лет сыновьям А. Сколько же?

Обсуждение. Конец задачи звучит парадоксально. Цвет волос старшего сына никак не связан с его возрастом! Но поскольку после последней фразы первого математика второй смог определить возраста сыновей, какая-то информация в ней все же была. Какая? Существование старшего среди трех сыновей.

Ответ. 2, 2 и 9 лет.