Это перевод статьи Дэвида Плаксо, моего товарища по увлечению математикой кубика Рубика, преподавателя департамента математики Университета Джорджии (UGA). Дэвид задался необычным вопросом: можно ли взять математический узел, превратить его в пиксельную проекцию и собрать ее на поверхности кубика Рубика или биг-куба — например, кубика 9×9×9? Причём сделать это таким образом, чтобы результат был не просто корректным с точки зрения топологии узлов, но ещё и визуально привлекательным, то есть «фотогеничным» (photogenic) — именно такой термин предлагает использовать Дэвид.
В итоге получилась увлекательная смесь математики, теории узлов, пиксель-арта и механики кубика Рубика — статья под названием «Photogenic Knot Projections on n×n×n Rubik’s Cubes» («Фотогеничные проекции узлов на кубиках Рубика n×n×n»), которую Дэвид представил на ежегодной конференции по математике и искусству Bridges в 2022 году.
Оригинал публикации: David Plaxco Photogenic Knot Projections on n×n×n Rubik’s Cubes // Proceedings of Bridges 2022: Mathematics, Art, Music, Architecture, Culture. Phoenix, Arizona: Tessellations Publishing, 2022, pp. 331–334.
Аннотация
В этой статье я описываю наборов критериев для категоризации пиксельных проекций узлов и использую эти критерии для определения фотогеничных проекций узлов. Я объясняю, как эти проекции могут быть созданы на кубе Рубика размером n×n×n, и выделяю три характеристики фотогеничных проекций узлов — количество цветов (c), количество используемых граней (f) и количество слоев на кубе (l). Наконец, я обсуждаю минимизацию некоторых узлов по параметрам c, f и l.
Фотогеничные узлы и их пиксельные проекции
Теория узлов — это один из тех разделов математики, где способ представления объекта почти так же важен, как и сам объект. Когда мы меняем форму записи или визуализации, мы часто начинаем видеть то, что раньше было скрыто. Именно так произошло и с узлами: их дискретизация (то есть перевод в пиксельный вид) открыла доступ к важным характеристикам — числу перекрёстков, детерминантам, полиномам и многому другому [1].
В этой статья речь пойдёт о преобразовании рисунков узлов в пиксельные проекции, и наборе критериев, которые позволяют получать так называемые фотогеничные отображения этих проекций.
Сама идея пикселизации довольно проста. Берём обычную диаграмму узла и накладываем на неё квадратную сетку. Затем каждому квадрату (пикселю) назначаем цвет так, чтобы итоговая картинка максимально напоминала исходную проекцию узла. Это можно делать автоматически, с помощью алгоритмов, или вручную — по сути, «перерисовывая» узел в стиле 8-битной графики, как показано на рисунке 1.
Такой подход даёт удобный способ получить дискретную версию узла — форму, с которой уже можно работать как с набором элементов, а не как с непрерывной кривой.
Однако при грубой пикселизации узлов довольно быстро возникает проблема: чтобы аккуратно разделить разные участки нити, показать повороты и особенно корректно отобразить пересечения (где одна нить проходит над другой), требуется очень много пикселей. Между сегментами приходится оставлять зазоры, а на перекрёстках — специальные «окошки», чтобы было понятно, какая нить сверху.
Один из способов сократить количество пикселей — использовать разные цвета для разных сегментов. Тогда можно отказаться от некоторых пустых промежутков: цвет сам будет подсказывать, где одна нить, а где другая.
Но если пойти дальше и попытаться «сжать» узел, постепенно убирая все пустоты между нитями, возникает другая проблема. Цвета начинают сливаться, переплетаться и образовывать визуальную кашу — в итоге узел становится трудно распознать даже для человека, который знает, что именно там изображено.
Именно поэтому я ввел понятие фотогеничных пиксельных проекций узлов. Это такие пиксельные изображения, которые не только корректно передают структуру узла, но и выглядят аккуратно, понятно и эстетично. Критерии здесь в первую очередь визуальные, а не строго математические, но на практике они приводят к проекциям, которые легко читать и которые не требуют чрезмерного количества пикселей.
За время экспериментов с пикселизацией узлов я сформулировал шесть критериев, которые практически всегда позволяют получить хороший результат. Если пиксельная диаграмма им соответствует, то проекцию можно считать «фотогеничной». На рисунке 2 показаны примеры и антипримеры для интуитивного понимания критериев:
Пиксели узла должны контрастировать с фоном, а цвет фона должен образовывать рамку хотя бы в один пиксель вокруг всего узла.
Сегменты узла должны состоять из прямых линий, которые поворачивают только под прямым углом.
Каждый сегмент должен быть одного цвета.
Сегменты одного цвета не должны перекрещиваться без разрыва, который показывает, какой сегмент проходит над, а какой — под другим.
Сегменты должны сохранять свой цвет, проходя «через» перекрёсток, то есть цвет нити не меняется в месте пересечения.
Параллельные нити и перекрёстки, близкие к прямым углам, должны быть разнесены, чтобы между ними оставался хотя бы один пиксель фона.
Фотогеничные узлы на кубике Рубика n×n×n
Шесть простых критериев задают баланс между компактностью и наглядностью, который делает пиксельный узел по-настоящему фотогеничным. Однако, возникает резонный вопрос: какое отношение эти критерии могут иметь к математике? Они выглядят скорее, как дизайнерские рекомендации, чем как аксиомы теории узлов.
И это справедливое замечание. Я больше года создаю такие узлы, но задумался об их формализации лишь недавно. Особенно сбивает с толку такой момент: если узел — это одна непрерывная нить, то как он может быть многоцветным? Ведь, согласно критериям 3 и 5, сегмент сохраняет свой цвет даже после перекрещивания.
Ответ появляется, как только мы переносим узлы с плоской картинки на трёхмерный объект — кубик Рубика размера n×n×n. Такой кубик можно рассматривать как шесть соединённых друг с другом пиксельных экранов размером n×n. Если взять собранный куб и начать вращать его элементы, мы можем «перемешивать пиксели» на экранах-гранях, создавая различные узоры. В частности — изображения узлов.
Здесь и проявляется ключевой эффект: если нить узла переходит с одной грани куба на другую, она неизбежно меняет цвет. Это не художественный приём, а следствие механики кубика: каждая грань имеет свой цвет, и элемент, который переехал на другую грань, автоматически меняет ее цветовую комбинацию. Поэтому одна и та же нить, физически непрерывная, может выглядеть как многоцветная в проекции на поверхности куба.
Чтобы понять, как это работает, полезно немного разобраться в устройстве самого кубика. С момента своего изобретения кубик Рубика стал почти идеальной «лабораторией» для экспериментов с теорией групп. Куберы используют алгоритмы — специальные последовательности вращений — чтобы переставлять и переориентировать отдельные элементы куба, изменяя его цветовые комбинации.
Большинство людей знают только классическую задачу «собрать кубик», когда каждая грань становится одноцветной. Но довольно рано энтузиасты начали использовать те же самые приёмы для создания узоров и картинок на гранях куба. Некоторые из первых книг о кубике Рубика были посвящены именно таким паттернам [2, 3].
Помимо классического кубика Рубика 3×3×3 появились кубики 4×4×4, 5×5×5 и больше— вплоть до 21×21×21. Для них разработаны обобщённые методы решения кубиков n×n×n [4, 5], которые позволяют не просто собирать куб, но и управлять расположением его элементов. Именно такие биг-кубы и становятся холстом для пиксельных узлов.
Чтобы понять, как на кубике Рубика могут появляться многоцветные узлы, нужно немного разобраться в его «внутренней анатомии». На любом кубике n×n×n есть три вида элементов: углы, рёбра, центры. Это те же элементы, что и на стандартном кубике 3×3×3, за исключением того, что куб n×n×n имеет несколько типов центральных и реберных элементов, различающихся по классу перестановок (рисунок 3).
На рисунке 3a показан один из таких классов. Любой из выделенных элементов можно за 3-цикла перестановок поменять местами с любым из другим из выделенных на трехмерной проекции куба (то же касается и 12 таких же элементов на обратной стороне куба). Этот классы перестановок определяют, какие элементы могут быть взаимозаменяемыми. Например, центральный элемент грани (обозначен как 0 на рисунке 3b) никогда не может оказаться ближе к краю — какие бы алгоритмы вы ни применяли. Аналогично, определённые рёберные элементы могут меняться только друг с другом, но не с соседними (рисунок 3c). Углы тоже живут в своём собственном мире, подчиняясь тем же ограничениям по чётности перестановок, аналогично углам на кубе Рубика 3×3×3.
И вот тут появляется ключевая особенность структуры кубика n×n×n, важная для узлов. Рёберные элементы имеют только два цвета — поскольку объединяют две грани. Если взять, например, ребро, где встречаются синяя и белая грань кубика 9×9×9, то оно будет состоять из семи двухцветных элементов – центрального и по три «крылышка» с каждой стороны, и все они уникальны для куба.
Когда такой элемент оказывается частью пиксельного узла, он выполняет роль переходника: именно здесь нить может сменить цвет (пример на рисунке 2.5). Поэтому, если проекция узла проходит через ребро кубика, она автоматически становится двухцветной в этой точке.
Именно так и строятся многоцветные фотогеничные узлы на кубе Рубика n×n×n. Нить идёт по одной грани, затем переходит через ребро на соседнюю — и цвет меняется, но геометрически узел остаётся непрерывным.
Например, на рисунке 4 показана фотогеничная проекция узла Конвея на кубе 11×11×11. Каждый раз, когда нить проходит через ребро, она меняет цвет, продолжаясь уже на другой грани. Это позволяет узлу занимать сразу несколько сторон куба и при этом выглядеть аккуратно: сегменты могут пересекаться без разрывов.
Глядя на эту проекцию узла Конвея на кубе 11×11×11, неизбежно возникают вопросы:
возможно ли разместить этот же узел на кубике меньшего размера?
возможно ли уложить проекцию узла двух гранях, а не на трёх?
возможно ли обойтись двумя цветами вместо трёх?
Именно эти вопросы привели меня к формальному описанию «фотогеничности» проекции узла на кубике n×n×n к параметрам c, f и l, о которых пойдёт речь далее.
c,f,l – фотогеничные проекции узлов
Размышления о узле Конвея указывают на три основные характеристики фотогеничных проекций узлов на кубах Рубика:
c — количество цветов, из которых состоит нить узла (не фон).
f — количество используемых граней.
l — количество слоев куба (в разговорной речи это «размер» куба).
Исходя из этого, можно сказать, что узел (или его проекция) является c,f,l–фотогеничной, если фотогеничная пиксельнная проекция узла может быть составлена из c цветов на f гранях куба с l слоями.
Например, на рисунке 5 показаны три разные c,f,l–фотогеничные проекции узла трилистника: 4,2,9; 6,3,5; и 2,3,9.
Размер кубика и его механика накладывают ограничения на то, какие узлы можно на нём изобразить. Если говорить в терминах пикселей, у маленького кубика просто не хватает «разрешения» для сложных узлов. Например, классический кубик 3×3×3 слишком груб, чтобы на нём изобразить узел с 11 перекрёстками — такой, как узел Конвея. Зато на кубике 11×11×11 это уже вполне возможно, и получается аккуратная фотогеничная проекция.
С другой стороны, ситуация даже для простых узлов может быть неожиданной. Как показано на рисунке 5, фотогеничную проекцию узла-трилистника на кубике 9×9×9 можно нарисовать всего двумя цветами. А вот на кубике 5×5×5, где его проекция всё ещё помещается, придется задействовать все шесть цветов кубика.
Заранее угадать, сколько цветов, граней и слоёв понадобится для конкретного узла, почти невозможно. Однако, экспериментируя с такими проекциями, я выработал набор приёмов, которые позволяют строить эти пиксельные узлы на кубике, а также постепенно уменьшать количество цветов, граней или размер куба, на котором узел ещё можно разместить.
В своей работе я сосредоточился на c,3,l–фотогеничных узлах на трех гранях с числом перекрёстков до 7, и нашёл их проекции на кубиках 9×9×9 и меньше с последующей минимизацией используемых цветов (рисунок 6). Трехмерная проекция позволяет с одной точки обзора видеть максимально возможные три грани кубика и добиваться визуального эффекта, когда цвета «лицевой» половины куба контрастируют с тремя цветами, которые находятся на обратной стороне.
Проекции на рисунке 6 дают верхние оценки того, насколько компактно каждый узел можно уместить в формате c,3,l: возможно, в будущем найдутся ещё более компактные варианты, но эти уже гарантированно работают.
В будущих работах я намерен поделиться более детальной информацией о процессах минимизации c и l для c,3,l–фотогеничной проекции конкретного узла. Это естественно приведёт к попыткам обобщения: определить для любого узла, какова может быть его оптимизированная c,3,l–фотогеничная проекция.
Например, можно показать, что 6,3,5- и 2,3,9–фотогеничные проекции узла трилистника на рисунке 5 являются оптимальными. То есть, 6,3,5–фотогеничная проекция — это наименьший куб, на котором трилистник может быть создан на трёх гранях, и после размещения на кубике для отображения нити узла необходимо использовать все 6 цветов.
Аналогично, для любого фотогеничного узла, где нити одного цвета не пересекаются, необходимо использовать два цвета нити. Таким образом, это будет 2,3,l–фотогеничная проекция трилистника, что невозможно на кубе с менее чем с 9 слоями.
Список литературы
C. C. Adams. The Knot Book. American Mathematical Society, 1994.
D. Singmaster. Notes on Rubik’s Magic Cube. Enslow Pub, 1981.
R. Schlafly. The Complete Cube Book. Regnery Gateway, 1982.
M. E. Larsen. “Rubik's Revenge: The Group Theoretical Solution.” The American Mathematical Monthly, vol. 92, no. 6, 1985, pp. 381–390.
J. Weed. “Sub-Optimal Multi-Phase Path Planning: A Method for Solving Rubik's Revenge.” arXiv preprint arXiv:1601.05744, 2016.
Дополнительно рекомендую посмотреть выступление Дэвида Плакско на конференции по занимательной математике Gathering 4 Gardner (G4G)