Читаем Энциклопедический словарь юного математика полностью

Энциклопедический словарь юного математика

В 1970-1980 гг. комбинаторика добилась новых успехов. В частности, с помощью ЭВМ решена проблема четырех красок: доказано, что любую карту можно раскрасить в четыре цвета так, чтобы никакие две страны, имеющие общую границу, не были окрашены в один и тот же цвет.

ВЕНГЕРСКИЙ ШАРНИРНЫЙ КУБИК

Необыкновенно популярной головоломкой стал кубик Рубика (рис. 1), изобретенный в 1975 г. преподавателем архитектуры из Будапешта Эрне Рубиком для развития пространственного воображения у студентов. Кубик Рубика – это куб, как бы разрезанный на 27 одинаковых кубичков. В исходном положении каждая грань куба окрашена в один из 6 цветов. Остроумный механизм позволяет поворачивать любой слой из 9 кубичков, примыкающих к одной грани куба, вокруг ее центра (на рис. 1 слегка повернут верхний слой); при этом цвета граней смешиваются. Задача состоит в том, чтобы вернуть разноцветные грани кубика в исходное положение.

Рис. 1

Приведем один из многочисленных алгоритмов решения этой задачи. Он включает два этапа: на первом собираются кубички, располагающиеся в серединах ребер куба (реберные), на втором – угловые. Каждый кубичек может находиться на одном и том же месте в нескольких положениях (реберный – в двух, угловой – в трех). В соответствии с этим каждый этап делится на два шага: на первом кубички только расставляются на нужные места, а на втором они, если это необходимо, разворачиваются на своих местах так, чтобы их цвета совпали с «правильными» цветами граней. Ориентирами при определении правильных положений реберных и угловых кубичков служат квадраты в центрах граней: их взаимное расположение не меняется при вращении граней, а их цвета задают будущие цвета граней куба.

Записывать последовательности ходов (операции) будем, пользуясь обозначениями рис. 1; например, ΦΠ' – это последовательность из двух поворотов: фасадной (передней) грани на 90° по часовой стрелке и правой – на 90° против часовой стрелки. Весь процесс сборки основан на операции F = ПВФВ'Ф'П'Ф и обратной к ней операции F = Ф'ПФВФ'В'П'.

1-й этап. Сборка реберных кубичков.

1. Для расстановки реберных кубичков применяется операция F (или F'), меняющая местами ровно два из них. (Действие операции на реберных кубичках показано на рис. 2.)

Рис. 2

2. Для разворачивания применяется операция F² = F·F; в результате на своих местах поворачиваются два кубичка (a и b на рис. 2).

2-й этап. Сборка угловых кубичков.

1. Для расстановки угловых кубичков применяется операция FB'F'B, действие которой показано стрелками на рис. 3, и обратная операция @, переставляющая те же кубички в обратном порядке.

Рис. 3

2. Для разворачивания угловых кубичков применяется операция F⁴, действие которой показано на рис. 4, и обратная к ней операция (F')⁴, поворачивающая те же три кубичка в противоположном направлении.

Рис. 4

Указанные операции можно использовать и в рамках других общих схем. Например, нетрудно правильно собрать все реберные кубички, кроме четырех, лежащих в одной грани, после чего можно перейти к выполнению первого этапа алгоритма. Общее число ходов при этом заметно сокращается, но остается все еще большим. Дальнейшее сокращение можно получить, в частности, за счет расширения набора стандартных операций. Имеются и принципиально другие схемы сборки. Лучшие из них позволяют обойтись примерно 50 ходами-поворотами, но теоретически из любого состояния кубика можно вернуться в исходное не более чем за 23 хода. Лучшее время, показанное на чемпионате мира 1982 г. по скоростной сборке кубика Рубика, составило всего 22,95 с.

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

КОМПЛЕКСНЫЕ ЧИСЛА

Так называют числа вида a + bi, где a и b - действительные числа, а i - число особого рода, квадрат которого равен -1, т.е. i² = -1. Действия над комплексными числами выполняются по таким же правилам, что и над многочленами, при этом i² заменяют на -1. Например: