Вершины правильного $n$-угольника покрашены несколькими красками
(каждая — одной краской) так, что точки одного и того же цвета служат
вершинами правильного многоугольника. Доказать, что среди этих многоугольников
найдется два равных.
Н. Б. Васильев
Всесоюзная математическая олимпиада (1970 год, 10 класс)
Предположим, что вершины некоторого правильного $n$-угольника удалось раскрасить так, что все одинаково покрашенные вершины составляют различные правильные многоугольники: $m_1$-угольник, $m_2$-угольник, $m_3$-угольник, $\ldots$, где $m_1\lt m_2\lt m_3\lt\ldots$ Наименьшее из этих чисел $m_1$ будет играть в наших рассуждениях особую роль, и мы обозначим его просто через $m$.
Проведём из центра $O$ $n$-угольника векторы во все его вершины; обозначим их по порядку: $\boldsymbol{a}_1$, $\boldsymbol{a}_2$, $\boldsymbol{a}_3$, $\ldots$, $\boldsymbol{a}_n$ (рис. 1, a). Тогда
$$
\angle\boldsymbol{a}_1\boldsymbol{a}_2=\angle\boldsymbol{a}_2\boldsymbol{a}_3=\ldots=\angle\boldsymbol{a}_{n-1}\boldsymbol{a}_n=\angle\boldsymbol{a}_n\boldsymbol{a}_1=\dfrac{2\pi}{n}.
$$
Здесь и ниже через $\angle\boldsymbol{a}\boldsymbol{b}$ мы обозначаем величину (наименьшего неотрицательного) угла, на который нужно повернуть против часовой стрелки вектор $\boldsymbol{a}$, чтобы он совпал с вектором $\boldsymbol{b}$; всегда $0\le\angle\boldsymbol{a}\boldsymbol{b}\lt2\pi$.
Рис. 1. Представьте себе, что цветные точки на рисунке а — бусины, нанизанные на проволоку, согнутую в спираль. Мы смотрим на эту спираль сверху, и поэтому две крайние красные бусины $A'$ и $A''$ проектируются для нас в одну точку $A$. Если мы теперь закрепим одну из бусин — $A'$, а $A''$ протянем по проволоке ещё 2 оборота, то придём к рисунку б, на котором углы между соседними векторами увеличились в 3 раза.
Будем говорить, что векторы $\boldsymbol{c}_1$, $\boldsymbol{c}_2$, $\boldsymbol{c}_3$, $\ldots$, $\boldsymbol{c}_q$ на плоскости, проведённые из точки $O$, образуют правильную систему, если они имеют равные длины и образуют друг с другом равные углы:
$$
\angle\boldsymbol{c}_1\boldsymbol{c}_2=\angle\boldsymbol{c}_2\boldsymbol{c}_3=\ldots=\angle\boldsymbol{c}_{q-1}\boldsymbol{c}_q=\angle\boldsymbol{c}_q\boldsymbol{c}_1=\alpha\gt0.
$$
Нам понадобится следующий почти очевидный факт (его доказательство приведено в конце решения).
Лемма. Сумма векторов, образующих правильную систему, равна нулю.
Прежде чем пользоваться леммой, проделаем с нашими векторами такое преобразование. Будем считать, что вектор $\boldsymbol{a}_1$ идёт в одну из вершин $m$-угольника. Обозначим его просто через $\boldsymbol{a}$ и будем все углы отсчитывать от него (в положительном направлении, т. е. против часовой стрелки). Обозначим через $\boldsymbol{b}_i$ вектор, который получается из $\boldsymbol{a}$ поворотом на угол $m\angle\boldsymbol{a}\boldsymbol{a}_i$; (для каждого $i=1$, 2, $\ldots$, $n$). При отображении $\boldsymbol{a}_i\to\boldsymbol{b}_i$, которое мы только что построили (на рисунке 1, б изображено такое отображение для $m=3$), углы между векторами увеличиваются в $m$ раз; более точно: если $m\angle\boldsymbol{a}_i\boldsymbol{a}_j\lt2\pi$, то $\angle\boldsymbol{b}_i\boldsymbol{b}_j=m\angle\boldsymbol{a}_i\boldsymbol{a}_j$. Поэтому правильную систему векторов с углом $\alpha\lt\dfrac{2\pi}{m}$ это отображение переводит снова в правильную систему векторов. В частности, сумма всех векторов $\boldsymbol{b}_1$, $\boldsymbol{b}_2$, $\ldots$, $\boldsymbol{b}_n$ равна нулю.
Подсчитаем эту сумму другим способом: найдём сначала сумму векторов, соответствующих вершинам каждого цвета, а потом сложим все эти суммы. Рассмотрим сначала все векторы $\boldsymbol{a}_i$, идущие в вершины $m_k$-угольника, где $m_k\gt m$. Это правильная система векторов с углом $\dfrac{2\pi}{m_k}\lt\dfrac{2\pi}{m}$. После отображения из неё получится снова правильная система, и сумма полученных векторов будет равна нулю.
Рассмотрим теперь векторы, идущие в вершины $m$-угольника. Угол между соседними векторами равен в этом случае $\dfrac{2\pi}{m}$, и после отображения все эти $m$ векторов совпадут с вектором $\boldsymbol{a}$, так что их сумма будет равна $m\boldsymbol{a}$ (на рисунке 1 это случилось с красными и с чёрными векторами).
Итак, получили противоречие: с одной стороны, сумма всех $\boldsymbol{b}_i$ равна нулю, с другой — она равна $m\boldsymbol{a}$. Поэтому наше предположение неверно.
Доказательство леммы. Физик сказал бы, что это утверждение очевидно из соображений симметрии. Один из способов превратить эти соображения в строгое доказательство состоит в следующем. Предположим, что $\boldsymbol{c}_1+\boldsymbol{c}_2+\ldots+\boldsymbol{c}_n=\boldsymbol{s}$ Повернём все векторы $\boldsymbol{c}_1$, $\boldsymbol{c}_2$, $\ldots$, $\boldsymbol{c}_n$ вокруг точки $O$ на угол $\alpha$. Тогда, разумеется, и их сумма повернётся на угол $\alpha$. Но по условию вся система из $n$ векторов после поворота на угол $\alpha$ совпадёт сама с собой ($\boldsymbol{c}_1$ попадёт на место $\boldsymbol{c}_2$, $\boldsymbol{c}_2$ — на место $\boldsymbol{c}_3$, $\ldots$, $\boldsymbol{c}_n$ — Ha место $\boldsymbol{c}_1$). Поэтому вектор $\boldsymbol{s}$ после поворота на угол $\alpha$ не должен измениться. Это может быть только в том случае, если $\boldsymbol{s}=0$.
Можно доказать, что правильная система из $q$ векторов в общем случае состоит из $q=dr$ векторов, проведённых из точки $O$ к вершинам правильного $r$-угольника, так что в каждую вершину проведено по $d$ равных векторов (если включить сюда и «двуугольники» — пары противоположных векторов, ссответствующие $m=2$); при этом $\alpha$ может быть равно любому из чисел $\dfrac{2\pi l}{r}$, где $l$ и $r$ взаимно просты, $0\lt l\lt r$. Мы оставили это замечание под конец, поскольку формально в доказательстве мы обошлись без детального выяснения того, как устроена правильная система векторов $\boldsymbol{b}_i$. Но, конечно, разбираясь в доказательстве «по существу», полезно это выяснить.
Идею изложенного здесь решения задачи предложил А. Лившиц (Ленинград). Внимательно разобравшись в этом решении, можно доказать, что любое разбиение вершин правильного $n$-угольника на несколько множеств, соответствующих (не обязательно различным) правильным многоугольникам, можно получить таким образом: сначала разбить $n$-угольник на несколько $m$-угольников (для этого нужно, чтобы $n$ делилось на $m$), затем один из полученных правильных многоугольников снова разбить на несколько равных правильных многоугольников (см. рис. 1) и т. д. несколько раз. Читателям, которые захотят разобраться в этом подробнее, мы советуем также обдумать связь нашей «одномерной» задачи с «двумерной» задачей M3, формулировка которой обсуждалась в «Кванте» №7 за 1970 год (стр. 54—55) и прежде всего установить эквивалентность нашей задачи M50 следующей: доказать, что множество всех целых чисел нельзя разбить на конечное число арифметических прогрессий (бесконечных в обе стороны), разности которых попарно различны.
