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

Занятие 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 лет.

Решение. Перечислим тройки натуральных чисел с произведением 36: 1, 1, 36; 1, 2, 18; 1, 3, 12; 1, 4, 9; 1, 6, 6; 2, 2, 9; 2, 3, 6; 3, 3, 4. Суммы чисел в этих тройках равны соответственно 38, 21, 16, 14, 13, 13, 11, 10. Если бы номер дома встречался среди сумм единственный раз, второй математик сразу бы определил возраста сыновей. Но он не смог этого сделать, поэтому номер его дома 13, а возможные возраста сыновей – 1, 6 и 6 лет или 2, 2 и 9 лет. Только во втором случае среди сыновей есть старший, поэтому им 2, 2 и 9 лет.

Комментарий. Подумайте, изменятся ли решение и ответ от такой перестановки реплик:

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

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

А: «Сумма их возрастов равна номеру твоего дома. Мой старший сын рыжий».

Задача 9.3. За столом сидело несколько жителей острова рыцарей и лжецов. Путешественник спросил каждого про его ближайших соседей. Каждый ответил: «У меня оба соседа – лжецы». Путешественник сказал: «Если бы вас было на одного больше или на одного меньше, я бы смог узнать, сколько среди вас рыцарей. А так не могу». Сколько человек было за столом?

Обсуждение. Обычно в задачах про рыцарей и лжецов известно количество участников и требуется только определить, кто есть кто. Попробуем и на этот раз для начала разобраться, как могли сидеть рыцари и лжецы, для небольшого количества сидящих. Ясно, что за столом сидело не менее трех человек. Как могли сидеть трое? А четверо? Пятеро? Шестеро? Семеро? Рано или поздно становится понятно, почему при достаточно большом количестве сидящих количество рыцарей может быть различным.

Ответ. 6.

Решение. Рыцари могут сидеть за столом только по одному между двумя лжецами, а лжецы – либо по одному, либо по двое. Поэтому трое, четверо и пятеро сидящих могут расположиться единственным образом (см. рис. 18).

Рис. 18

Шестеро сидящих могут расположиться двумя способами (см. рис. 19), семеро – единственным (см. рис. 20).

Рис. 19

Рис. 20

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

Задача 9.4. Два мудреца написали на семи карточках числа от 5 до 11. После этого они перемешали карточки, первый мудрец взял себе три карточки, второй взял две, а две оставшиеся карточки они не глядя спрятали в мешок. Изучив свои карточки, первый мудрец сказал второму: «Я знаю, что сумма чисел на твоих карточках четна!» Какие числа написаны на карточках первого мудреца?

Задача 9.5. Один из двух братьев-близнецов по имени Джон совершил преступление. Известно, что по крайней мере один из близнецов всегда лжет. Судья спросил у братьев по очереди: «Вы – Джон?» Первый ответил: «Да». Второй тоже что-то ответил. После этого судья смог определить, кто из них на самом деле Джон. Определите это и вы.

Задача 9.6. На острове живут два племени: рыцарей и лжецов. Путешественник встретил двух островитян и спросил одного из них: «Вы оба рыцари?» Тот ответил «да» или «нет». Путешественник не смог определить, кто перед ним, и спросил у того же человека: «Вы из одного племени?» Тот ответил «да» или «нет», и теперь путешественник понял, из какого племени каждый из островитян. Кого он встретил?

Задача 9.7. Путешественник посетил деревню, каждый житель которой либо всегда говорит правду, либо всегда лжет. Все жители деревни встали в круг лицом к центру, и каждый сказал путешественнику про соседа справа, правдив ли тот. На основании этих сообщений путешественник смог однозначно определить, какую долю от всех жителей составляют лжецы. Определите и вы, чему она равна.

Задача 9.8. Путешественник на острове рыцарей и лжецов пришел в гости к своему знакомому рыцарю и увидел его за круглым столом с пятью гостями.

– Интересно, а сколько среди вас рыцарей? – спросил он.

– А ты задай каждому какой-нибудь вопрос и узнай сам, – посоветовал один из гостей.

– Хорошо. Пусть каждый ответит на вопрос: кто твои соседи? – спросил путешественник.