Окружности на клетчатой бумаге

Обратите внимание, что если центр окружности сам является узлом клетчатой бумаги, то количество лежащих на этой окружности узлов кратно четырём. Если же центр окружности находится в середине стороны какой-либо клеточки, то на такой окружности будет расположено чётное число узлов. Это относится и к тем случаям, когда окружность вообще не проходит через узлы клетчатой бумаги, потому что ноль делится как на 2, так и на 4 (и вообще на любое натуральное число).

Будем считать, что расстояние между соседними узлами клетчатой бумаги равно единице. Тогда на ней можно задать систему координат таким образом, чтобы множество всех узлов в точности совпадало со множеством всех точек, обе координаты которых целочисленны.

а) Воспользуйтесь тем фактом, что если центр окружности радиуса r является началом координат, то количество лежащих на ней узлов клетчатой бумаги есть число целочисленных решений уравнения

    x² + y² = r²      (1)

б) Если r² — нечётное целое число, то в каждой паре вида (x, y), являющейся решением уравнения (1), одно из чисел чётное, а другое — нечётное, причём количество пар, в которых первое число нечётное, равно количеству пар, в которых второе число нечётное.

в) В качестве центра такой окружности можно выбрать точку (1/3, 0).

Попробуйте изучить окружности, квадраты радиусов которых имеют вид 5^k, 5^k/4 и 5^k/9 соответственно.

а) Рассмотрим уравнение

    x² + y² = 25.          (2)

Его решениями являются двенадцать пар чисел вида (±5, 0), (0, ±5), (±3, ±4) и (±4, ±3). Нетрудно убедиться простым перебором, что других целочисленных решений данное уравнение не имеет. Следовательно, на окружности радиуса 5 с центром в начале координат лежит ровно 12 узлов клетчатой бумаги (рис. 1).

Рис. 1

б) Пусть центр окружности радиуса 5/2 расположен в точке (1/2, 0). Тогда эта окружность задаётся уравнением

Домножая обе части равенства на 4, можно перейти к такому соотношению:

    (2x – 1)² + (2y)² = 25.          (3)

Если же сделать переобозначения вида a = (2x – 1) и b = 2y, то мы придём к уравнению вида a² + b² = 25. Оно, как мы знаем из пункта а), имеет в точности 12 целочисленных решений (потому что это решения уравнения (2)), причём ровно в половине из них число a нечётное, а число b — чётное. Значит, уравнение (3) обладает в точности шестью целочисленными решениями. А именно, ему удовлетворяют следующие пары чисел: (3, 0), (–2, 0), (2, ±2) и (–1, ±2). Таким образом, на окружности радиуса 5/2 с центром в точке (1/2, 0) лежит ровно 6 узлов клетчатой бумаги (рис. 2).

Рис. 2

в) Внимательный читатель наверняка заметил, что решение пункта б), по существу, вытекало из пункта а). Более того, можно было рассмотреть задачу в более общем виде и доказать такое утверждение: если на окружности радиуса r, центр которой находится в начале координат, лежит 4n узлов клетчатой бумаги и число r² — нечётное, то на окружности радиуса r/2 с центром в точке (1/2, 0) расположено 2n узлов. Ниже на примере нашей задачи мы покажем, как подобным методом получить окружность, на которой лежит ровно n узлов.

Для начала рассмотрим окружность с центром в начале координат, радиус которой равен 25. Эта окружность задаётся уравнением

    x² + y² = 625,          (4)

которому, как нетрудно проверить, удовлетворяют двадцать пар целочисленных решений: (±25, 0), (0, ±25), (±7, ±24), (±24, ±7), (±15, ±20) и (±20, ±15). То есть на этой окружности находится ровно 20 узлов клетчатой бумаги.

Теперь рассмотрим окружность радиуса 25/3, центром которой является точка (1/3, 0). Задающее её уравнение имеет вид

что после соответствующих преобразований превращается в соотношение

    (3x – 1)² + (3y)² = 625.          (5)

Как и в пункте б), сделав замену a = (3x – 1), b = 3y, мы получим уравнение a² + b² = 625, решения которого нам известны. Осталось понять, какие из них нам подходят, а какие — нет. Но это оказывается довольно просто: если c делится на 3, то из каждой четвёрки решений вида (c, d), (c, –d), (d, c), (–d, c) подходит ровно одно. В нашем случае, это (–8, 0), (–2, ±8), (7, ±5). И таким образом, на окружности, которая задана уравнением (5), лежит ровно 5 узлов клетчатой бумаги (рис. 3).

Рис. 3

Замечание. Глядя на пять красных точек, изображённых на рис. 3, читатель может подумать, что если последовательно соединить их друг с другом, получится правильный пятиугольник. Однако это не так: у этого пятиугольника между собой равны только три стороны, а две другие немножко меньше. В действительности на клетчатой бумаге расположить правильный пятиугольник нельзя. Как и любой другой правильный многоугольник, за исключением квадрата.

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

