В 2014 году профессор математики Стэнфордского университета Марьям Мирзахани в одной из своих лекций упомянула интересную математическую головоломку, но не стала давать её решение. Спустя годы появились различные вариации задачи. Однако сначала речь пойдёт о первоисточнике.

Головоломка относится к классу так называемых «бильярдных задач», изучаемых в области динамических систем. Решение текущей задачи принадлежит профессору математики университета Джонса Хопкинса Эмили Рил.

Рассмотрим квадратную комнату в плоскости XY, и пусть A («ассасин») и T («цель») — две произвольные, но фиксированные точки внутри комнаты. Предположим, что комната схожа по физическим характеристикам с бильярдным столом, так что любой «выстрел» А рикошетит от стен, причём угол падения равен углу отражения. Можно ли заблокировать любой возможный «выстрел» А в Т, разместив конечное количество аналогичных по свойствам точек («телохранителей») в комнате?

Решение

Этап 1. Перенос задачи в плоскость XY

Бильярдные траектории сложно анализировать, поэтому для упрощения задачи найдём способ заменить любую траекторию линией на плоскости. Сегодня почти каждый раз, когда в околоматематическом тексте в одном предложении упоминаются слова «квадрат», «траектория» и «линия», вероятность того, что речь идет о торе Клиффорда, составляет почти 100%. Итак, цель первого этапа решения состоит в том, чтобы каким-то образом использовать плоский тор для переноса головоломки с бильярдного стола на плоскость XY.

Изобразим комнату в виде квадрата, стены которой раскрашены в разные цвета. Это для того, чтобы не забыть, что в отличие от плоского тора ни одна из сторон этого квадрата не отождествлена. Выберем две произвольные, но фиксированные точки в квадрате, обозначающие наших персонажей A и T. Чтобы визуально различать точки, также обозначим их цветами: А — белой точкой, а Т — чёрной.

Теперь, хотя исходная комната не является плоским тором, мы можем его получить, склеив вместе четыре квадрата. Как? Прежде всего, обратите внимание, что квадрат можно отразить четырьмя разными способами.

Квадрат 1 представляет собой исходный без отражения. Обозначим его края сторонами света. Квадрат 2 получается путём отражения квадрата 1 по горизонтальной оси, так что северная и южная стороны меняются местами. Квадрат 3 получается путём отражения квадрата 1 по вертикальной оси, так что восточная и западная стороны меняются местами. Последовательно выполнив оба отражения, получаем квадрат 4. Чтобы получить тор, просто соберём четыре квадрата, как показано ниже.

Теперь перейдём к универсальному покрытию тора, то есть замостим всю плоскость.

Итак, мы перенесли задачу из квадрата в плоскость, то есть любая траектория в исходной комнате будет соответствовать отрезку на плоскости. Например, траектория от А до Т слева на рисунке ниже является прямым отрезком справа.

Этап 2. Рождение решётки

До сих пор я упускал одну деталь, но сейчас самое время указать на неё. На самом первом рисунке обозначены две точки на исходном квадрате, а поскольку они есть на исходном квадрате, они должны быть указаны и на отражённых копиях, и в замощённой плоскости.

Для наглядности также разделим отображение персонажей в плоскости по номерам квадратов.

На данный момент сосредоточимся только на том, что происходит с копиями квадрата 1. Куча повторяющихся черно-белых точек является решёткой. Более формально это будет выглядеть примерно так: для данной точки (x, y) ∈ × , решётка, порождённая (x, y), представляет собой набор точек {(x, y)+(n, m)|n,m ∈ }. Другими словами, начиная с (x, y) и двигаясь на m единиц влево/вправо и n единиц вверх/вниз, где m и n принадлежат множеству целых чисел, получаем набор точек, называемый решёткой ×.

На рисунке ниже множество точек Т в исходном квадрате создаёт решётку, обозначенную номером 1.

Аналогичную процедуру можно сделать и с А — он также генерирует свою решётку, однако она нам не понадобится. Достаточно рассмотреть оригинального «убийцу» на исходном квадрате, а не его копии. Также необходимо помнить, что нас больше интересует исходный квадрат и решётки, порождённые Т, хотя мы и получаем больше решёток из-за трёх других квадратов. Так вот, в дополнение к решётке 1, назовём решёткой 2 решётку, порождённую целью в квадрате 2, решёткой 3 — в квадрате 3, решёткой 4 — в квадрате 4. Как на рисунке ниже.

Как я уже писал выше, любой выстрел «убийцы» А по «цели» Т в исходной комнате может быть представлен отрезком линии в плоскости, идущей от «убийцы» в исходном квадрате до копии мишени в одной из четырёх решёток. Чтобы решить задачу, разработаем следующую стратегию.

Чтобы заблокировать любой выстрел в «цель», нужно заблокировать любой выстрел в каждой из четырёх решёток.

Назовём этот процесс защитой решётки. Сначала нужно защитить решётку 1, потом 2, 3 и 4. Как только найдём способ защитить решётку 1, можно применить аналогичную защиту для остальных решёток. Другими словами, если мы сможем защитить решётку 1 с помощью k «телохранителей», то понятно, что для полноценной защиты всей плоскости понадобится 4k, чтобы заблокировать любой выстрел «убийцы» в «цель».

