Квант 2023, №8 · Страницы

МАТЕМАТИЧЕСКИЙ КРУЖОК

Мудрецы на графе

К.КОХАСЬ, А.ЛАТЫШЕВ

НАЧНЕМ С ТОГО, ЧТО НАПОМНИМ читателям загадку о шляпах, очень известную и уже почти ставшую классической. Загадка. Два мудреца сидят друг напротив друга. Каждому из них надевают шляпу черного или белого цвета так, что каждый не видит свою шляпу, но видит шляпу напарника. Не общаясь и не передавая никаких сигналов, они должны по команде одновременно назвать предполагаемый цвет своей шляпы. Мудрецы заранее были предупреждены о правилах и имели возможность посовещаться. Как им следует действовать, чтобы заведомо хотя бы один из них угадал свой цвет? Ответ удивителен и красив. Не надо быть мудрецом, чтобы предсказать, что при проведении этого шоу шляпы окажутся либо одинакового цвета, либо различного. Пусть первый мудрец проверяет первую гипотезу, пользуясь стратегией что вижу, то и говорю, а второй – вторую: называю цвет, противоположный тому, который вижу. Очевидно, что заведомо кто-то из них (причем только один) угадает. Сразу отметим одну тонкость: хотя один из мудрецов заведомо угадает, но сами они в момент угадывания не знают и не могут знать, кто же именно окажется этим счастливцем, – ведь оба не имеют никакой информации о цвете своей шляпы. Не так давно в «Кванте» уже рассказывалось об обобщенной игре в угадывание шляп и рассматривался вопрос о том, как следует действовать n мудрецам в аналогичном тесте, если им дают шляпы n (или даже больше) цветов (см. статью К.Кохася «Принесите еще шляп!» в «Кванте» №11 за 2019 г.). В этой статье мы рассмотрим другое обобщение этой загадки. А именно, будем решать следующую общую задачу. Задача. Пусть дан произвольный граф G, т.е. схема, вроде той, что показана на рисун-

DOI: https://doi.org/10.4213/kvant20230803

Рис. 1. Какой-то граф G

ке 1. Кружочками – они называются вершинами графа – обозначены комнаты, а линиями – это ребра графа – обозначены оптические кабели, соединяющие комнаты. Комнаты, соединенные линиями, будем называть соседними. В каждой комнате находится один мудрец, благодаря оптическим кабелям он видит, что происходит в соседних комнатах.$^{1}$ Все мудрецы знакомы друг с другом, различают друг друга, знают, какой у них граф и кто в какой вершине находится. Дальше с ними проводят тест, аналогичный тому, что описан в загадке. Каждому мудрецу надевают шляпу черного или белого цвета так, что каждый не видит свою шляпу, но благодаря оптическим кабелям видит шляпы своих соседей. Не общаясь и не передавая никаких сигналов, мудрецы должны по команде одновременно назвать предполагаемый цвет своей шляпы. Перед тестом мудрецы проводят совещание, на котором договариваются о своих стратегиях. Вопрос, который нас интересует, – какое наибольшее количество мудрецов сможет заведомо угадать свой цвет? Честно говоря, эта постановка вопроса совершенно непонятна. Давайте разбираться, о чем же на самом деле тут спрашивается. Во-первых, для ясности будем считать, что организатором этого теста является чертик, который играет против мудрецов. Чертик незримо присутствует на совещании (подсматривает и подслушивает) и узнает стратегии всех мудрецов. Если каждому из n мудрецов дают шляпу одного из двух цветов, то всего имеется $2^{n}$ «раскладов» шляп. При проведении теста чертик старается выбрать

1 Кажется, в реальности оптические кабели работают по-другому, видимо, там должно быть еще какое-то оборудование, о котором мы не упомянули.

Живописцы часто приходят в отчаяние от своего подражания природе, видя, что их картины не имеют той рельефности и той живости, которую имеют предметы, видимые в зеркале. Леонардо да Винчи …что касается цвета – в этой области никто до сих пор не может похвастаться успехом. Христиан Гюйгенс …тела приобретают свой цвет отрицательным способом: окраска – следствие не прибавления, а исключения. Джон Тиндаль Ньютон впервые дал действенное учение о цветах, на основании которого он сам нашел огромное число новых фактов… Леонид Мандельштам

С восприятием света связано множество интересных явлений, в которых тесно переплетаются и физические, и физиологические процессы… Ричард Фейнман

Человек … – узник разума, не способного постичь, как можно верно изобразить объемный трехмерный мир на плоскости, на листе бумаги, холсте, стене… Борис Раушенбах

Радость видеть и понимать – самый прекрасный дар природы. Альберт Эйнштейн

А так ли хорошо знакомы вам

ФИЗИКА + ЖИВОПИСЬ

Ох, уж эти художники! Сколько загадок невольно задали они ученым, пытавшимся разобраться, как и почему творения живописцев воздействуют на зрителей. Столетиями шли споры, как осмыслить бинокулярное зрение, имеется ли рациональная основа под методами пространственных художественных построений, каковы особенности зрительного восприятия, что из себя представляет такая необычная категория, как цвет… Достижения науки, и не в последнюю очередь физики, оснащение все более изощренной исследовательской аппаратурой не раз позволяли продвинуться в понимании порой неприступных для естественно-научного анализа проблем. Однако какие интереснейшие открытия были совершены на этом тернистом пути! Присоединяйтесь же и вы к увлекательной научно-художественной экскурсии.

Вопросы и задачи

1. Живописец, рисуя пейзаж с натуры, прикидывает, что больше: облако или его полная тень? А что полагаете $вы?^{2.}$ Если расположенную горизонтально спичку рассматривать через цилиндри-

?

ческий стакан с водой, то ее длина кажется больше диаметра стакана, а толщина не изменяется. Если в том же опыте спичку расположить вертикально, то ее длина не меняется, а толщина возрастает. Как это $объяснить?^{3.}$ Почему близорукий художник может различать более мелкие детали, чем живописец с нормальным $зрением?^{4.}$ Редко когда удается точно налить воду в далеко отстоящие друг от друга стаканы, если один глаз плотно закрыт. С чем это $связано?^{5.}$ Как объяснить прием, применяемый в живописи: предметы, которые должны казаться нам далекими, изображаются размытыми, без четких контуров и более бледными, чем близлежащие $предметы?^{6.}$ Почему изображение предмета в воде всегда менее яркое, чем сам $предмет?^{7.}$ Во время одного из погружений с аквалангом его изобретатель Жак Ив Кусто случайно порезал руку и с удивлением увидел, что из нее течет зеленая кровь. Как это $понимать?^{8.}$ Действительно ли зеленый лист – зеленый?