Ключевым моментом решения проблемы является следующая лемма.

Лемма. Уравнение x² + y² = 5^k имеет ровно 4(k + 1) целочисленных решений для любого целого неотрицательного k.

(На самом деле представленная лемма является частным случаем более общего факта. Именно, пусть r(n) обозначает число всевозможных способов представления натурального n в виде суммы квадратов пары целых чисел. Тогда можно доказать, что r(n) = d₁(n) – d₃(n), где d₁(n) и d₃(n) — числа, отвечающие количеству делителей n вида (4k + 1) и (4k + 3) соответственно.)

Для доказательства мы проверяем сначала, что утверждение леммы справедливо при k = 0 и k = 1. В самом деле, уравнение x² + y² = 1 имеет четыре целочисленных решения: (0, ±1) и (±1, 0). А уравнение x² + y² = 5 обладает ровно восемью корнями: (±2, ±1) и (±1, ±2).

Потом в дело вступает принцип математической индукции. С его помощью можно доказать, что при всех целых k > 1 уравнение x² + y² = 5^k имеет ровно восемь таких решений (x, y), что x и y не делятся на 5. Точно так же, как и корни уравнения x² + y² = 5, эти восемь пар чисел получаются друг из друга перестановкой x и y и изменениями знаков. А вместе с 4(k – 1) парами вида (5a, 5b), где (a, b) — решения уравнения a² + b² = 5^k–2, они дают нам в точности 4(k + 1) решений исходного уравнения.

Теперь, вооружившись леммой, мы легко сможем дать ответ на поставленный вопрос. Из соображений симметрии ясно, что если расположить центр окружности в узле клетчатой бумаги (например, в начале координат), то количество лежащих на ней узлов будет делиться на четыре. А из леммы сразу вытекает, что если квадрат радиуса такой окружности равен 5^k, то на этой окружности лежит ровно 4(k + 1) узлов. В частности, на окружности x² + y² = 25 расположено ровно 12 узлов клетчатой бумаги.

В качестве примера окружности, на которой лежит произвольное наперёд заданное чётное число узлов клетчатой бумаги, мы можем взять окружность, заданную уравнением:

              (6)

Чтобы убедиться в том, что она годится (то есть что на ней лежит 2(k + 1) узлов), достаточно повторить рассуждения из решения пункта б) и применить лемму. Если же хочется провести окружность через нечётное число узлов, то можно взять такую:

              (7)

Используя лемму и свойства делимости на 3, можно доказать, что на ней лежит ровно (2k + 1) узлов, а выбирая подходящее k, это количество можно сделать любым наперёд заданным нечётным числом.

Окружности, которые задаются уравнениями (6) и (7), называются окружностями Шинцеля, по имени польского математика Анджея Шинцеля (Andrzej Schinzel). Отметим, что для данного натурального числа n эти уравнения задают, вообще говоря, не самую маленькую окружность с n узлами клетчатой бумаги на ней. Например, так происходит с n = 1 (очевидно, можно предъявить окружность сколь угодно маленького радиуса) или с n = 4 (здесь ясно, что существует окружность радиуса 1/√2. Менее тривиальный пример: n = 9. Соответствующая окружность Шинцеля имеет радиус 625/3, однако на окружности с центром (1/3, 0) и радиусом 65/3 также лежит ровно 9 узлов клетчатой бумаги.

Рис. 4

Существуют также и менее тривиальные комбинации точек. Так, на рис. 4 изображена окружность с центром в точке (1/5, 2/5) и радиусом  — на ней лежат четыре узла клетчатой бумаги: (–6, –2), (1, 7), (5, 5) и (2, –6). А на окружности с центром в точке (1/7, 2/7) и радиусом  находятся пять узлов: (–12, –4), (–7, 11), (4, –12), (10, –8) и (13, 1) (рис. 5).

Рис. 5

Описание множества окружностей, которые проходят ровно через n узлов клетчатой бумаги для заданного натурального числа n, — пока нерешённая задача. Предполагается, что окружность, проходящая более чем через три узла, — достаточно редкое явление, то есть если провести окружность через три случайно выбранных узла клетчатой бумаги, то через четвёртый она пройдёт с малой вероятностью.

Рис. 6

С этой задачей также связан вопрос об изображении круга на экране монитора. Будем считать, что экран представляет собой прямоугольный лист клетчатой бумаги, а круг на экране — объединение тех клеточек (пикселей), которые пересекаются со внутренностью круга. Тогда вопрос заключается в том, сколько различных изображений на экране имеет круг данного радиуса. Например, на рис. 6 представлено три различных изображения круга радиуса 4/5 (сторона клеточки, соответственно, равна единице). Полного ответа на этот вопрос пока тоже нет.

При подготовке данной публикации использовалась статья В. Вавилова и А. Устинова Окружности на решетках («Квант» №6, 2006), в которой обсуждаются некоторые свойства целочисленных решеток и расположение окружностей на них.