Эта задача навеяна рядом известных задач Гуго Штейнгауза.

Конкурсная задача №83 (8 баллов)

Плоскость разлинована в клеточку (одна клетка - квадрат со стороной 1). Найти минимальный радиус окружности, проходящей через:
1) ровно 3 узла решетки;
2) ровно 6 узлов решетки;
3) ровно 12 узлов решетки;
4) ровно 16 узлов решетки;
5) по крайней мере 2008 узлов решетки.

Примечание:
Пункт 5 появился с «на злобу дня». На данный момент я не умею строго доказывать минимальность радиуса для этого пункта. Соответственно, строгое обоснование минимальности в этом пункте будет оцениваться дополнительными призовыми баллами, сверх тех восьми, что заявлены в цене задачи.

Решение

Ясно, что центр окружности, проходящей, по крайней мере, через три целочисленных узла, имеет рациональные координаты (как решение системы линейных уравнений с рациональными коэффициентами).
Не нарушая общности, можно считать, что этот центр С(x;y), где 0 ≤ x,y ≤ 1/2.

Влад Франк предложил универсальный способ нахождения окружности минимального радиуса, проходящей через заданное число узлов (для 2008, этот метод, к сожалению, работает лишь теоретически):
1) найти какую-либо окружность радиуса R, проходящую через нужное число узлов;
2) найти описанные окружности для всевозможных треугольников с вершинами в узлах, лежащие в окружности радиуса R+1, концентрической исходной. Одной из них обязательно будет скомая окружность минимального радиуса.

Разумеется, для конкретного числа узлов возможны строгие обоснования минимальности, требующие меньшего перебора.

1. R = 5/6 * sqrt(2).
Например, окружность (x-1/6)² + (y-1/6)² = 25/18 проходит через узлы (1; 1), (-1; 0) и (0; -1).

2. R = 5/2.
Ясно, что центр выгодно поместить в точку, одна из координат которой - целое число, а другая - полуцелое. Тогда достаточно подобрать рациональный радиус (это обеспечит два узла), квадрат которого представим в виде суммы квадратов целого и полуцелого положительных чисел (это даст еще четыре узла). Подходящей окружностью будет (x-1/2)² + y² = 25/4. Она проходит через целочисленные узлы (3; 0), (-2; 0), (2; 2), (-1; 2), (2; -2), (-1, -2).
Минимальность можно обосновать перебором. Но, по сути, она очевидна в силу минимальности пифагоровой тройки (3, 4, 5), на базе которой сконструирована наша окружность. Несимметричные же варианты заведомо приводят к бОльшим радиусам.

3. R = 5/sqrt(2).
Взяв центр с целыми (полуцелыми) координатами и R², представимое в виде суммы суммы различных целых (полуцелых) квадратов, получим окружность, проходящую через восемь узлов (за счет вариации знаков и транспозиции x и y). Еще четыре узла можно получить, взяв в в качестве R² полный квадрат (этот способ годится только для целых кооординат), или взяв R², являющееся удвоенным квадратом.
Первый способ приводит к минимальному R = 5: окружность x² + y² = 25 проходит через 12 узлов (восемь получены модификацией узла (3; 4), а еще четыре модификацией узла (5; 0)).
Второй способ приводит к окружности (x-1/2)² + (y-1/2)² = 25/2, радиус которой в sqrt(2) раз меньше.
Вот двенадцать узлов, через которые проходит вторая окружность:
(4; 0), (-3; 0), (4; 1), (-3; 1), (3; 3), (-2; 3), (3; -2), (-2; -2), (1; 4), (0; 4), (1; -3), (0; -3).

4. R = sqrt(65/2).
Для этого пункта достаточно взять (2R)², допускающее два существенно различных представления в виде суммы квадратов различных нечетных чисел. Наименьшим таким числом будет 130 = 3² + 11² = 7² + 9². На окружности x² + y² = 130 будет лежать 16 узлов решетки: (3; 11), (7; 9) и еще четырнадцать точек полученных из данных вариацией знаков и транспозицией x и y.
Перенося центр в точку с полуцелыми кооординатами, можно уменьшить радиус вдвое. Вот пример уравнения окружности, проходящей через 16 узлов решетки: (x-1/2)² + (y-1/2)² = 65/2

