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

Занятие 9
Метаголоволомки
Ничего не найдено, — опять говорил
себе
Пьер, — ничего
не
придумано.
Знать мы можем только то, что ни-
чего не знаем. И это высшая степень
человеческой премудрости.
Лев Толстой. «Война и мир»
В большинстве задач для школьников требуется найти ответ на во-
прос, пользуясь данными задачи. В современных задачах теории ин-
формации ставится вопрос о вопросе: возможно ли по имеющейся ин-
формации ответить на данный вопрос?
С такой постановкой задачи мы встречаемся при определении ми-
нимального количества взвешиваний (вопросов), необходимых для на-
хождения фальшивой монеты (задуманного числа). Интерес в таких
задачах обычно представляет конструктивная часть, а для доказатель-
ства минимальности найденного числа взвешиваний достаточно срав-
нить количество возможных вариантов ответа (монет, пар монет и т. п.)
с количеством информации, полученной в результате определенного
числа взвешиваний. Задачам на взвешивание посвящен отдельный вы-
пуск нашей серии.
Основу же нашего занятия составляют метаголоволомки, т. е. голо-
воломки о головоломках. В их условии сообщается, что некто по име-
ющейся информации может или не может установить истину. Совсем
простая задача 9.1 демонстрирует, насколько информативным может
быть факт неоднозначности ответа. В задаче следующего уровня 9.2
количество информации постепенно увеличивается, и ранее неотличи-
мые ситуации становятся отличимыми.
Большинство метаголоволомок довольно сложны. Как к ним под-
ступаться? Для начала можно поставить себя на место решающего го-
ловоломку и поразбираться с частными случаями. В обсуждении зада-
чи 9.3 явно описано, с какими именно; в задаче 9.7 можно как попало
поставить рыцарей и лжецов и записать их ответы и т. п. А затем по-
лезно задать себе вопросы: «Почему имевшейся информации оказалось
(не)достаточно? Что нового в такой-то информации?» Если вариантов
немного, бывает проще всего полностью их перебрать (в задаче 9.2 рас-
82

смотрены все разложения числа 36 на три множителя, в задаче 9.6 —
все возможности племенной принадлежности двух островитян, в зада-
че 9.8 — все возможные ответы на вопрос).
К метаголоволомкам можно отнести и задачи о мудрецах, пооче-
редно сообщающих, могут ли они определить цвет своего колпака, чис-
ло на карточке и т. п. Дополнительная сложность этих задач заклю-
чается в возрастающей с каждым высказыванием глубине рекурсии
(А знает, что Б знает, что В не знаетff), им посвящено следующее за-
нятие. Задача 9.4 их напоминает лишь сюжетом, так как мудрец в ней
высказался всего один раз. А вот мирные жители в задаче 9.11 хоть
и не названы мудрецами, ими являются, и сложность именно в том,
что приходится анализировать, кто что знает в момент произнесения
очередной реплики.
Две последние задачи занятия не являются метаголоволомками.
Задача 9.10 служит мостиком от задачи 9.1 к задачам с неоднозначны-
ми данными, в которых предлагается определить, можно ли по имею-
щейся информации однозначно ответить на некоторый вопрос. Подбор-
ку таких задач, составленную А. В. Шаповаловым для подготовки мос-
ковских школьников к заключительному этапу Всероссийской олим-
пиады, можно найти по ссылке http://www.ashap.info/Uroki/Mosbory/
2014v/index.html. Задача 9.11 — мостик к следующему занятию о муд-
рецах.

жүктеу/скачать 1.3 Mb.

Достарыңызбен бөлісу: