51
Равномерные расположения
М. Л. КОНЦЕВИЧ
Пусть на окружности расположено точек, и неокторые из них выделены — будем называть их черными, а остальные — белыми. Легко указывать самое неравномерное расположение черных точек среди остальных: нужно расставить их все подряд. Оказывается, можно дать в полне естественное определение и для самого равномерного расположения черных точек. Такие равномерные расположения обнаруживают во многих математических, да и не только математических, ситуациях. О них и рассказывается в этой заметке; здесь приводится решение задачи М818 из «Задачика «Квана», опубликованной в № 9, 1983 г.
Определение, примеры и основная теория
Назовем расположение черных точек равномерным, если для каждой натурального (где — общее количество точек — черных и белых) количество черных точек в наборах из последовательных точек на окружности отличия друг от друга не более чем на 1. Например, расположение 4 точек среди 9 на рисунке 1 равномерно — в этом легко убедиться перебором, а расположение 7 точек среди 17 на рисунке 2 не равномерно. Равномерное расположение черных точек среди точек на окружности будем обозначать . Заметим, что замена цветов — черного на белый — превращает в , поэтому всегда можно свести до к следующим .
Расположение нам особенно хорошо знаком — это расположение пяти коротких (менее 31 дня) месяцев в году, а также пяти черных клавиш среди 12 клавиш одной; octавы; легко убедиться, что это — одинаковые расположения: яварю соответствует nota «фа», февраль — «фа диез» и т. д., так что, чтобы проиграть хроматическое гамму, достаточно вспомнить, сколько дней в каждом из 12 месяцев (рис. 3, 4). Изображение равномерных расположений не на окружности, а в виде перiodической последовательности черных и белых точек на прямой, встретившееся в последнем примере, оказывается очень удобным для новых интерпретаций и обобщений, которые мы указываем в заключительных задачах.
На внешних окружностях рисунков 5 и 6 показаны расположения и . Мы обязываем общий способ, который они построены; одновременно будет доказана следующая
52
Основная теорема: для любых натуральных чисел n и k (k≤n) существует равномерное расположение P(n;k), причем только (с точностью до переdivision точки по окружности без изменения порядка их расположения).
Это и требовалось сделать в задаче M818.
Лемма «о спуск»
и построение P(n;k)
Условия расстояние между двумя крайними точками A и B отрезка из m последовательных точек на окружности считать равным m-1 (при этом между A и B лежит еще m-2 точки); это расстояние мы будем ниже называть также «длиной» отрезка AB и обозначать |AB|.
Рассмотрим сначала очевидный случай, когда n делится на k. При расстановке k черных точек на равных расстояниях d=n/k друг от друга получаем равномерное расположение P(n;k): среди m вершин, расположенных подряд, всегда будет [m/d] или [m/d]+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 (для P(17;7)) — дкдккк. Видно, что во второй последовательности буквы д расположены равномерно, а в первой — нет. Такие последовательности удобно снова изобразать точками на меньшей окружности: длиные отрезки — черными, короткие — белыми (рис. 5, 6). И вот ключевая лемма. Пусть k черных точек среди n точек на окружности, разбавают ее на отрезки длины d+1 и d. Для того чтобы расположение черных точек было равномерным, необходимо и достаточно, чтобы было равномерным соответствующей расположение r черных точек среди k точек на меньшей окружности.
По этой лемме, которое мы докажем чуть ниже, из существования и единственности P(k;r) следует существование и единственности P(n;k). Отсюда сразу получается доказательство основной теоремы (по индукции) и удобный способ построения равномерных расположений при любых n и k. Ведь назывный «спуск» можно продолжить: k разделить (с остатком r₂<r) на r₁=r, затем — r₁ (с остатком r₃<r₂) на r₂ и т. д., пока какой-то остаток r₁-1 не разделится на следующий r₂. (Это — известный алгоритм Евклида отискания наиболее общего делителя чисел n и k: r₅=НОД (n;k).) Таким образом, за несколько шагов спуска мы придем к оченьному случанию P(r₅-1;r₅), когда r₅-1 делится на r₅. Проделав для данной пары чисел n и k необходимо деления с остатком (как в алгоритме Евклида), мы узнали, как целое расположение P(r₅-1;r₅), P(r₅-2;r₅-1),…· ведет к P(n;k) и может «вырастить» расположение P(n;k) (как показано на рисунке 6), построив из «бусин» двух цветов в концентрических ярусов-окружностей. Потренируйтесь в построении этих «ожерели». В наших примерах n и k взаимно просты, то есть r₅=1 и спуск приводит к расположению вида P(r₅-1;1) с единственной выделенной среди остальных точкой. Заметим, что практические спуск можно несколько ускорить; если на некотором шаге оказывается больше половины черных точок, то можно «пометь цвет» (перейти от пары (n, k) к паре (n;n-k)), так что на каждом шаге число точек будет убывать более чем вдвое.
Доказательство леммы
Занутерум по порядку (скажем, по часовой стрелке) черные точки: B₁, B₂, …, Bₖ. Расстояние (отсутствие такое по часовой стрелке) от B₁ до q-й от нее черной точки B₁+q обозначаем |B₁B₁+q|, здесь B₁+1=B₁, B₁+2=B₂ и т. д. Среди отрезков B₁B₁+1, B₁+1B₂+2, …, B₁+q-1B₁+qровно |B₁B₁+q|—qd имеют длину d+1, остальные — длину d. Таким образом, мы должны доказать, что равномерность расположения точки B₁ эквивалентна условия: при каждом q<k расстояния |B₁B₁+q| отличается друг от друга не больше чем на 1. Доказательство в обе стороны проводет от противного. Если нашей расположение не равномерно, то найдет два отрезка одинаковой длины, на одном из которых расположено лишь q-1 черных точек B₁+1, …, B₁+q-1, на другом — по крайней мере на 2 большие B₁, B₁+1, …, B₁+q, но тогда |B₁B₁+q|—|B₁B₁+q|≥2. Обратно, если выполнен последнее неравенство, то на отрезке B₁B₁+q лежит q+1 черная точка, а на отрезке той же длины, начиная шемся со следующей за B₁ точки, — по крайней мере на две меньше.