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

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

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

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

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

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

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

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

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

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

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

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

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

Основу же нашего занятия составляют метаголоволомки, т. е. головоломки о головоломках. В их условии сообщается, что некто по имеющейся информации может или не может установить истину. Совсем простая задача 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 – мостик к следующему занятию о мудрецах.