Ожерелье из кубиков

Проследите за ниткой, на которую нанизаны кубики. Какую форму принимает эта нитка, когда кубики упаковываются в кубическую коробку? Полезно обратить внимание на порядок чередования вершин кубиков ожерелья.

а) В ожерелье из 27 кубиков выберем какой-нибудь один кубик и отметим его номером 1. Занумеруем остальные кубики по порядку, двигаясь вдоль нити в одном из двух возможных направлений. В кубике с номером n обозначим через A_n ту из лежащих на нити вершин, которая примыкает к предыдущему кубику.

Введем систему координат (это не обязательно, но так удобнее): начало поместим в одну из вершин коробки, а оси направим вдоль ее ребер. В качестве единицы возьмем длину ребра кубика. Если ожерелье упаковано в коробку, то лежащие на нити вершины каждого кубика имеют различные по четности абсциссы. Значит, сумма этих двух абсцисс для каждого кубика — нечетное число. Следовательно, сумма всех абсцисс по всем 27 кубикам — также нечетное число. Но каждая абсцисса повторяется в этой сумме дважды: каждая вершина A_n принадлежит двум кубикам. Значит, указанная сумма четна. Получаем противоречие, а значит, упаковать ожерелье из 27 кубиков в кубическую коробку 3×3×3 невозможно.

Рис. 2.

б) Покажем, что ожерелье из 64 кубиков можно упаковать в кубическую коробку 4×4×4. Для этого рассмотрим куб 2×2×2, составленный из восьми единичных кубиков и отметим в каждом из них по одной диагонали так, как показано на рис. 2. Полученный при этом граф из отмеченных диагоналей содержит шесть вершин. Заметим, что у всех них четная степень, то есть в каждой вершине сходится четное число ребер графа. Очевидно, из восьми кубов 2×2×2 с так же проведенными диагоналями можно составить куб 4×4×4. Объединение всех 64 отмеченных диагоналей этих блоков представляет собой граф, все вершины которого четны.

Но как доказал Леонард Эйлер еще в XVIII веке, в связном графе, не имеющем вершин нечетной степени, есть эйлеров цикл — замкнутый обход ребер, в ходе которого каждое ребро посещается ровно один раз. Это и означает, что ожерелье упакуется в коробку 4×4×4: его нитка должна просто проходить по ребрам эйлерова цикла.

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

Рассмотренные способы решения задачи в пунктах а) и б) позволяют решить задачу и в общем случае — для произвольных кубов — и сделать вывод, что ожерелье из n³ единичных кубиков при нечетным n нельзя упаковать в кубическую коробку n×n×n, а при четном n — можно.

Участникам олимпиады задача очень понравилась, они придумали много оригинальных решений. Вот некоторые из них.

Красивое доказательство невозможности упаковки ожерелья для нечетного n предложил будущий победитель трех международных олимпиад Владимир Дрёмов. Если ожерелье упаковано в кубе n×n×n, то все вершины кубиков находятся в нескольких параллельных плоскостях. Покрасим попеременно белым и черным цветом эти плоскости и вершины кубиков, в них попавшие. Тогда концы каждой большой диагонали каждого кубика имеют разные цвета, поэтому в замкнутом ожерелье белые и черные вершины, лежащие на нити, должны чередоваться. Но это невозможно, так как на нити ожерелья находится n вершин — нечетное число.

Запомнилось еще одно решение — векторное. Снова доказываем, что при нечетном n ожерелье из кубиков нельзя упаковать. Предположим противное: пусть ожерелье упаковано в форме куба n×n×n. Тогда нить ожерелья примет форму пространственного n³-угольника. Сторонами этого многоугольника являются диагонали n³ кубиков. Если его стороны рассматривать как векторы, стрелки которых расставлены по правилу многоугольника, то сумма этих векторов равна \(\vec0\). Но тогда равна нулю и сумма проекций этих векторов на любую прямую. С другой стороны, ясно, что проекция каждого из этих векторов на прямую, содержащую ребро куба n×n×n, равна 1 или −1. Но сумма нечетного количества таких чисел не может равняться нулю. Противоречие.

Ежегодно в МГУ проводится Математический праздник: самая массовая олимпиада по математике для учеников 6–7 классов — в ней участвует тысячи школьников. После олимпиадной части — решения задач — организаторы проводят для участников много интересных мероприятий. В этом году Математический праздник состоится 9 февраля, регистрация еще открыта. Одновременно с основной — московской — площадкой олимпиаду планируют провести еще в нескольких городах. Следите за информацией на сайте Математического праздника.

Одно из них было связано с головоломками, его предложили провести мне. Я привез с собой чемодан головоломок из моей коллекции, среди которых был и игровой вариант нашей задачи — головоломка «Ожерелье из 27 кубиков» (рис. 3). На его нити есть застежка, поэтому собирать куб 3×3×3 можно пытаться в двух вариантах: либо из разомкнутой цепочки кубиков, либо из ожерелья. В обоих вариантах ставилась одна цель — уложить кубики в форме куба 3×3×3.

Рис. 3.

На первый взгляд (особенно для тех, кто не решал задачу) это очень легкая головоломка, но, повозившись с ней некоторое время, начинаешь понимать, что это «крепкий орешек». Более того, со временем приходишь к мысли, что сложить куб 3×3×3 невозможно. Как мы доказали выше, в «замкнутом» варианте головоломка и не имеет конструктивного решения. Нужно иногда предлагать и такие «жизненные» головоломки, чтобы решающий после нескольких неудачных попыток выполнить задание остановился и задумался, можно ли его вообще выполнить, — в жизни ведь далеко не все задачи имеют решение.

При желании, ожерелье можно использовать и по прямому назначению — как украшение. На рис. 4 показан вариант из 64 дубовых кубиков. Как мы знаем, его можно хранить в компактной коробке.

Рис. 4.

Можно рассмотреть и вариант задачи для n = 2. В таком случае используется всего 8 кубиков, поэтому ожерелье логичнее называть браслетом. На рис. 5 показан такой браслет из игральных кубиков. Напомним, что на стандартном игральном кубике точки расставлены так, что суммы чисел на противоположных гранях равны одному и тому же числу 7. То есть пары чисел на противоположных гранях такие: 1 и 6, 2 и 5, 3 и 4. Во всех кубиках нить соединяет вершину, в которой сходятся грани с числами 1, 2 и 3, с вершиной, в которой сходятся грани с числами 4, 5 и 6.

Рис. 5.

С этим браслетом связаны следующие задания.

Первое — совсем простое: сложить из такого браслета куб 2×2×2. Это не должно вызвать особых трудностей — куб складывается почти сам.

Второе задание посложнее: собрать куб так, что сумма четырех чисел на каждой его грани была равна 14.