Змейка в шестиугольнике

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

На рис. 1 для примера показана змейка с семью звеньями.

Рис. 1.

На рис. 2 показаны шестиугольники со сторонами 1 и 2, в которых середины противоположных сторон соединены змейками (с двумя и тремя звеньями, соответственно). Но если взять шестиугольник со стороной 3, то, немного поэкспериментировав, можно убедиться, что в него змейку таким же образом уже не вместить. Да и со следующими несколькими целочисленными шестиугольниками ничего не выйдет. Что же делать?

Рис. 2.

Рассмотрим достаточно длинную змейку, вершины которой обозначены так, как на рис. 3. Проведем прямую через точку \(A_0\) и середины четных отрезков (красная на рис. 3). Рассмотрим произвольное нечетное \(k>1\) и обозначим через \(B\) точку пересечения этой прямой со звеном \(A_{k-1}A_k\) (на рис. 3 \(k=7\)). Тогда для треугольника \(A_0BA_k\) верно следующее: \(\angle A_0BA_k =\frac{2\pi}{3}\), \(BA_k=\frac{k+1}{2}\), \(A_0B=2\cdot\left(1+2+\ldots+\frac{k-1}{2}\right)=\frac{k^2-1}{4}\).

Рис. 3.

По теореме косинусов находим третью сторону этого треугольника: \(A_0A_k=\frac{k+1}{4}\sqrt{k^2+3}\). Если оказалось, что вершины \(A_0\) и \(A_k\) — середины противоположных сторон правильного шестиугольника, то мы получаем, что радиус его вписанной окружности (составляющий половину \(A_0A_k\)) равен \(r_k=\frac{k+1}{8}\sqrt{k^2+3}\). По известным формулам, связывающим длины разных важных отрезков в правильном шестиугольнике, находим, что тогда радиус его описанной окружности равен \(R_k=2r_k/\sqrt3=\frac{k+1}{4}\sqrt{\frac{k^2}{3}+1}\). Значит, и сторона шестиугольника равна этому выражению.

Для четных \(k\) ситуация аналогична. Если обозначить за \(C\) точку пересечения красной прямой со звеном \(A_{k-1}A_k\) (на рис. 3 \(k=6\) в этом случае), то в треугольнике \(A_0CA_k\) угол \(A_0CA_k\) тоже будет равен \(\frac{2\pi}3\). Прилегающие к нему стороны легко найти: \(CA_k=\frac{k}{2}\), \(A_0C=2\cdot\left(1+2+\ldots+\frac{k}{2}\right)-\frac{k}2=\frac{k^2}{4}\). Теорема косинусов дает \(A_0A_k=\frac{k}{4}\sqrt{(k+1)^2+3}\). И, повторяя рассуждение с радиусами вписанной и описанной окружностей шестиугольника, находим, что его сторона должна быть равна \(R_k=\frac{k}{4}\sqrt{\frac{(k+1)^2}{3}+1}\).

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

Рассмотрим случай нечетного \(k\): \(\frac{k^2}{3}+1=\left(\frac pq\right)^2\). Перепишем это равенство так: \(k^2+3=3p^2/q^2\). Числа \(p\) и \(q\) можно считать взаимно простыми (это значит, что дробь несократима). Если \(q>1\), то, поскольку слева стоит целое число, получим, что \(q\) делится на 3: \(q=3q_1\). Значит, \(k^2+3=p^2/3q_1^2\), но из этого равенства следует, что и \(p\) делится на 3. Но это противоречит взаимной простоте \(p\) и \(q\). Следовательно, \(q=1\), то есть подкоренное выражение на самом деле является целым числом. Аналогичные рассуждения работают и для случая четного \(k\).

Итак, для нечетного \(k\) мы получили, что выполняется равенство \(\frac{k^2}{3}+1=m^2\), где \(m\in\mathbb{Z}\), а для четного \(k\) — равенство \(\frac{(k+1)^2}{3}+1=m^2\).

Заметим, что в обоих случаях \(m\) — четное. Из этого следует, что если верно равенство из предыдущего абзаца (свое для четного и нечетного \(k\)), то сторона шестиугольника \(R_k\), равная либо \(\frac{k+1}4m\) (при нечетном \(k\)), либо \(\frac{k}{4}m\) (при четном), автоматически будет целой! Значит, осталось найти целые решения этих двух уравнений.

Рассмотрим первое из них:

Сразу ясно, что \(k\) делится на 3, то есть \(k=3k_1\). Тогда уравнение можно переписать так:

А теперь — так:

