|
|
 |
Условие
N³ единичных кубиков просверлены по диагонали и плотно нанизаны на нить, после чего нить связана в кольцо (то есть вершина первого кубика соединена с вершиной последнего). При каких N такое ожерелье из кубиков можно упаковать в кубическую коробку с ребром длины N?
Решение
Выберем в ожерелье какой-нибудь кубик и отметим его номером 1. Затем занумеруем остальные кубики по порядку, двигаясь вдоль нити в одном из двух возможных направлений. В кубике с номером n обозначим через An ту принадлежащую нити вершину, которая примыкает к предыдущему кубику.
Выберем систему координат, совместив начало с вершиной коробки, направив оси вдоль её ребер и взяв в качестве единицы длины длину ребра кубика.
Если ожерелье упаковано в коробку, то принадлежащие нити вершины каждого кубика имеют различные по чётности абсциссы. Значит, сумма этих двух абсцисс для каждого кубика – нечётное число. Следовательно, в случае нечётного N сумма всех этих абсцисс по всем кубикам – также нечётное число.
Но каждая абсцисса повторяется дважды: каждая вершина An принадлежит двум кубикам. Значит, указанная сумма чётна. Таким образом, при нечётном N упаковать ожерелье в коробку невозможно.
При чётном N в каждом кубике проведём диагональ, связывающую вершину вида (ч, ч, н) (то есть вершину, у которой первые две координаты чётны, а третья – нечётна) с вершиной вида (н, н, ч). Рассмотрим граф, образовавшийся на вершинах такого вида. Нетрудно понять, что он связен. Кроме того, каждая вершина внутри куба соединена с восемью вершинами, на грани – с четырьмя, а на ребре – с двумя
вершинами. Следовательно, по известному критерию (см. решение задачи 30806), в этом графе существует цикл, проходящий по каждому ребру ровно один раз.
Уложив кубики в порядке обхода этого цикла так, что просверленная
диагональ каждого попадёт на соответствующее ребро, получим требуемую
укладку нашего ожерелья.