Этап 3. Защита решётки 1

На рисунке ниже изображение решётки 1 с обозначением «убийцы» на исходном квадрате.

Чтобы упростить визуализацию, введём новую координатную плоскость, в которой «убийца» находится в начале координат.

Теперь предположим, что исходная «цель» обладает определёнными координатами (a, b) в этой плоскости. Тогда координаты «цели» в трёх других квадратах, ближайших к началу координат, будут как на рисунке:

Итак, наша главная цель — заблокировать любой выстрел «убийцы» в «цель». Для этого, естественно, нужно рассматривать ближайшие узлы решётки. Разместим «телохранителя», отмеченного красной точкой и обозначенного буквами B₁, B₂, B₃ и B₄, между «убийцей» и «целью» в каждом из четырёх ближайших квадратов. Самым простым случаем размещения является середина расстояния между A и T. Запишем точные координаты «телохранителей».

Более того, каждая точка B₁, B₂, B₃ и B₄ порождает свою решётку. Идея в том, что B₁ (и его копии), например, потенциально могут блокировать и другие выстрелы, в том числе рикошеты. В любом случае уже наверняка заблокировано четыре ближайших выстрела «убийцы» в «цель». По условиям задачи нужно защитить «цель» от любого выстрела. Сколько ещё «телохранителей» для этого нужно? Поразительно, но ответ на этот вопрос — ноль. Чтобы защитить решётку 1, нужно всего четыре «телохранителя». Теперь докажем это.

Этап 4. Доказательство достаточности

На этом этапе необходимо доказать, что любая траектория выстрела в решётке 1 должна пересекать один из узлов решётки, сгенерированной «телохранителями» B₁, B₂, B₃ и B₄.

Рассмотрим произвольный выстрел «убийцы» в «цель». На плоскости это соответствует отрезку прямой от начала координат до точки вида (a+m, b+n) для некоторых целых чисел m и n. Чтобы заблокировать этот выстрел, поместим новую точку B в середину отрезка. Таким образом, получаем координаты B — (a+m\2, b+n\2).

В зависимости от значений m и n координаты точки B будут совпадать с координатами одной из копий B₁, B₂, B₃ и B₄. Другими словами, этот новый «телохранитель» не такой уж и новый. Действительно:

Вариант 1: если и m, и n чётные, (m=2m', n=2n' для некоторых целых чисел m' и n'), тогда B=(a/2, b/2) + (m’, n’), что является точкой в решётке, порожденной B₁.

Вариант 2: если m и n нечётные (m=2m'-1, n=2n'-1 для некоторых целых чисел m' и n'), тогда B=(a-1/2, b-1/2) + (m’, n’), что является точкой в решётке, порождённой B₃.

Вариант 3: если m чётное, а n нечётное (m=2m', n=2n'-1 для некоторых целых чисел m' и n'), тогда B=(a/2, b-1/2) + (m’, n’), что является точкой в решётке, порожденной B₄.

Вариант 4: если m нечётное, а n чётное (m=2m'-1, n=2n' для некоторых целых чисел m' и n'), тогда B=(a-1/2, b/2) + (m’, n’), что является точкой в решётке, порожденной B₂.

Например, m=1 и n=2 на иллюстрации выше. В этом случае рассматриваем вариант 4, так что B=(a-1/2, b+2/2) — точка в решётке, порождённой B2. И этот «телохранитель» блокирует именно ту траекторию, которую мы видели ранее. Обратите внимание, что на среднем рисунке ниже «цель» находится в одном из квадратов, отмеченных цифрой 1, что гарантирует, что это точка в решётке 1. Более того, можно добраться до этого квадрата, начав с исходного квадрата, пройдя вверх на два квадрата, отмеченных цифрой 1, что соответствует n=2, а затем, переместившись вправо на один квадрат с номером 1, что соответствует m=1. Что и следовало доказать.

Как только мы уничтожим первых четырёх «телохранителей», мы автоматически блокируем все остальные выстрелы в первой решётке. Итого, чтобы защитить решётку 1, нужно всего четыре «телохранителя». Так что число k=4. Что замечательно, аргумент, который мы использовали для защиты решётки 1, работает для любой решётки. В частности, это означает, что мы также можем защитить все остальные решётки, используя всего по четыре «телохранителя» в каждой, т. е. в общей сложности 16.

Интерактивная демонстрация

Джереми Кун сделал интерактивную демонстрацию решения этой задачи. Серая точка «убийца», зелёная точка — «цель», а 16 красных точек — «телохранители». Ниже изображение демки. Оригинальная демка здесь.

Обратите внимание, что выстрел никогда не достигает «цели», более того, это справедливо вне зависимости от положения персонажей. Чтобы увидеть это, просто обновите вкладку. «Убийца» и «цель» будут случайным образом менять позиции, «телохранители» будут менять своё положение соответствующим образом. Если перетащить зелёную точку, «телохранители» также будут менять своё положение.

А что если комната не квадратная?

