Шестиугольники на решетке

а) Начните с небольших n = 1, 2, 3, … Постарайтесь заметить закономерность в последовательности чисел, равных количеству шестиугольников в каждом случае.
б) Рассмотрите частный случай: выясните, сколько шестиугольников определяют точки, расположенные на периметре правильного шестиугольника со стороной m, и, учитывая результат пункта а), найдите общее число всех шестиугольников.

а) Итак, рассмотрим правильный шестиугольник H со стороной n, нарисованный на треугольной сетке. Посчитаем, сколько в нем содержится правильных шестиугольников со сторонами, параллельными сторонам H.

Ясно, что шестиугольник со стороной n всего один — он совпадает с H. Шестиугольников со стороной \(n-1\) уже 7 штук: у одного центр совпадает с центром H, а остальные получаются из него сдвигами к каждой из вершин H. Если продолжить уменьшать размер шестиугольника, то после аккуратного разбора случаев можно получить, что со стороной \(n-2\) будет 19 шестиугольников, а со стороной \(n-3\) — уже 37. Как возникают эти числа и что их объединяет?

Зафиксируем натуральное \(k<n\) и посмотрим, какие положения может занимать, например, левая нижняя вершина шестиугольника со стороной k. Несложно понять, что она может находиться только внутри шестиугольника со стороной \(n-k\), «приклеенного» к левой нижней вершине шестиугольника H (рис. 2).

Рис. 2.

Поскольку у каждого шестиугольника ровно одна левая нижняя вершина, то получается, что всего таких шестиугольников будет столько же, сколько узлов сетки попадает внутрь и на стороны шестиугольника со стороной \(n-k\).

Рис. 3.

Считать число точек внутри шестиугольника с данной стороной m можно разными способами. Мы последуем простому и изящному рассуждению, приведенному Мартином Гарднером в книге «Путешествие во времени». На рис. 3 все точки разбиты на четыре группы: те, что находятся в трех параллелограммах, плюс одна центральная точка. В одном параллелограмме \(m(m-1)\) точек, поэтому всего в шестиугольнике со стороной m будет \(p_m=3m(m-1)+1=3m^2-3m+1\) точек.

Нам, чтобы теперь решить задачу, нужно просуммировать эти выражения по всем m от 1 до n, то есть найти сумму \(P=\sum\limits_{m=1}^n p_m\). Удобнее всего это сделать, перегруппировав слагаемые так, чтобы отдельно сложить квадраты, отдельно — первые степени и отдельно — единицы:

Теперь осталось воспользоваться известными формулами для суммы чисел от 1 до n и для суммы их квадратов (см. задачу Суммы квадратов, суммы кубов...):

После упрощения получится, что это выражение равно \(n^3\).

б) Надо заметить, что все точки, расположенные на периметре правильного шестиугольника со стороной m (где \(m\in\mathbb{N}\), \(m\le n\)) определяют ровно m правильных шестиугольников (рис. 4). Верно и обратное: если на нашей сетке построен правильный шестиугольник, то его вершины обязательно будут лежать на сторонах другого шестиугольника, которые при этом параллельны сторонам H.

Рис. 4.

С учетом результатов пункта а) это означает, что надо найти сумму \(N=\sum\limits_{m=1}^{n}(p_{n-m+1}\cdot m)\). Или, в полном виде:

Упрощать это выражение можно по-разному. Вот один из путей. Сначала выделим в отдельное слагаемое сумму, которую мы уже нашли в пункте а):

Сумма в первых скобках равна, как мы знаем, \(n^3\), и с учетом множителя n получится \(n^4\).

Разберемся со второй суммой. Компактно она записывается в виде \(\sum\limits_{m=1}^{n} p_m\cdot (m-1)\). Но каждое слагаемое \( p_m\cdot (m-1)=(3m^2-3m+1)(m-1)=3m^3-6m^2+4m-1\) — это многочлен, а значит с этой суммой можно поступить так же, как мы делали в пункте а) — перегруппировать ее так, чтобы каждая степень складывалась отдельно:

Опять воспользуемся известными формулами для этих сумм и получим:

После упрощения останется следующее: \(\frac34n^4-\frac12n^3-\frac14n^2\).

Поэтому искомое число всех правильных шестиугольников равно:

Ненадолго отвлечемся от треугольных решеток и рассмотрим довольно естественно возникающий в контексте этой задачи вопрос: можно ли на обычной квадратной сетке (на построить правильный шестиугольник или треугольник так, чтобы все его вершины находились в узлах?

Оказывается, что нет. Краткое доказательство приводится ниже в скрытом виде, так что у вас остается возможность подумать самостоятельно над тем, почему это так.

Доказательство

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

Допустим, что такой треугольник ABC все-таки существует. Тогда его площадь обязательно выражается рациональным числом. Это сразу следует из формулы Пика (см. статью Г. Мерзона Площади многоугольников и тающий лёд), но есть и простое наглядное рассуждение, не привлекающее такую «тяжелую артиллерию». Дело в том, что треугольник ABC достраивается до прямоугольника AMNK (достаточно провести через его вершины вертикальные и горизонтальные линии сетки, см. рис), площадь которого, очевидно, целая. При этом добавляются три прямоугольных треугольника (или два, если одна из сторон треугольника ABC идет по линии сетки), площади S₁, S₂ и S₃ которых либо целые, либо полуцелые. Значит, и площадь треугольника ABC сама тоже либо целая, либо полуцелая — и в любом случае рациональная.

С другой стороны, площадь правильного треугольника выражается через его сторону AB по формуле \(AB^2\sqrt3/4\). Но по теореме Пифагора \(AB^2=AM^2+MB^2\) — целое число. Поскольку \(\sqrt3\) — число иррациональное, то и площадь получается иррациональной. Получаем противоречие: одно и то же число (площадь ABC) не может быть одновременно рациональным и иррациональным.

Можно рассуждать и несколько по-другому. А именно, следить можно не за площадями, а за углами треугольника. Точнее, за их тангенсами. С одной стороны, как хорошо известно, угол равностороннего треугольника равен 60°, а его тангенс — \(\sqrt3\). С другой стороны, аналогичным достроением до прямоугольника получим, что этот угол представляется как сумма (или разность — в зависимости от расположения треугольника ABC относительно линий сетки) двух углов, тангенсы которых рациональны. Из этого следует, что и этот угол должен быть рациональным (см. формулу тангенса суммы). Опять получается противоречие.

Рис. 5.

Вернемся к треугольной решетке. При внимательном ее рассмотрении обнаруживаются интересные свойства. Например, в каждом правильном шестиугольнике с вершинами в узлах решетки центр тоже является узлом. Кажется, что это очень простое наблюдение, но оно позволяет заметить большее. Оказывается, что число шестиугольников, имеющих центром некоторый узел, в точности равно значению выражения \(h(h+1)/2\), где h — расстояние от этого узла до ближайшей стороны исходного шестиугольника, а в качестве единицы измерения взята высота единичного треугольника сетки (рис. 5).

Это легко можно доказать, опираясь на факт, которым мы пользовались при решении пункта б): с центром в данном узле существует ровно h шестиугольников размера от 1 до h, стороны которых параллельны сторонам исходного шестиугольника H, а каждый из них «порождает», в соответствии с упомянутым фактом, число шестиугольников, равное его размеру. Значит, надо сложить числа от 1 до h, а это и даст выражение \(h(h+1)/2\). Числа такого вида называют треугольными.

Опираясь на эту находку, сделанную Сергеем Царановым, можно решить пункт б) еще одним способом. Для этого в каждом внутреннем узле решетки запишем число, равное количеству шестиугольников, имеющих центром данный узел (рис. 6, слева) — то есть соответствующее треугольное число T_k. Сумма всех записанных чисел будет равна числу всех правильных шестиугольников (будут посчитаны и те шестиугольники, стороны которых не лежат на линиях разбиения).

Рис. 6.

Но как сосчитать такую сумму? Можно так: все слагаемые разобьем на 6 одинаковых групп, заключенные в треугольные области, тогда искомая сумма равна увеличенной в 6 раз сумме всех чисел одной группы и плюс центральное число, не вошедшее ни в одну из групп (рис. 6, справа), которое равно T_n. Учитывая, что в группе по рядам записаны треугольные числа, получаем, что нужно посчитать сумму \(\sum\limits_{i=1}^{n-1}(T_i\cdot (n-i))\). Это делается аналогично тому, как подсчитывались суммы в решении — получится \(\frac{1}{24}(n-1)n(n+1)(n+2)\).

Значит, всего шестиугольников

Упрощая это выражение получим все тот же результат — \(\left(\frac{n(n+1)}{2}\right)^2\). Это, кстати, квадрат центрального треугольного числа.

Другой подход есть и к пункту а), причем он почти не требует вычислений. По аналогии с рис. 2 будем отмечать положения, которые может занимать центр шестиугольника (со сторонами, параллельными сторонам исходного шестиугольника), последовательно уменьшая его размер от n до 1 (рис. 7).

Рис. 7.

То есть для каждого размера мы имеем свое множество центров. Каждое из этих множеств можно представить себе по-другому: в виде трехгранного уголка, сложенного из единичных кубиков (рис. 8). Из таких уголков складывается кубик со стороной n. Это и дает ответ: n³ шестиугольников.

Рис. 8.

С обсуждаемой задачей связана и придуманная автором головоломка «Разрушенные шестиугольники»: из спичек сложен правильный шестиугольник, разбитый на треугольные ячейки (рис. 9); какое наименьшее количество спичек надо убрать из этой конструкции, чтобы в ней не осталось ни одного контура правильного шестиугольника?

Рис. 9.

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

Решение головоломки

Как мы уже знаем, в шестиугольнике со стороной 3 есть 27 правильных шестиугольников: 19 со стороной 1 спичка, 7 со стороной 2 спички и 1 со стороной 3 спички. Заметим, что шесть спичек — по одной при каждой вершине исходного шестиугольника — не входят ни в один из этих 27 шестиугольников, поэтому ни одну из этих спичек нет смысла убирать.

Остальные спички можно представить в объединения трех неперекрывающихся групп спичек. В первой группе 6 шестиугольников со стороной 1 спичка, во второй группе 7 таких шестиугольников, в третьей группе — еще 6 (см. рис.).

Чтобы разрушить эти 19 шестиугольников, надо разбить их на смежные пары и в каждой паре убрать общую спичку, то есть надо убрать 3 + 4 + 3 = 10 спичек. После чего останется только один центральный шестиугольник со стороной 2, для разрушения которого надо убрать еще одну спичку. Значит, всего требуется убрать 11 спичек — например так, как показано на следующем рисунке.

Эта головоломка основана на исходной задаче при n = 3. При n = 1 и n = 2 она решается совсем просто, а вот уже при n = 4 возникают сложности и без компьютерного перебора справиться не получается. Возможно, у кого-то из читателей получится это сделать...