Легко видеть, что при четном \(k\) все сведется к этому же уравнению, только замена будет другой: \(k=3k_1-1\).

Это уравнение относится к так называемым уравнениям Пелля. Они уже встречались в наших задачах (см. задачу Отношения фигурных чисел) и хороши тем, что про них все известно (см., например, брошюру В. Бугаенко, посвященную этим замечательным уравнениям, а также серию статей В. Сендерова и А. Спивака в «Кванте» №№ 3, 4 и 6 за 2002 год). Для конкретно этого уравнения верно следующее утверждение: если пара чисел \((m;\,k_1)\) является решением, то решением будет и пара \((2m+3k_1;\,m+2k_1)\) (убедитесь в этом!). Одну пару легко угадать — это (1; 0). Она порождает следующие решения: (2; 1), (7; 4), (26; 15), (97; 56), (362; 209), ...

Нас интересуют только пары с четным \(m\), то есть (2; 1), (26; 15) и (362;209). Каждая из них дает по два значения \(k\) (по формулам замен, которыми мы пользовались выше) и, тем самым, по два шестиугольника: из пары \((m;\,k_1)=(2;\,1)\) получаем \(k=2\) и \(k=3\) (эти случаи изображены на рис. 2), из пары (26; 15) — \(k=44\) и \(k=45\), из пары (362; 209) — \(k=626\) и \(k=627\).

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

Возникает естественный вопрос: а сколько звеньев у змейки для седьмого или восьмого шестиугольников? И вообще, что в общем случае — для \(n\)-го по счету шестиугольника? Ответ на эти вопросы, в принципе, был получен в решении: установив связь между числом звеньев наших змеек и уравнением Пелля \(x^2-3y^2=1\), мы все свели к анализу решений этого уравнения. Как уже говорилось, теория уравнений Пелля хорошо разработана, и, более того, для уравнений с небольшими коэффициентами при \(y\) уже все посчитано: например, все значения \(y\), удовлетворяющие этому уравнению, составляют последовательность A001353 в Онлайн-энциклопедия целочисленных последовательностей (OEIS). Надо лишь брать нечетные элементы этой последовательности и получать из них пары подходящих значений \(k\).

Можно заметить, что числа в этой последовательности растут очень быстро. Например, для двадцатого по счету шестиугольника \(y=21\,252\,634\,831\). То есть у соответствующей змейки \(k=3y=63\,757\,904\,493\) звена. Почему так? Дело в том, что элементы этой последовательности растут экспоненциально. Чтобы это выявить, нужно заметить, что их можно задать линейным рекуррентным соотношением, а именно: \(y_n=4y_{n-1}-y_{n-2}\), \(y_0=0\), \(y_1=1\). Вывод этого соотношения оставим в качестве упражнения (обратите внимание на приведенные в решении формулы для генерации решений уравнения Пелля). А, как известно, общий член линейной рекуррентной последовательности можно выразить через корни ее характеристического многочлена (подробности описаны, например, здесь). В данном случае получаем \(y_n=\frac{\sqrt3}{6}((2+\sqrt3)^n-(2-\sqrt3)^n)\). Естественно, так же быстро растет и число звеньев змейки.

При решении нашей задачи можно было рассуждать и несколько иначе (но с тем же результатом). По определению змейки ее звенья могут иметь лишь два направления. Это значит, что если змейка «вписана» в шестиугольник требуемым образом, то можно параллельно их перенести так, чтобы получилась ломаная всего из двух звеньев с теми же концами. Одно из звеньев новой ломаной составлено из нечетных звеньев змейки, второе — из четных. Угол между звеньями новой ломаной также равен 60°. Достроим ее до треугольника, соединив концы отрезком, — этот отрезок соединяет середины противоположных сторон шестиугольника. Если сторона шестиугольника равна \(a\), то длина этого отрезка равна \(a\sqrt3\).

В результате получим треугольник с углом 60°, прилегающие к которому стороны известны: одна равна \(u=1+3+5+\ldots\), вторая — \(v=2+4+6+\ldots\). Пусть, для определенности, число звеньев змейки четно и равно \(2l\). Тогда \(u=1+3+\ldots+(2l-1)=l^2\), а \(v=2+4+\ldots+2l=l(l+1)\). Снова применим теорему косинусов, чтобы выразить третью сторону: \(3a^2=u^2+v^2-uv=l^2(l^2+l+1)\). Дальнейший анализ этого уравнения приводит к тому же самому уравнению Пелля, что получилось в нашем решении. Для змейки с нечетным числом звеньев все аналогично.