Текст статьиКонцевич М. Л. Равномерные расположения // Квант. — 1985. — № 7. — С. 51—52, 59.
Пусть на окружности расположено $n$ точек, и некоторые $k$ из них выделены — будем называть их чёрными, а остальные — белыми. Легко указать
самое неравномерное расположение $k$ чёрных точек среди остальных: нужно
расставить их все подряд. Оказывается, можно дать вполне естественное
определение и для самого равномерного расположения чёрных точек. Такие
равномерные расположения обнаруживаются во многих математических, да и не только математических, ситуациях. О них и рассказывается в этой заметке;
здесь приводится решение задачи М818 из «Задачника
«Кванта», опубликованной в № 9, 1983 г.
Определение, примеры и основная теорема
Назовём расположение чёрных точек равномерным, если для каждого
натурального $m\lt n$ (где $n$ — общее количество точек — чёрных и белых)
количества чёрных точек в наборах из $m$ последовательных точек на окружности отличаются друг от друга не более чем на 1. Например,
расположение 4 точек среди 9 на рисунке 1 равномерно — в этом
легко убедиться перебором, а расположение 7 точек среди 17 на рисунке 2 не равномерно. Равномерное расположение $k$ чёрных точек
среди $n$ точек на окружности будем обозначать $\text{Р}(n;k)$. Заметим,
что замена цветов — чёрного на белый — превращает $\text{Р}(n;k)$ в $\text{Р}(n;n-k)$, поэтому всегда можно свести дело к случаю
$k\le\dfrac n2$.
Рис. 1Рис. 2
Расположение $\text{Р}(12;5)$ нам особенно хорошо знакомо — это расположение пяти коротких (менее 31 дня) месяцев в году, а также пяти
чёрных клавиш среди 12 клавиш одной октавы; легко убедиться, что это —
одинаковые расположения: январю соответствует нота «фа», февралю — «фа диез»
и т. д., так что, чтобы проиграть хроматическую гамму, достаточно вспомнить,
сколько дней в каждом из 12 месяцев (рис. 3, 4). Изображение
равномерных расположений не на окружности, а в виде периодической
последовательности чёрных и белых точек на прямой, встретившееся в последнем
примере, оказывается очень удобным для новых интерпретаций и обобщений,
которые мы укажем в заключительных задачах.
Рис. 3Рис. 4Рис. 5Рис. 6
На внешних окружностях рисунков 5 и 6 показаны расположения
$\text{Р}(17;7)$ и $\text{Р}(84;19)$. Мы объясним общий способ, которым они построены; одновременно будет доказана следующая
Основная теорема:для любых натуральных чисел $n$ и $k$
$(k\le n)$ существует равномерное расположение $\text{Р}(n;k)$, причём
только одно (с точностью до передвижения точек по окружности без изменения порядка их расположения).
Это и требовалось сделать в задаче М818.
Лемма «о спуске» и построение $\bm{\textbf{Р}(n;k)}$
Условимся расстояние между двумя крайними точками $A$ и $B$ отрезка из $m$ последовательных точек на окружности считать равным $m-1$ (при этом
между $A$ и $B$ лежит ещё $m-2$ точек); это расстояние мы будем ниже
называть также «длиной» отрезка $AB$ и обозначать $|AB|$.
Рассмотрим сначала очевидный случай, когда $n$ делится на $k$. При расстановке $k$ чёрных точек на равных расстояниях $d=\dfrac nk$ друг от друга получаем равномерное расположение $\text{Р}(n;k)$: среди $m$ вершин,
расположенных подряд, всегда будет $\left[\dfrac md\right]$ или $\left[\dfrac md\right]-1$ чёрных точек ($[x]$ — целая часть числа $x$). При любой другой расстановке $k$ чёрных точек их расположение не будет
равномерным: среди расстояний между соседними чёрными точками встретится
хотя бы одно не меньше $d+1$ и одно — не больше $d-1$, так что среди $m=d$
последовательных, точек может оказаться и 2, и 0 чёрных.
Для произвольных $n$ и $k$, как показывает аналогичное рассуждение,
расстояния между соседними чёрными точками равномерного расположения также
должны отличаться друг от друга не более чем на 1. В сумме все эти $k$
расстояний равны $n$, поэтому если $n=kd+r$ (мы разделили $n$ на $k$ с остатком), то $r$ из этих расстояний имеют длину $d+1$, а остальные — $d$.
Но важно ещё (сравните рисунки 2 и 5), как $r$ более длинных
отрезков расположены среди всех $k$ отрезков по окружности.
Например, на рисунке 2 (с неравномерным расположением)
последовательность длинных и коротких отрезков, выписанная по часовой
стрелке от точки со звёздочкой, выглядит так: дкддккк, а на рисунке 5
(для $\text{Р}(17;7)$) — дкдккдк. Видно, что во второй последовательности
буквы д расположены равномерно, а в первой — нет. Такие последовательности
удобно снова изображать точками на меньшей окружности: длинные отрезки —
чёрными, короткие — белыми (рис. 5, 6). И вот ключевая
Лемма.Пусть $k$ чёрных точек среди $n$ точек на окружности
разбивают её на отрезки длины $d+1$ и $d$. Для того чтобы расположение
чёрных точек было равномерным, необходимо и достаточно, чтобы было
равномерным соответствующее расположение $r$ чёрных точек среди $k$ точек на меньшей окружности.
По этой лемме, которую мы докажем чуть ниже, из существования и единственности $\text{Р}(k;r)$ следует существование и единственность
$\text{Р}(n;k)$. Отсюда сразу получается доказательство основной теоремы (по
индукции) и удобный способ построения равномерных расположений при любых $n$
и $k$. Ведь начатый «спуск» можно продолжить: $k$ разделить (с остатком
$r_2\lt r$) на $r_1=r$, затем — $r_1$ (с остатком $r_3\lt r_2$) на $r_2$
и т. д., пока какой-то остаток $r_{s-1}$ не разделится нацело на следующий
$r_s$. (Это — известный алгоритм Евклида отыскания наибольшего общего
делителя чисел $n$ и $k$: $r_s=\gcd(n;k)$.) Таким образом, за несколько
шагов спуска мы придём к очевидному случаю $\text{Р}(r_{s-1};r_s)$, когда
$r_{s-1}$ делится на $r_s$. Проделав для данной пары чисел $n$ и $k$
необходимые деления с остатком (как в алгоритме Евклида), мы узнаем, какая
цепочка расположений $\text{Р}(r_{s-1};r_s)$, $\text{Р}(r_{s-2};r_{s-1})$,
$\ldots$ ведёт к $\text{Р}(n;k)$ и может «вырастить» расположение
$\text{Р}(n;k)$ (как показано на рисунке 6), построив из «бусин» двух
цветов $s$ концентрических ярусов-окружностей. Потренируйтесь в построении
этих «ожерелий». В наших примерах $n$ и $k$ взаимно просты, т. е. $r_s=1$ и спуск приводит к расположению вида $\text{Р}(r_s;1)$ с единственной
выделенной среди остальных точкой. Заметим, что практически спуск можно
несколько ускорить; если на некотором шагу окажется больше половины чёрных
точек, то можно «поменять цвет» (перейти от пары $(n;k)$ к паре $(n;n-k)$),
так что на каждом шаге число точек будет убывать более чем вдвое.
Доказательство леммы
Занумеруем по порядку (скажем, по часовой стрелке) чёрные точки: $B_1$,
$B_2$, $\ldots$, $B_k$. Расстояние (отсчитываемое также по часовой стрелке)
от $B_j$ до $q$-й от неё чёрной точки $B_{j+q}$, обозначим $|B_jB_{j+q}|$,
здесь $B_{k+1}=B_1$, $B_{k+2}=B_2$ и т. д. Среди отрезков $B_jB_{j+1}$,
$B_{j+1}B_{j+2}$, $\ldots$, $B_{j+q-1}B_{j+q}$ ровно $|B_jB_{j+q}|-qd$ имеют
длину $d+1$, остальные — длину $d$. Таким образом, мы должны доказать, что равномерность расположения точек $B_j$ эквивалентна условию: при каждом
$q\lt k$ расстояния $|B_jB_{j+q}|$ отличаются друг от друга не больше чем на 1. Доказательство в обе стороны проведём от противного. Если наше
расположение не равномерно, то найдутся два отрезка одинаковой длины, на одном из которых расположено лишь $q-1$ чёрных точек $B_{i+1}$, $\ldots$,
$B_{i+q-1}$, на другом — по крайней мере на 2 больше $B_j$, $B_{j+1}$,
$\ldots$, $b_{j+q}$, но тогда $|B_iB_{i+q}|-|B_jB_{j+q}|\ge2$. Обратно, если
выполнено последнее неравенство, то на отрезке $B_jB_{j+q}$ лежит $q+1$
чёрных точек, а на отрезке той же длины, начинающемся со следующей за $B_i$
точки, — по крайней мере на две меньше.
Несколько задач
Разделим окружность на $n$ равных дуг и впишем в неё правильный
$n$-угольник (вершины которого не попадают в концы дуг, рис. 7).
Закрасим в чёрный цвет те $k$ дуг, в которые попали вершины. Докажите, что их расположение среди всех $n$ дуг равномерно. (Эта задача даёт новый способ
построения $\text{Р}(n;k)$.)
Рис. 7
Будем располагать $n$ (чёрных и белых) точек в вершинах правильного
$n$-угольника. Докажите, что чёрные точки равномерного расположения
$\text{Р}(n;k)$ образуют множество, симметричное относительно некоторой
прямой.
Сколько таких осей симметрии у $\text{Р}(n;k)$?
В следующих задачах изучается несколько более общее понятие: равномерное
расположение на прямой. Пусть на прямой задана бесконечная (в обе стороны)
последовательность точек — в частности, например, целочисленных точек
числовой оси, — «раскрашенных» в чёрный и белый цвет. Она называется
равномерной, если для любого натурального $m$ количество чёрных
среди $m$ последовательных её точек колеблется не более чем на 1. Докажите
следующие теоремы.
Для данных чисел $a$, $b$ ($a\gt1$) целые числа $[al+b]$, где $l$ пробегает всевозможные целые числа, назовём чёрными, остальные целые
числа — белыми. Полученное расположение равномерно. Оно периодично, если и только если $a$ — рациональное число (при $a=\dfrac nk$ оно имеет период $n$
и расположение чёрных и белых точек на периоде совпадает с расположением
$\text{Р}(n;k)$ на окружности).
Для любого равномерного расположения найдётся
число $\alpha$ такое, что количество чёрных точек среди любых $m$
последовательных точек расположения отличается от $\alpha m$ менее чем на 1.
Проведём на бесконечном листе клетчатой бумаги
прямую, не проходящую через узлы, отметим чёрным точки её пересечения с линиями одного направления, белым — другого (рис. 8). Полученное
расположение равномерно.
Рис. 8
Две бесконечные (в обе стороны) арифметические прогрессии $a_1l+b_1$,
$a_2l+b_2$ ($l\in\mathbb{Z}$) не имеют общих членов. На числовой прямой
числа одной прогрессии помечены чёрным, другой — белым. Полученное
расположение чёрных и белых точек равномерно.
