21
«КВАНТ»
ДЛЯ
МЛАДШИХ
ШКОЛЬНИКОВ
Знание – сила!
С.КУЗНЕЦОВ
ВЭТОЙ СТАТЬЕ МЫ ОБСУДИМ НЕСКОЛЬКО задач, слегка необычных с математической точки зрения. В этих задачах нам будет интересно не только истинны или ложны некоторые высказывания, но и знают ли об истинности этих высказываний персонажи, действующие в задачах. Задача 1. Илье Муромцу, Добрыне Никитичу и Алеше Поповичу за верную службу дали 6 монет: 3 золотых и 3 серебряных. Каждому досталось по две монеты. Илья Муромец не знает, какие монеты достались Добрыне, а какие Алеше, но знает, какие монеты достались ему самому. (Также Илья знает, что монет всего 6, по 3 каждого металла, и что каждому досталось по две монеты.) Требуется задать Илье Муромцу один вопрос, предполагающий ответ «да» или «нет», и по ответу на этот вопрос выяснить, какие монеты ему достались. С виду кажется, что задача неразрешима: вариантов того, какие монеты у Ильи, три (две золотые, две серебряные, золотая и серебряная), а вариантов ответа всего два, «да» или «нет». Но есть и третий возможный ответ – «не знаю». Чтобы получить его, нужно спрашивать не о монетах Ильи, а о монетах других богатырей. Однако тогда может показаться, что ответ будет всегда «не знаю»: ведь даже в условии прямо сказано, что Илья Муромец не знает о монетах Добрыни и Алеши. Тем не менее, некоторую информацию об этих монетах Илья может вычислить, зная только свои монеты. Например, если у Ильи Муромца две золотые монеты, то он знает, что осталась только одна золотая монета. Значит, ни у Добрыни, ни у Алеши не может оказаться двух золотых монет. Зато заведомо у кого-то из них обе монеты серебряные. Это соображение и приводит нас к ответу: нужно задать вопрос «Верно
ли, что у кого-то их двух других богатырей обе монеты – серебряные?» Запишем возможные ситуации коротко: буква «З» означает золотую монету, «С» – серебряную. Сначала идут монеты Ильи, потом Добрыни, потом Алеши. Например, «ЗЗ;СС;ЗС» означает, что у Ильи 2 золотые монеты, у Добрыни 2 серебряные, а у Алеши 1 золотая и 1 серебряная. На рисунке 1 возможные ситуации разделены на
Рис. 1
три группы. В каждой группе ситуации неразличимы с точки зрения Ильи Муромца: он-то видит только свои монеты. Кроме того, ситуации расцвечены: зеленым цветом обозначены те, в которых истинный ответ на наш вопрос «да»; красным – в которых ответ «нет». Теперь видно, что в средней группе, когда у Ильи золотая и серебряная монеты, есть как «красные», так и «зеленые» ситуации. Значит, Илья даже теоретически не может, опираясь на знания о своих монетах, ответить на вопрос, и он скажет «не знаю». В верхней группе обе ситуации «зеленые», и Илья, проведя такое же рассуждение, как и мы сейчас, ответит «да». В нижней группе, наоборот, обе ситуации «красные», и ответ будет «нет». Чтобы наши рассуждения имели силу, нужны два предположения о богатыре, которого мы спрашиваем: 1. Богатырь честен, т.е. отвечает на наши вопросы правдиво.
22
КВАНТ 2017/№6
- Богатырь умен, т.е. говорит «не знаю» только в том случае, когда получить ответ, исходя из доступной ему информации, теоретически невозможно. Это условие позволяет Илье Муромцу использовать косвенное знание о монетах других богатырей. Второе условие не так безобидно, как может показаться на первый взгляд. Чтобы осознать это, посмотрим, например, на шахматную игру и зададимся вопросом: у какого из игроков (играющего за черных или за белых) есть стратегия, позволяющая заведомо, независимо от коварства противника, выиграть или хотя бы свести игру к ничьей? Количество всевозможных шахматных партий хоть и астрономически велико, но все-таки не бесконечно. Значит, теоретически возможно проанализировать все возможные партии и дать ответ на этот вопрос (кроме этого, можно доказать, что либо ровно у одного из игроков есть выигрывающая стратегия, либо у обоих есть стратегия, приводящая к ничьей). Этот ответ будет логически следовать из правил игры, т.е., по нашему условию, должен быть известен любому, кто эти правила знает. В реальности, однако, ответ неизвестен никому. Другой пример, более близкий к математике: поскольку все теоремы, скажем, школьного курса геометрии логически следуют из аксиом, то по нашему условию получилось бы, что тот, кто выучил все аксиомы, автоматически знает все теоремы. На самом деле, конечно, для этого требуется более длительное обучение, а всех возможных теорем не знает никто. Эта трудность обычно называется проблемой логического всезнания. Она возникает в случаях, когда число возможных ситуаций настолько велико, что человек или даже компьютер оказывается неспособным их перебрать, или когда оно вообще бесконечно. В наших примерах это число невелико, и мы можем смело пользоваться вторым условием. Теперь обсудим классическую задачу о чумазых детях. Задача 2. Несколько детей вернулись с прогулки, и папа сказал, что у некоторых
(хотя бы у одного) из них лица перепачканы грязью. Каждый ребенок видит лица других детей, но не свое собственное. Папа спрашивает, знает ли кто-нибудь из детей, что он сам чумазый. Дети отвечают «нет». Потом папа задает тот же вопрос еще раз, потом еще раз… Поймет ли кто-то из детей, что он сам чумазый? Казалось бы, ничего не меняется, и дети всегда будут говорить «нет». Однако каждый раз ребенок получает знание о незнании других, и эта информация может помочь ему догадаться, чумазый ли он сам. Чтобы лучше понять, что происходит, рассмотрим случай, когда детей всего трое и два из них – второй и третий – чумазые, а первый чист. Кто чумазый, а кто чистый, знаем мы (и папа), но не сами дети. Поэтому нужно рассматривать все потенциально возможные ситуации, и мы будем для краткости обозначать чумазого ребенка цифрой 1, а чистого – цифрой 0: например, 010 означает, что первый и третий чисты, второй чумаз. Возможные случаи удобно изобразить в виде куба (рис. 2). Здесь две ситуации соединены красным ком, если они неотличимы с точки зрения первого ребенка (он не знает, чумаз ли он сам, поэтому не может отличить, например, 001 от 101). Зеленые отрезки соединяют ситуации, неотличимые вторым, синие – третьим ребенком. Одной вершины в этом кубе недостает: раз сказано, что чумазые есть, случай 000 невозможен. Посмотрим теперь, что изменится после первого вопроса. В ситуациях, когда чумазый ребенок ровно один (например, 100), этот ребенок сразу понимает, что он чумазый. Значит, если все ответили «нет», то эти ситуации невозможны и, что нам особенно важно, об этом теперь знают все дети! Получается картинка, изображенная на рисунке 3.