Перевёртыши

54

Перевертыш

Кандидат физико-математических наук
В. Н. ДУБРОВСКИЙ

Раскрывать секрет решения головоломки — занятие столь же нечесное, как сообщать заядлому болельщику счеточного футбольного матча перед его телевизionной трансляцией на другой день. Поэтому в нашем раскраске о двух головоломках—«перевертышах», знакомых читателю по обложкам 1-го и 2-го номеров «Кванта» за этот год, вопросов будет больше, чем ответов. Но прежде чем задавать вопросы и ответать на них, напомним, как эти головоломки устроены.

В одной головоломке 8 одинаково раскрашенных в шесть цветов кубиков размером 1×1×1 стоит выполню друг к другу в квадратной коробке размером 3×3 (рис. 1). В другой головоломке вместе кубиков берутся 23 одинаковых парамидики (правильных тетради) с раскрашенными в четыре цвета вершинами (рис. 2,a), которые размещаются в коробке, имеющей форму правильного шестиугольника со сторонай, в два раза большей ребра парамидики (рис. 2,б). В обих головоломках одно место пустует — «дырка», что позволяет переставлять элементы (кубики и парамидики), перекатывая их через ребро. Задачи, которые мы будем обсуждать, звучат для двух головоломок по-разному. Paramaidiки надо научиться переводить в «правильное», или «начальное», положение, показанное на рисунке 2,б, после того, как оно было разрушено произвольными перекатыванием. У кубиков много правильных положений (что это такое — ясно из рисунка 1; проверьте, что имеется 24 правильных положения); требуется одно из них превращать в другое. Но обе эти задачи — частные случаи обшей для всех «перестановочных» головоломок задачи: для любых двух размешений элементов выяснить, переводится ли одно в другое, а если да, то каким образом.

Кубики

Попробуем придумать операции, которые бы поворачивать кубик, оставляя его на месте,— тогда можно будет повернуть все кубики поочередно. Поставим в коробку только один кубик и прокатим его по квадрату 2×2 векруг одной из вершин основания A (рис. 3). Когда он вернется на место, мы увидим, что он повернулся относительно исходного положения на 120° около диагонали, выходящей из вершины A. Точно так же можно катать по квадрату 3 кубика — целочкой: после четырех ходов дырка вернется на место, а кубики циклические переставятся (рис. 4) — эту операцию, когда перестановка происходит против часовой стрелки векруг точки A, обозначаем C_A. Ясно, что операция C^3_A (троекратно повторенная C_A) возвращает все 3 кубика на исходные места, причем каждый из них поворачивается на 120° векруг своей диагонали, выходящей из A (см. рис. 4). Чтобы повернуть эти кубики в обратном направлении, нужно выполнить обратную операцию C^-3_A =

55

$$= \left( C_A^{-1} \right)^3,$$
где $C_A^{-1}$ — обход дырки воокруг точки $A$ по часовой стрелке.

Итак, мы можем поворачивать кубики на своих местах, но пока только группами по 3. Теперъ уже нетрудно придумать и операции, которые бы поворачивать только один кубик. Для них хватает поля размером $3 \times 2$ клетки. Пусть свободная клетка расположена вверху (рис. 5), она принадлежит двум квадратам $2 \times 2$ с центрами $A$ и $B$. Операция $C_A$ не затрагивает два правых кубика, а операция $C_B$ — два левых, поэтому операции $R_1 = C_A^3 C_B^3 C_A^{-3} C_B^{-3}, R_2 = C_A^{-3} C_B^3 \times C_A^3 C_B^{-3}$) и им подобные (см. задачу 1) заведено оставляют эти 4 крайних кубика неподвижными; пятый же кубик (назовем его «боковым»), как можно проверить, поворачивается в обихх случах на $180^\circ$: при $R_1$ — воокруг оси, параллельной $AB$, при $R_2$ — воокруг «горизонтальной» оси, перpendикулярной $AB$. Операция вида $[X, Y] = XYX^{-1}Y^{-1}$ называется коммутатором операций $X$ и $Y$. Коммутаторы оказываются очень полезными во всех головоломках с переставляющимся элементами; имеются, например, алгоритмы сборки кубика Рубика, целиком основные на коммутаторах (см. статью В. и С. Залгаллеров «Венгерский шарнирный кубик» в «Кванте» № 12 за 1980 год).

Задание

1. Рассмотрите всевозможные коммутаторы операций $C_A^{\pm 3}, C_B^{\pm 3}$. Показите, что все они действуют как $R_1$ или $R_2$ или как $R_1 R_2$ (поворот кубика на $180^\circ$ воокруг вертикальной оси).

2. Показите, что существует 24 способа поставить кубик на заданную клетку; из них только 12 можно получить из исходного положения перекатываниями по замкнутым маршрутом, а из этих 12 только 4 получаются

*) Порядок выполнения операций — слева направо; например, для $R_1 = C_A^3 C_B^3 C_A^{-3} C_B^{-3}$ сначала выполняется операция $C_A^3$, затем $C_B^3, C_A^{-3}$, и наконец, $C_B^{-3}$.

