В США, Британии и Австралии в 1980-х – 1990-х годах была популярна интеллектуальная телеигра Blockbusters, где игровое поле было поделено на шестиугольники, в каждом из которых содержалась буква. Участники игры выбирали буквы, а ведущий задавал вопрос, ответ на который начинался на выбранную букву.
Например: какая передовая область математических исследований, а также какой процесс, проходящий во время приготовления эспрессо, называется словом на букву «П»?
Ответ: перколяция, или просачивание. Перколяция как область исследований математики зародилась в статистической физике. Она занимается вопросом проникновения жидкостей через пористые материалы. Французский математик Юго Дюминиль-Копен в 2022 году получил филдсовскую медаль за работу в этой области.
А сегодняшняя загадка связана с решёткой из шестиугольников следующего вида:
На картинке изображён ромб размером 10х10 шестиугольников, вокруг которого идёт ещё один ряд шестиугольников, обозначающий его границы. Верхний правый и нижний левый участки границы окрашены синим. Левый верхний и правый нижний участки остались белыми.
Допустим, для каждого шестиугольника нашего ромба мы каким-либо образом выберем один из двух цветов: белый или синий. Тогда произойдёт одно из двух. Либо появится путь из синих шестиугольников, соединяющий синие участки границы, например, как тут:
Либо такого пути не появится, например:
Ромб содержит 100 шестиугольников. Поскольку каждый из них может быть белым или синим, то общее количество конфигураций раскраски ромба составляет 2 х 2 х 2 х … х 2 – и так сто раз, то есть, 2100, или примерно 1 000 000 000 000 000 000 000 000 000 000.
Какова доля вариантов такой раскраски, в которых существует путь, соединяющий два синих участка границы ромба?
Решение
Ровно 50%.
Доказательство основывается на простой идее: если существует путь из синих шестиугольников, соединяющий синие участки границы ромба, тогда не существует пути из белых шестиугольников, соединяющего белые участки границы. А если не существует пути из синих шестиугольников, соединяющего синие участки границы ромба, тогда существует путь из белых шестиугольников, соединяющий белые участки границы.
Суть игры Blockbusters была построена именно на этом: участникам при помощи правильных ответов на вопросы нужно было либо построить путь, ведущий сверху вниз, либо путь, ведущий слева направо. Не могло быть такой ситуации, когда существуют оба пути, или когда ни одного пути не существует – это гарантировало выигрыш одной из сторон.
Однако одной этой идеи недостаточно. Надо также доказать, что синий путь существует ровно в половине конфигураций раскраски ромба. Для этого начнём с одной произвольной конфигурации – например, такой, как на картинке ниже. На ней есть синий путь, соединяющий синие участки границы, и нет белого пути, соединяющего белые:
Инвертируем ситуацию, поменяв все синие шестиугольники на белые, а белые – на синие:
Зеркально отразим ромб так, чтобы его левая верхняя часть оказалась левой нижней, а правая верхняя – правой нижней:
То есть, мы начали с конфигурации, в которой есть синий путь, соединяющий синие границы, и превратили её в конфигурацию, в которой нет синего пути, соединяющего синие границы. А если мы повторим нашу процедуру – поменяем цвета на противоположные, и отразим ромб по горизонтали – то вернёмся к изначальной конфигурации.
Наоборот, если бы мы начали с конфигурации, в которой нет синего пути, соединяющего синие границы, это означало бы, что в ней есть путь, соединяющий белые границы. Повторив процедуру «меняем цвета, отражаем ромб», мы бы пришли к конфигурации, в которой был бы синий путь, соединяющий синие границы. Повторив этот процесс снова, мы вернулись бы к первоначальной конфигурации.
Следовательно, мы можем заключить, что какую бы конфигурацию раскраски ромба мы ни выбрали, она будет частью пары конфигураций. В одной из этих двух конфигураций есть синий путь, соединяющий синие границы, а в другой – белый путь, соединяющий белые.
Как упоминалось ранее, не существует такой конфигурации, в которой одновременно есть и синий путь между синими границами, и белый путь между белыми.
А если у каждой конфигурации есть пара, то количество конфигураций, в которых есть синий путь между синими границами, должно равняться количеству конфигураций, в которых есть белый путь между белыми границами. Поэтому доля конфигураций, содержащих синий путь, равна ровно 50%.
При чём же тут кофе?
Как я уже упоминал, перколяция как область исследований занимается вопросом проникновения жидкостей через пористые материалы. Шестиугольная решётка – это модель материала, а каждая синяя ячейка может, например, обозначать наличие поры, в которую может просочиться жидкость. Теоретикам перколяции интересны такие вопросы, как, например, в каком проценте от общего числа всех возможных конфигураций сетки есть синий путь?
Как следует из задачки, когда вероятность того, что шестиугольник будет синим, а не белым, равна 50%, тогда нужный путь есть у 50% конфигураций. А что будет, если мы поменяем вероятность того, что шестиугольник может быть синим – уменьшим или увеличим её? А что, если у нас будет больше двух вариантов состояний каждого шестиугольника? Ответы на подобные вопросы помогли учёным понять поведение материалов при фазовых переходах – когда одна базовая структура материала внезапно меняется на другую. Эти ответы находят применение в физике, биологии, экологии и теории сетей.
Доказательство основывается на простой идее: если существует путь из синих шестиугольников, соединяющий синие участки границы ромба, тогда не существует пути из белых шестиугольников, соединяющего белые участки границы. А если не существует пути из синих шестиугольников, соединяющего синие участки границы ромба, тогда существует путь из белых шестиугольников, соединяющий белые участки границы.
Суть игры Blockbusters была построена именно на этом: участникам при помощи правильных ответов на вопросы нужно было либо построить путь, ведущий сверху вниз, либо путь, ведущий слева направо. Не могло быть такой ситуации, когда существуют оба пути, или когда ни одного пути не существует – это гарантировало выигрыш одной из сторон.
Однако одной этой идеи недостаточно. Надо также доказать, что синий путь существует ровно в половине конфигураций раскраски ромба. Для этого начнём с одной произвольной конфигурации – например, такой, как на картинке ниже. На ней есть синий путь, соединяющий синие участки границы, и нет белого пути, соединяющего белые:
Инвертируем ситуацию, поменяв все синие шестиугольники на белые, а белые – на синие:
Зеркально отразим ромб так, чтобы его левая верхняя часть оказалась левой нижней, а правая верхняя – правой нижней:
То есть, мы начали с конфигурации, в которой есть синий путь, соединяющий синие границы, и превратили её в конфигурацию, в которой нет синего пути, соединяющего синие границы. А если мы повторим нашу процедуру – поменяем цвета на противоположные, и отразим ромб по горизонтали – то вернёмся к изначальной конфигурации.
Наоборот, если бы мы начали с конфигурации, в которой нет синего пути, соединяющего синие границы, это означало бы, что в ней есть путь, соединяющий белые границы. Повторив процедуру «меняем цвета, отражаем ромб», мы бы пришли к конфигурации, в которой был бы синий путь, соединяющий синие границы. Повторив этот процесс снова, мы вернулись бы к первоначальной конфигурации.
Следовательно, мы можем заключить, что какую бы конфигурацию раскраски ромба мы ни выбрали, она будет частью пары конфигураций. В одной из этих двух конфигураций есть синий путь, соединяющий синие границы, а в другой – белый путь, соединяющий белые.
Как упоминалось ранее, не существует такой конфигурации, в которой одновременно есть и синий путь между синими границами, и белый путь между белыми.
А если у каждой конфигурации есть пара, то количество конфигураций, в которых есть синий путь между синими границами, должно равняться количеству конфигураций, в которых есть белый путь между белыми границами. Поэтому доля конфигураций, содержащих синий путь, равна ровно 50%.
При чём же тут кофе?
Как я уже упоминал, перколяция как область исследований занимается вопросом проникновения жидкостей через пористые материалы. Шестиугольная решётка – это модель материала, а каждая синяя ячейка может, например, обозначать наличие поры, в которую может просочиться жидкость. Теоретикам перколяции интересны такие вопросы, как, например, в каком проценте от общего числа всех возможных конфигураций сетки есть синий путь?
Как следует из задачки, когда вероятность того, что шестиугольник будет синим, а не белым, равна 50%, тогда нужный путь есть у 50% конфигураций. А что будет, если мы поменяем вероятность того, что шестиугольник может быть синим – уменьшим или увеличим её? А что, если у нас будет больше двух вариантов состояний каждого шестиугольника? Ответы на подобные вопросы помогли учёным понять поведение материалов при фазовых переходах – когда одна базовая структура материала внезапно меняется на другую. Эти ответы находят применение в физике, биологии, экологии и теории сетей.
