Кубик (Не)Рубика

Кубик Рубика – должно быть, самая популярная на сегодняшний день механическая головоломка. В конце концов, по скоростной сборке кубика проводятся даже Чемпионаты Мира. Однако статичная модель куба 3х3х3 в математических задачах не менее популярна – вспомните, например, задачи об упаковке: такой размер кубика идеален, чтобы найти решение можно было «в уме», и в то же время оно не было бы слишком простым.

Давайте проведем мысленный эксперимент. В стандартном Кубике Рубика 27 маленьких кубических блоков. Двумя тройками взаимно-перпендикулярных плоскостей можно разрезать большой куб так, чтобы отделить каждый маленький кубик от других – при этом перемещать уже «отрезанные» части не придется. Тем не менее, лень – двигатель прогресса, поэтому возникает логичный вопрос: можно ли обойтись меньшим числом разрезов, если отделенные ранее блоки разрешено перемещать произвольным удобным образом?

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

Графы – еще одна неожиданная область математики, в которой можно столкнуться с кубом 3х3х3. И в этот раз, как и для Кубика Рубика, нас будет интересовать исключительно то, что находится снаружи, а именно – 54 разноцветных квадрата на гранях. Собственно, задача ставится следующим образом: можно ли провести в каждом из этих квадратов по одной диагонали так, чтобы в итоге получился НЕ-самопересекающийся путь? Итак, наш следующий объект для исследований – трехмерный граф, в котором должно быть 54 ребра!

В каждом квадрате нужно провести только одну диагональ, поэтому пересекаться ребра графа могут только в вершинах разноцветных квадратов – чтобы путь был НЕ-самопересекающимся, граф должен содержать ровно 54 + 1 = 55 неповторяющихся вершин. Теперь рассмотрим Кубик Рубика. На каждой из шести граней в середине находятся 4 вершины квадратов. На каждом из 12 ребер куба расположено еще по 4 вершины, однако 8 из них мы посчитали трижды, так как они принадлежат сразу трем ребрам. Итого получим 6*4 + 12*4 – 8*(3-1) = 56 возможных вершин для нашего графа, всего одна из которых должна остаться незадействованной. Давайте обратим на нее более пристальное внимание. К одинокой вершине может прилегать либо три квадрата – в случае, если мы выбрали вершину большого куба, либо четыре – для любой другой. Для каждого из квадратов существует только два варианта диагонали, и один из них недопустим, так как выбранная вершина должна остаться «одинокой». Получается, что диагонали неизбежно замыкаются в цикл вокруг незадействованной вершины. К сожалению, построить такой НЕ-самопересекающийся путь нельзя.

Нередко в математических задачах, вопрос в которых начинается с «А можно ли?», привести единственный пример в качестве доказательства не получается. В таком случае хорошо работает метод доказательства от противного, который – присмотритесь! – использовался и для головоломок с Кубиком (Не)Рубика.