Разделы 
Дополнительно
Задача по математике - 3665
2019-06-15 
Вершины правильного $n$-угольника покрашены несколькими красками (каждая одной краской) так, что точки одного и того же цвета служат вершинами правильного многоугольника. Докажите, что среди этих многоугольников найдутся два равных.
Решение:
Назовем систему единичных векторов $e_1, e_2, \cdots, e_m$ (с общим началом $О$) симметричной, если при повороте на угол $2 \pi k/m$ (при некотором $k < m$) она переходит в себя. Сумма векторов такой системы очевидно равна 0, так как она не меняется при повороте на угол $\frac{2 \pi k}{m} < 2 \pi$.
В частности, симметричную систему образуют векторы, идущие в последовательные вершины правильного $m$-угольника: для них $k = 1$.
Подвергнем все единичные векторы с началом $О$ преобразованию $e \rightarrow D^l e$ ($l$ - кратному закручиванию): увеличим угол от начального направления $Оx$ до $e$ в $l$ раз; полученный вектор и примем за $D^le$. При таком преобразовании $D^l$ симметричная система векторов перейдет в симметричную, если только $kl$ не делится на $m$ (угол $2 \pi k/m$ между соседними векторами $e_i, e_{i+1}$ увеличится в $l$ раз; вычитая из $2 \pi kl/m$ кратный $2 \pi$ угол, получим, что угол между $D^le_i$ и $D^le_{i+1}$ равен $2 \pi r/m$, где $r$ - остаток от деления $kl$ на $m$). Если же $kl$ делится на $m$ (в частности, при $k = m$), то все векторы $D^le_i$ сольются в один.
После этих замечаний перейдем к решению задачи. Предположим, что вершины $n$-угольника удалось раскрасить несколькими красками, так что вершины одного цвета образуют правильные многоугольники: $l$-угольник, $q_1$-угольник, $q_2$-угольник, \cdots, $q_s$-угольник, где $l < q_1 < q_2 < \cdots < q_s$. Симметричную систему векторов, проведенных в вершины $n$-угольника, мы можем тем самым разбить на $s + 1$ симметричных систем из $l_1, q_1, q_2, \cdots, q_s$ векторов. Пока никакого противоречия нет: сумма каждой из них равна 0, и общая сумма - тоже. Но стоит подвергнуть все наши векторы $l$-кратному закручиванию, как противоречие возникнет: все $l$ векторов первой системы сольются в один, так что их сумма станет отличной от 0, а остальные системы - из $q_i (i = 1, 2, \cdots, s)$ векторов и из всех $n$ векторов - останутся правильными, поскольку углы между соседними векторами в них $2 \pi l/q_1 < 2 \pi, 2 \pi l /q_2 < 2 \pi, \cdots, 2 \pi l/n < 2 \pi$, так что сумма в них останется равной 0.
Это замечательное решение придумал А. Лифшиц. Идея «$l$-кратного закручивания» векторов становится более прозрачной, если рассматривать векторы как комплексные числа; преобразование $D^l$ - это просто возвышение в степень $z \rightarrow z^l$ комплексных чисел $z$ с $|z| = 1$; симметричная система векторов - это геометрическая прогрессия $u, u \epsilon, u \epsilon^2, \cdots, u \epsilon^m$ , где $|m| = 1$ и $\epsilon$ - некоторый корень $m$-й степени из $1, \epsilon \neq 1$; если аргумент числа $\epsilon$ - угол между соседними векторами системы - равен $2 \pi k/m$, то такая система, как можно показать, состоит из векторов, идущих в вершины правильного $m/d$-угольника, где $d$ - некоторый делитель $m, d < m$, причем в каждую вершину идет $d$ векторов.
Решение этой задачи показывает, что любое разбиение множества целых чисел Z на несколько непересекающихся (бесконечных в обе стороны) арифметических прогрессий получается только таким способом: $Z$ разбивается на $d$ прогрессий с одной и той же разностью $d$, затем, быть может, одна (или несколько) из них разбивается на прогрессии с одинаковой разностью и т. д. Применение в теоретико-числовых задачах комплексных чисел, подобное описанному в нашем решении, называется «методом тригонометрических сумм».
Вершины правильного $n$-угольника покрашены несколькими красками (каждая одной краской) так, что точки одного и того же цвета служат вершинами правильного многоугольника. Докажите, что среди этих многоугольников найдутся два равных.
Решение:
Назовем систему единичных векторов $e_1, e_2, \cdots, e_m$ (с общим началом $О$) симметричной, если при повороте на угол $2 \pi k/m$ (при некотором $k < m$) она переходит в себя. Сумма векторов такой системы очевидно равна 0, так как она не меняется при повороте на угол $\frac{2 \pi k}{m} < 2 \pi$.
В частности, симметричную систему образуют векторы, идущие в последовательные вершины правильного $m$-угольника: для них $k = 1$.
Подвергнем все единичные векторы с началом $О$ преобразованию $e \rightarrow D^l e$ ($l$ - кратному закручиванию): увеличим угол от начального направления $Оx$ до $e$ в $l$ раз; полученный вектор и примем за $D^le$. При таком преобразовании $D^l$ симметричная система векторов перейдет в симметричную, если только $kl$ не делится на $m$ (угол $2 \pi k/m$ между соседними векторами $e_i, e_{i+1}$ увеличится в $l$ раз; вычитая из $2 \pi kl/m$ кратный $2 \pi$ угол, получим, что угол между $D^le_i$ и $D^le_{i+1}$ равен $2 \pi r/m$, где $r$ - остаток от деления $kl$ на $m$). Если же $kl$ делится на $m$ (в частности, при $k = m$), то все векторы $D^le_i$ сольются в один.
После этих замечаний перейдем к решению задачи. Предположим, что вершины $n$-угольника удалось раскрасить несколькими красками, так что вершины одного цвета образуют правильные многоугольники: $l$-угольник, $q_1$-угольник, $q_2$-угольник, \cdots, $q_s$-угольник, где $l < q_1 < q_2 < \cdots < q_s$. Симметричную систему векторов, проведенных в вершины $n$-угольника, мы можем тем самым разбить на $s + 1$ симметричных систем из $l_1, q_1, q_2, \cdots, q_s$ векторов. Пока никакого противоречия нет: сумма каждой из них равна 0, и общая сумма - тоже. Но стоит подвергнуть все наши векторы $l$-кратному закручиванию, как противоречие возникнет: все $l$ векторов первой системы сольются в один, так что их сумма станет отличной от 0, а остальные системы - из $q_i (i = 1, 2, \cdots, s)$ векторов и из всех $n$ векторов - останутся правильными, поскольку углы между соседними векторами в них $2 \pi l/q_1 < 2 \pi, 2 \pi l /q_2 < 2 \pi, \cdots, 2 \pi l/n < 2 \pi$, так что сумма в них останется равной 0.
Это замечательное решение придумал А. Лифшиц. Идея «$l$-кратного закручивания» векторов становится более прозрачной, если рассматривать векторы как комплексные числа; преобразование $D^l$ - это просто возвышение в степень $z \rightarrow z^l$ комплексных чисел $z$ с $|z| = 1$; симметричная система векторов - это геометрическая прогрессия $u, u \epsilon, u \epsilon^2, \cdots, u \epsilon^m$ , где $|m| = 1$ и $\epsilon$ - некоторый корень $m$-й степени из $1, \epsilon \neq 1$; если аргумент числа $\epsilon$ - угол между соседними векторами системы - равен $2 \pi k/m$, то такая система, как можно показать, состоит из векторов, идущих в вершины правильного $m/d$-угольника, где $d$ - некоторый делитель $m, d < m$, причем в каждую вершину идет $d$ векторов.
Решение этой задачи показывает, что любое разбиение множества целых чисел Z на несколько непересекающихся (бесконечных в обе стороны) арифметических прогрессий получается только таким способом: $Z$ разбивается на $d$ прогрессий с одной и той же разностью $d$, затем, быть может, одна (или несколько) из них разбивается на прогрессии с одинаковой разностью и т. д. Применение в теоретико-числовых задачах комплексных чисел, подобное описанному в нашем решении, называется «методом тригонометрических сумм».