5. R = 5*sqrt(5*13*17*29*37*41*53*61/2)
Пусть a = p_1^s_1 * p_2^s_2 *…* p_k^s_k, где все p_i - простые числа вида 4m+1. Тогда количество целочисленных решений уравнения x² + y² = a равно b = 4*(s_1 + 1)*(s_2 + 1)*…*(s_k + 1) (см. любой учебник по теории чисел). Уравнение x² + y² = 2*a имеет столько же решений. Но все подходящие иксы и игреки нечетны, что позволяет нам, сместить центр в точку с полуцелыми координатами и уполовинить радиус.
Остается подобрать p_i и s_i так, чтобы b было не меньше 2008 при как можно меньшем a. Легко убедиться, что наименьшее такое a получается при b = 2048 и равно 5^3*13*17*29*37*41*53*61.
Окружность (x-1/2)² + (y-1/2)² = 5^3*13*17*29*37*41*53*61/2 проходит через 2048 узлов целочисленной решетки.

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

Обсуждение

Олег Полубасов получил следующую последовательность наискорейшего роста количества целых точек на окружности в зависимости от радиуса: N = 2, 4R² = 1
N = 4, 4R² = 2
N = 8, 4R² = 2 * 5 = 10
N = 12, 4R² = 2 * 25 = 50
N = 16, 4R² = 2 * 5 * 13 = 130
N = 24, 4R² = 2 * 25 * 13 = 650
N = 32, 4R² = 2 * 5 * 13 * 17 = 2210
N = 36, 4R² = 2 * 25 * 169 = 8450
N = 48, 4R² = 2 * 25 * 13 * 17 = 11050
N = 64, 4R² = 2 * 125 * 13 * 17 = 55250
N = 72, 4R² = 2 * 25 * 169 * 17 = 143650
N = 80, 4R² = 2 * 625 * 13 * 17 = 276250
N = 96, 4R² = 2 * 125 * 169 * 17 = 718250
N = 128, 4R² = 2 * 125 * 13 * 17 * 29 = 1602250
N = 144, 4R² = 2 * 25 * 169 * 17 * 29 = 4165850
N = 160, 4R² = 2 * 625 * 13 * 17 * 29 = 8011250
N = 192, 4R² = 2 * 125 * 169 * 17 * 29 = 20829250
N = 256, 4R² = 2 * 125 * 13 * 17 * 29 * 37 = 59283250
N = 288, 4R² = 2 * 25 * 169 * 17 * 29 * 37 = 154136450
N = 320, 4R² = 2 * 625 * 13 * 17 * 29 * 37 = 296416250
N = 384, 4R² = 2 * 125 * 169 * 17 * 29 * 37 = 770682250
N = 512, 4R² = 2 * 125 * 13 * 17 * 29 * 37 * 41 = 2430613250
N = 576, 4R² = 2 * 25 * 169 * 17 * 29 * 37 * 41 = 6319594450
N = 640, 4R² = 2 * 625 * 13 * 17 * 29 * 37 * 41 = 12153066250
N = 768, 4R² = 2 * 125 * 169 * 17 * 29 * 37 * 41 = 31597972250
N = 864, 4R² = 2 * 25 * 169 * 289 * 29 * 37 * 41 = 107433105650
N = 1024, 4R² = 2 * 125 * 13 * 17 * 29 * 37 * 41 * 53 = 128822502250
N = 1152, 4R² = 2 * 25 * 169 * 17 * 29 * 37 * 41 * 53 = 334938505850
N = 1280, 4R² = 2 * 625 * 13 * 17 * 29 * 37 * 41 * 53 = 644112511250
N = 1536, 4R² = 2 * 125 * 169 * 17 * 29 * 37 * 41 * 53 = 1674692529250
N = 1728, 4R² = 2 * 25 * 169 * 289 * 29 * 37 * 41 * 53 = 5693954599450
N = 2048, 4R² = 2 * 125 * 13 * 17 * 29 * 37 * 41 * 53 * 61 = 7858172637250.

Задача допускает целый ряд естественых обобщений, но я буду приводить их, поскольку планирую вернуться к обсуждаемой ситуации в одной из следующих задач Марафона.

Награды

За правильное решение задачи 83 Владислав Франк, Олег Полубасов и Анатолий Казмерчук получают по 8 призовых баллов. За неполное решение задачи Галина Крюкова получает 5 призовых баллов, а Николай Дерюгин - 4 балла.

Эстетическая оценка задачи - 5 баллов

---