Рис. 3.

Рис. 4. Синце стрелки показывают перемещение кубков при операции $C_A$, красные — вращение кубков при операции $C_A^3$.

Рис. 5.

при действии коммутаторов $[X, Y]$, где $X$ и $Y$ — произвольные операции, возвращающие кубик на исходное место. Придумайте кратчайшую цепочку ходов, при выполнении коммутатором операций $X$ и $Y$. Коммутаторы оказываются очень полезными во всех головоломках с переставляющимся элементами; имеются, например, алгоритмы сборки кубика Рубика, целиком основные на коммутаторах (см. статью В. и С. Залгаллеров «Венгерский шарнирный кубик» в «Кванте» № 12 за 1980 год).

Итак, мы научились поворачивать 4 «боковых» кубика. Чтобы повернуть угловой кубик, достаточно поставить его на место бокового, применить операцию $R_1$ или $R_2$, а потом вернуть назад: например (см. рис. 5), операция $R_2' = C_A R_2 C_A^{-1} = C_A^{-2} C_B^3 C_A^{-3} C_B^{-3} C_A^{-1}$ поворачивает левый нижний кубик на $180^\circ$ воокруг «горизонтальной» оси, перепределикулярной $AB$ (аналогичную операцию для правого нижнего кубика составьте самостояльно).

Теперъ мы уменьшаем все кубики, но, наверное, не самым коротким способом (число ходов у нас равно 8·48=384): ведь каждый кубик поворачивается отдельно и к тому же остается на месте, что не обязательно*).

*) Для случая, когда пустое место не в центре, а слева внизу, А. В. ХодULEВ-придумал решение в 100 ходов, причем кубики поворачиваются здесь не на $180^\circ$, а на $90^\circ$: $JH^2 \Pi B^2 \Pi H(\Pi B J H)^3 H J B^2 \Pi H(J B J H)^2 H J B J H^2 B^2 J^2 H^2 J B J H^2 H J B J H^2 J^2 H J B J H^2 J^2 H J B J H^2 J^2 H J B J H^2 J^2 H J B J H^2 J^2 H J B J H^2 J^2 H J B J H^2 J^2 H J B J H^2 J^2 H J B J H^2 J^2 H J B J H^2$.

*) Для случая, когда пустое место не в центре, а слева внизу, А. В. ХодULEВ-придумал решение в 100 ходов, причем кубики поворачиваются здесь не на $180^\circ$, а на $90^\circ$: $JH^2 \Pi B^2 \Pi H(\Pi B J H)^3 H J B^2 \Pi H(J B J H)^2 H J B J H^2 B^2 J^2 H^2 J B J H^2 J^2 H J B J H^2 J^2 H J B J H^2 J^2 H J B J H^2 J^2 H J B J H^2 J^2 H J B J H^2 J^2 H J B J H^2 J^2 H J B J H^2 J^2 H J B J H^2 J^2 H J B J H^2$.

Рис. 5.

57

Ян ГевелиЙ

(Начало см. на с. 53)

астроомичесмии инструктами. Пожар уничтожил также все его иммущество. Но он мужственно перенес это несчастье и при первой же возмездности возобновил свои исследования.

Сегодня мы знаем о Луне намного больше, чем во времена Гевелия. Сфотографирован и детально изучен рельеф ее обратной стороны. Космические аппараты исследовали ее поверхность и принесли нам образцы лучного грунта. На Луне pobывали и первыше астронавты.

На второй странице обложки воспроизведен фрагмент карты Луны, на котором изображен участок обратной стороны, прилегающий к Морю Москвы (диаметр этого моря составляет 460 км). Она впервые было обнаружено на фотографиях, полученных советской автоматической международной станцией «Луна-3» в 1959 году. В 1961 году Международный астрономичесный союз утвердил восемнадцать наименованный объектов обратной стороны Луны, и средних — Море Москвы. Поднее к ним было добавлено еще более патискот наименованный деталей лунного рельфа обратной стороны Луны. Международный астрономичесный союз утвердил наименованный объектов обратной стороны Луны. Международный астрономичесный союз утвердил наименованный объектов обратной стороны Луны, и техническая деталей науки и техники — Ломоносова, Циолковского, Королева, Лебедева, Мандельштама, Курчатова, Арцимовича, Пастера, Кюри, Ферми и многохругиx. В лучну номенклатуру вошли также имена погибших космонавтов — Комарова, Волкова, Добровольского, Пацаева, Гриссома, Уайта, Чаффи. Вокрестности Моря Москвы расположены кратеры, называющие именами советских космонавтов Титова, Николаева, Терешковой, Беляева, Леонарова, Шаталова, Феоктистова. Они хорошо видны на фрагменте лунной карты, изображеном на второй полoce обложки. В районе бассейна Аполлон и Моря Спокойстия шесть кратеров носят имена американских астронавтов — участников лунных экспедиций. Это кратеры Армстронг, Олдин, Коллинз, Андерс, Борман и Ловелл.

Ж. Ф. Родионова, В. А. Лешковцев