Австралийский писатель-фантаст Грег Иган посмотрел на задачу более широко. Сначала он рассмотрел вырожденный случай, в котором две точки располагаются между двумя параллельными отражающими поверхностями. В этом случае бесконечное количество траекторий выстрела можно заблокировать, используя всего четыре точки («телохранителя»).

Зеркальные отражения синей точки, создаваемые двумя отражающими поверхностями, состоят из двух равноотстоящих друг от друга одномерных решёток. Отражение в одной поверхности, а затем в другой приводит к перемещению всего, что отражается, на удвоенное расстояние между зеркалами, поэтому все изображения синей точки (вместе с самой синей точкой) образуют два равноотстоящих друг от друга набора, причём один набор для чётного числа отражений (включая ноль), а другой — для нечётного числа отражений.

Для каждой одномерной решётки можно заблокировать все траектории от красной точки к точкам этой решётки всего двумя препятствиями. Почему двумя? Если бы зеркал не было и все изображения в выбранной нами решётке были реальными объектами, можно было бы заблокировать траектории к ним, поместив препятствия на полпути между каждым из них и красной точкой. Но размещение препятствий на полпути к последовательности равномерно расположенных точек означает, что сами препятствия также будут располагаться равномерно, но с половиной расстояния между ними. Итак, можно разместить одно физическое препятствие между зеркалами, которое будет иметь тот же эффект, что и все виртуальные препятствия с чётными номерами, и другое, которое будет иметь тот же эффект, что и все виртуальные препятствия с нечётными номерами.

Разобравшись с простейшим примером этого явления, обобщим его на другие варианты расположения отражающих поверхностей.

А что, если комната представляет собой равносторонний треугольник, а не квадрат? Получается, что набор изображений «цели» будет представлять собой объединение шести отдельных решёток, а не четырёх, поэтому всего потребуется 24 телохранителя.

На анимациях показано, как 24 «телохранителя» (зелёные) блокируют различные выстрелы в треугольной комнате для фиксированных положений «цели» (синий) и «убийца» (красный), и для варианта с переменными позициями персонажей.

На рисунке ниже показаны шесть решёток изображений одной точки, движущейся в зеркальной треугольной комнате. Изображениям комнаты присваивается шесть различных цветов в зависимости от того, к какой решётке принадлежит изображение содержащейся в них точки. Чёрные параллелограммы (домены) обозначают области решёток. Место начала и конца домена определяется произвольно в зависимости от того, где мы решили разместить один угол параллелограмма, а размер и направление сторон определяются решёткой. Но все шесть решёток здесь являются просто транслированными копиями друг друга, поэтому ко всем из них применим один и тот же выбор доменов.

Точка в одном из доменов может лежать внутри треугольника любого из шести цветов, но если мы выберем один треугольник (скажем, жёлтый в центре) для обозначения физической комнаты, между этим треугольником и любым другим будет однозначное отождествление, которое мы сможем провести, неоднократно отражая жёлтый треугольник.

Если комната представляет собой правильный шестиугольник, отражения «цели» будут представлять собой объединение шести различных решёток, но есть еще один нюанс. Каждая из 24 средних точек, которые являются эквивалентными перемещениями по модулю в решётке, может соответствовать любому из 6 различных физических мест внутри шестиугольника, поэтому всего необходимо 144 телохранителя.

Откуда такое резкое отличие квадратной и треугольной комнаты? Если замостить плоскость правильными шестиугольниками, в каждом углу домена сойдутся три шестиугольника. Это нечётное число, в отличие от четырёх, которые встречаются в каждом углу квадратной мозаики, или шести в треугольной мозаике. Если внимательно проследить за отражениями вокруг каждого угла, то нечётное количество отражений показывает, что виртуальное изображение исходного объекта не накладывается на его исходное положение.

Всего в одном изображении комнаты может быть до шести отражений объекта. Конечно, ни одна последовательность отражений не может заставить комнату, содержащую только один объект, оказаться содержащей шесть копий этого объекта. Но одну и ту же виртуальную комнату на плиточной плоскости можно увидеть несколькими путями: разными последовательностями отражений, которые в конечном итоге по-разному отражают комнату. Таким образом, вместо уникального способа идентификации любого шестиугольника с любым другим, есть шесть различных вариантов, зависящих от конкретной последовательности задействованных отражений. А поскольку «убийца» может воспользоваться любым из них, количество требуемых «телохранителей» умножается ещё на шесть.

Обратите внимание, что анимация ниже показывает полный, идеализированный набор точек, независимо от того, будут ли они на самом деле видны кому-либо. Истинный набор изображений, который наблюдатель сможет увидеть в любой момент, будет неким подмножеством этого.

В конце статьи вернёмся к профессору Марьям Мирзахани. Уникальная женщина, с уникальной историей и жизнью. Блестящий учёный и очень интересный человек. Про вручение Филдсовской премии на Хабре имеется статья. В июле 2017 года в возрасте сорока лет профессор умерла от последствий рака груди.

Requiescat in pace.

НЛО прилетело и оставило здесь промокод для читателей нашего блога:
— 15% на заказ любого VDS (кроме тарифа Прогрев) — HABRFIRSTVDS.