Рис. 1 Часы Рубика
В прошлом году мы познакомили читателей «Кванта» с «часами Рубика» (см. 4-ю с. обложки 4-го номера). Хотя эта головоломка была запатентована знаменитым изобретателем в 1988 году, она все еще малоизвестна у нас (да, пожалуй, такой и останется). Тем не менее, мы получили письма с просьбами выполнить данное почти года назад обещание и рассказать о «часах» подробнее. Надеемся, что наш рассказ будет интересен всем любителям головоломок, а не только немногочисленным обладателям «часов Рубика». Тем более, что эта головоломка и устроена, и решается проще, чем, скажем, «волшебный кубик», и поэтому, уяснив себе, как «часы» работают, вы можете попробовать придумать алгоритм «на кончике пера».
Рисунок 1 показывает, как выглядят «часы Рубика» снаружи: с двух сторон круглого корпуса расположены по 9 окошек с вращающимися кружками-циферблатами, на которых нарисованы стрелки. Сбоку корпуса выступают 4 шестеренки, вращая которые, стрелки можно переводить. Скрытый зубчатый механизм — «коробка передач» — позволяет подключать к вращению разные наборы циферблатов. Управляется «коробка передач» кнопками; на каждой стороне корпуса их по 4, но фактически это 4 стержня, выступающие с обеих сторон: если нажать на стержень с лицевой стороны, он выскочит с тыльной, и наоборот. Задача ставится так же, как для «кубика» и множества других подобных головоломок — «запутав» показания часов, надо вернуть их все в «правильное» состояние, а именно, поставить на 12 часов.
Прежде чем решать эту задачу, надо, конечно, разобраться, как «часы» управляются, какие стрелки подключаются к вращаемой шестеренке при том или ином варианте нажатия кнопок («передаче»). Тот, у кого головоломка есть, должен просто перепробовать все варианты. А остальным мы предлагаем сразу заглянуть внутрь «часов». На рисунке 2 вы видите, что на ведущих (угловых) шестеренках, выступающих из корпуса, укреплены по 2 циферблата — с тыльной и лицевой стороны; такие парные циферблаты всегда вращаются синхронно. Эта шестеренка сцеплена с шестеренкой на ближайшей кнопке, а она, в свою очередь, сцеплена либо с шестеренками трех соседних тыльных циферблатов (центрального и двух боковых), если кнопка нажата, либо с тремя соответствующими циферблатами лицевой стороны, если кнопка отжата. С этих шестеренок в зависимости от «передачи» вращение может распространяться еще дальше. Очевидно, сцепленные между собой циферблаты могут вращаться только одновременно, в одну сторону и с одной и той же скоростью. Можно сказать, что «часы Рубика» имеют 14 «степеней свободы», отвечающих 4 парам угловых циферблатов и еще 10 одиночным циферблатам, каждый из которых в принципе может быть повернут независимо от остальных. Следовательно, число различных расположений стрелок не превосходит 12^4, что примерно равно 1,28*10^15. В дальнейшем мы увидим, что все эти расположения действительно можно получить.
Рис. 2 "Часы Рубика" в разрезе (плоскостью, проходящей через оси бокового и центрального циферблатов): а) пара угловых циферблатов, укреплённых на ведущей шестерёнке, б) кнопка с шестерёнкой для переключения передач, в) лицевой цетральный циферблат, г) тыльный центральный циферблат, д) корпус головоломки.
А теперь посмотрим, какими возможностями при переводе стрелок мы располагаем. Каждая из кнопок может находиться в двух положениях, поэтому всего в головоломке имеется 2^4=16 «передач». При любом нажатии кнопок можно выделить две группы подключенных друг к другу циферблатов: в одну входят угловые пары и лицевые циферблаты, окружающие ненажатые кнопки, другая определяется так же, только если посмотреть на «часы» с тыльной стороны. Каждая пара угловых циферблатов обязательно попадет в одну из групп, но некоторые «одиночные» циферблаты могут оказаться несцепленными с другими. Таким образом, при заданном положении кнопок имеется, вообще говоря, два способа вращения стрелок— можно вращать любую из двух групп. Но в двух случаях — когда все кнопки нажаты или отжаты — образуется только одна группа, поэтому общее число способов вращения равно 2 • 16 — 2=30. Однако если считать эквивалентными те способы вращения, которые получаются друг из друга поворотом головоломки в ее плоскости или ее переворачиванием, то останутся всего 5 неэквивалентных вариантов. Все они показаны на рисунке 3. (Проверьте, что имеется 2 способа вращения, эквивалентные варианту A, по 8 способов, эквивалентные В, С и Е, и 4 способа, эквивалентные D.) 
Рис. 4 Пять принципиально различных передач "часов Рубика" (вид с лицевой стороны): жёлтым показаны ненажатые кнопки, чёрным - нажатые, зубцы выделены у вращаемой шестерёнки.
Если повернуть ведущее колесико на 360°/12=30°, то в зависимости от включенной «передачи» те или иные циферблаты (на рисунке 3 они помечены стрелками) повернуться на тот же угол, т. е. на 1 час. Такие операции будем называть элементарными; для «передач», показанных на рисунке 3, мы будем обозначать их, соответственно, А, В, С, D, Е. Результат операции можно записывать с помощью таблички из нулей и единиц:
и т. д.; здесь 1 означает поворот на 1 час, 0 — отсутствие поворота. (Таблички для А, В, С показывают лишь то, что происходит на лицевой стороне «часов», но этого достаточно, т. к. на тыльной стороне будут-вращаться только угловые циферблаты, повторяя вращение парных им лицевых.) Чтобы найти результат последовательного выполнения нескольких элементарных операций, надо просто сложить поэлементно соответствующие таблицы. Например,
Очевидно, что такое «сложение» операций коммутативно, т. е. не зависит от порядка слагаемых. И в этом — главная особенность «часов Рубика», которая делает их существенно проще «волшебного кубика» и родственных ему головоломок.
Результат любой «неэлементарной» операции полностью определяется числом повторений в ней каждой из 30 возможных элементарных операций (оно может быть и нулем), поэтому ее можно записать в виде суммы 30 слагаемых aA+bB+cC+dD+eE, где коэффициенты а, Ь, с…— это количество повторений А, В, С …. или углы (в часах), на которые поворачивается ведущая шестеренка при соответствующих положениях кнопок. Теперь дело сводится к чисто алгебраической задаче, точнее, просто к решению системы линейных уравнений.
Действительно, определим для каждого циферблата угол, на который его надо повернуть, чтобы поставить стрелку на 12 часов; получатся две таблички для лицевой и тыльной стороны.
Пусть, например, для лицевой стороны эта табличка выглядит так:
тогда соответствующие уравнения имеют вид
Всего здесь 9 уравнений с 30 неизвестными, но, добавляя еще 5 уравнений для неугловых циферблатов тыльной стороны, получим систему из 14 уравнений. Ее надо решить в целых числах, а точнее, «по модулю 12», т. е., считая числа, дающие одинаковый остаток при делении на 12, равными (ведь 12 час=0 час). Поскольку число неизвестных здесь больше числа уравнений, часть из них, вообще говоря, можно задать произвольно, а остальные уже найти из системы. Ясно, что оставить нужно 14 неизвестных — по числу уравнений, т. е. из всего многообразия 30 элементарных операций можно ограничиться только 14-ю. Но эти операции (или неизвестные в наших уравнениях) должны быть независимы, т. е. ни одна из них не должна выражаться через остальные — иначе мы не сможем получить все 12^14 состояний «часов Рубика»…
Прервем здесь наши алгебраические рассуждения. Принцип уже ясен, а такое чисто вычислительное, рутинное решение не требует ни воображения, ни соображения — качеств, без которых любая головоломка теряет всю привлекательность. Обратимся лучше снова к рисунку 3 и попробуем, глядя на него, найти такие комбинации элементарных операций, которые позволяли бы переводить стрелки наших часов по отдельности, или хотя бы небольшими группами. Это позволило бы найти прямой путь к решению.
Одна такая операция видна сразу — это
(знак «минус», конечно, означает, что стрелки поворачиваются в направлении, противоположном указанному на рис. 3). Операция t(A—В), где t=0, 1,…,11, поворачивает на t делений левую верхнюю пару угловых циферблатов. Аналогично можно поворачивать по отдельности и 3 другие угловые пары. Эти операции удобно использовать в конце решения, поскольку они не разрушат того, что уже достигнуто.
Теперь хотелось бы найти аналогичную операцию для боковых циферблатов. Причем она может поворачивать и угловые циферблаты, ведь мы их все равно будем устанавливать позже. Наверное, вы уже нашли ответ:
Эта операция переводит на 1 час вперед верхнюю стрелку на лицевой строке (и соседние с ней угловые). Понятно, что головоломку можно повернуть так, чтобы на «верхнем лицевом» месте оказался и любой из 7 других боковых циферблатов.
Итак, мы имеем 8 эквивалентных операций для установки боковых циферблатов и 4 — для угловых. Добавим к ним еще две операции для центральных циферблатов, например, А и аналогичную «тыльную» операцию. Получится 14 операций, которых достаточно для решения головоломки (вспомним систему из 14 уравнений!). Действовать можно так:
- операцией А (точнее, tA, где t=0, 1, …. 11) устанавливаем центральную стрелку лицевой стороны на 12 часов;
- операциями вида t(A—С) устанавливаем лицевые боковые стрелки (центральная останется при этом неподвижной);
- переворачиваем головоломку и повторяем первые два шага;
- операциями вида t(A—В) устанавливаем угловые стрелки.
Можно было бы на этом и закончить, но наш алгоритм допускает усовершенствование, точнее, его можно сократить. Если считать «ходом» поворот одной из шестеренок при фиксированной «передаче», то число ходов для 1-го шага равно 1, для 2-го — 2*4=8 (на каждый циферблат тратится 2 хода — tA и —tC), для 3-го — еще 1+8=9, для 4-го — 2*4=8, а всего — 26. Но ведь мы использовали только 14 разных элементарных операций (А, В, С и получающиеся из них поворотами головоломки), а значит, меняя их порядок, можно свести все к 14 ходам. Вот как это делается:
- операцией вида tC установим центральную лицевую стрелку параллельно верхней лицевой; поворачивая корпус на 90°, повторим эту процедуру еще 3 раза — в результате 5 стрелок (центральная и боковые) на лицевой стороне станут параллельными;
- операцией вида tA установим эти 5 стрелок на 12 часов;
- переворачиваем головоломку и повторяем 1-й шаг;
- операцией вида tC (на тыльной стороне!) устанавливаем все 5 неугловых стрелок параллельно левой верхней угловой и повторяем это еще 3 раза, поворачивая головоломку на 90° — в результате все 9 стрелок станут параллельными;
- операцией tA (опять-таки на перевернутой головоломке, т. е. на тыльной стороне) ставим все стрелки на 12 часов. Все.
Сделаем в заключение еще несколько замечаний. Ясно, что наш алгоритм позволяет получить любое из 12^14 возможных расположений стрелок. При этом мы используем 14 ходов, каждый из которых является повторением (в количестве от 0 до 11) одной из 14 элементарных операций А, В, С и им эквивалентных. С учетом коммутативности имеется всего 12^14 различных комбинаций этих операций. А это значит, что все они различны и каждому расположению стрелок отвечает только одна такая комбинация.
Итак, если ограничиться только выделенными нами 14-ю операциями, можно утверждать, что от любого расположения стрелок к любому другому можно перейти не более чем за 14 ходов, причем последовательность кодов определена однозначно (с точностью до порядка).
В этом — разительное отличие «часов Рубика» от его «волшебного кубика», для которого не только нет речи о какой-либо единственности решения, но и вопрос о кратчайшем алгоритме так и остается открытым (см. статью «Математика волшебного кубика» в «Кванте» № 8, 1982 г.). Более того, с математической точки зрения «часы» вообще можно считать тривиальной головоломкой, поскольку ее решение сводится к линейным уравнениям. Вот к каким последствиям приводит простенькое свойство коммутативности!
И все же и в этой головоломке остается вопрос, над которым можно подумать. Если пустить в ход все 30 элементарных операции, то однозначность решения, конечно, нарушится, а многие операции можно будет сократить. Верно ли, что и при таком расширенном арсенале ходов найдутся положения стрелок, до которых нельзя будет добраться быстрее, чем за 14 ходов? Ждем ваших ответов.
Статья взята из журнала «Квант».
