Один в поле воин

Как это часто бывает в задачах, в которых требуется найти какой-то объект с максимальными (или минимальными) свойствами, найти его не очень сложно. В нашей задаче, особенно в пункте а), нарисовав несколько треугольников с единственным узлом внутри, можно прийти к правильному ответу. Но еще нужно доказать, что найденное — это именно то, что требовалось. Во второй подсказке будут даны ответы на оба поставленных в задаче вопроса.

В пункте а) ответ 9. Доказать, что это максимальное возможное число узлов на границе треугольника, можно используя несложную «школьную» геометрию (достаточно предположить, что хотя бы на одной из сторон треугольника оказалось «много» узлов, и вывести из этого, что внутри него обязательно будет хотя бы два узла).

В пункте б) ответ 6. Наводящий вопрос: сколько вершин может быть у многоугольника с вершинами в узлах, если внутри него вообще нет других узлов?

Сначала разберемся с пунктом а). Ответ, как уже говорилось, 9, а пример такого треугольника изображен слева на рисунке 1.

Рис. 1

Докажем, что больше 9 узлов на границе треугольника с единственным узлом внутри быть не может. Если на каждой стороне кроме вершин есть не больше двух внутренних — то есть отличных от вершин — узлов, то и доказывать нечего. Пусть на стороне АВ треугольника АВС есть хотя бы три внутренних узла (а такое возможно — пример изображен справа на рис. 1). Покажем, что тогда на других сторонах не может быть больше одного внутреннего узла. Допустим, на стороне АС треугольника таких узлов оказалось хотя бы два (рис. 2). Обозначим буквой D тот из них, который ближе к вершине А, а буквой Е — ближайший к А узел на стороне АВ. Проведем DF параллельно АВ и отложим на луче DF отрезки DG и GH, равные АE. Ясно, что точки G и H — это узлы. Осталось показать, что точка H лежит именно на отрезке DF, то есть, что она внутри треугольника. Из-за того, что на стороне АС есть еще хотя бы один внутренний узел, отличный от D, верно неравенство \( \dfrac{CD}{AC}\ge\dfrac23 \), из которого и из подобия треугольников АВС и DFC следует, что \( DF\ge\dfrac23AB \). Из-за того, что на стороне АВ находятся хотя бы три внутренних узла, верно неравенство \( \dfrac{AE}{AB}\le\dfrac14 \), откуда \( DH=2AE\le\dfrac12AB \). То есть действительно \( DH<DF \), что и требовалось.

Рис. 2

Теперь обсудим пункт б). Шестиугольник с единственным узлом внутри изображен на рис. 3. Почему большего числа вершин у выпуклого многоугольника с одним внутренним узлом быть не может?

Рис. 3

Прежде, чем ответить на этот вопрос, поймем, сколько вершин может быть у выпуклого многоугольника, внутри которого нет узлов. Три или четыре вершины может быть — примеры легко придумать. Причем, если не только внутри четырехугольника, но и на его сторонах нет узлов кроме вершин, то этот четырехугольник — обязательно параллелограмм (попробуйте доказать это). Может ли быть больше вершин? Оказывается, нет: у любого выпуклого пятиугольника уже будет хотя бы один внутренний узел. Доказывается это от противного: если предположить, что внутри выпуклого пятиугольника ABCDE нет узлов (можно считать, что и на его сторонах нет узлов кроме вершин — иначе пятиугольник можно «уменьшить»), то получится, что внутри и на сторонах четырехугольников ABCD и ABCE тоже нет узлов, а значит, это параллелограммы. То есть ABCDE на самом деле вырождается в четырехугольник.

Теперь вернемся к исходному вопросу. Допустим, что есть n-угольник с единственным внутренним узлом O и что n ≥ 7. Проведем через точку О прямую, которая не проходит через вершины многоугольника. Тогда (по принципу Дирихле) в одной из двух получившихся полуплоскостей окажется минимум четыре вершины многоугольника. Обозначим их A, B, C, D. Тогда внутри пятиугольника OABCD узлов не окажется, что противоречит предыдущим рассуждениям.

Вопросы, рассмотренные в этой задаче могут показаться совершенно детскими и несерьезными — ну, в самом деле, какой может быть глубокий смысл в рисовании многоугольничков на клетчатой бумаге? Тем более таких простых многоугольников, какие встречались в задаче. Однако совершенно неожиданным образом здесь вылезают связи с довольно сложными областями математики.

Чтобы увидеть эти связи, потребуется одно несложное определение. Пусть имеется нарисованный на клетчатой плоскости выпуклый многоугольник A₁A₂...A_n, все вершины которого лежат в узлах и внутри которого находится всего один узел О. Тогда двойственный многоугольник строится следующим образом (рис. 4). Нужно взять векторы сторон \( \overrightarrow{A_1A_2} \), \( \overrightarrow{A_2A_3} \), ..., \( \overrightarrow{A_nA_1} \) и отложить их все от точки О. После этого на каждом из отложенных векторов нужно отметить ближайший к О узел. Соединяя последовательно отмеченные узлы, получим двойственный многоугольник.

Рис. 4

Оказывается, верна следующая теорема: если на границе выпуклого многоугольника с единственным внутренним узлом находится b узлов, а на границе двойственного многоугольника — b* узлов, то b + b* = 12.

Эта теорема — ее называют «теоремой о 12 целых точках» — была открыта совсем недавно, в конце ХХ века. Интересно, что первые ее доказательства использовали сложные понятия вроде торических многообразий (toric variety) или модулярных форм. С этими двумя доказательствами, а также еще с двумя идеями доказательств этой теоремы можно познакомиться в статье Lattice Polygons and the Number 12. Правда, все они нетривиальные и требуют довольно серьезного уровня подготовки. К счастью, несколько лет назад появилось и элементарное доказательство этой теоремы, которое доступно старшекласснику. С ним можно познакомиться в статье Д. Реповша, М. Б. Скопенкова и М. Ценцеля «Элементарное доказательство теоремы о 12 целых точках».

Из теоремы о 12 точках ответы на вопросы задачи следуют почти мгновенно. Действительно, раз меньше трех точек на границе двойственного треугольника быть не может, то и больше 9 точек на границе исходного треугольника тоже не будет. В пункте б) рассуждение такое: поскольку многоугольник выпуклый, то у двойственного многоугольника число вершин будет таким же, как и у исходного (векторы, которые мы откладываем от внутреннего узла, не могут быть сонаправлены как раз из-за выпуклости), поэтому их не больше 6.

При подготовке этой задачи использовались материалы XVI Летней конференции Турнира городов.