Эта задача является прямым продолжением задачи 83

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

Плоскость разлинована в клеточку (одна клека - квадрат со стороной 1). Доказать, что для любого натурального n найдется окружность, проходящая ровно через n узлов решетки.

Решение

Можно обойтись фиксированным центром и не слишком разнообразными радиусами.

Окружность (x-1/3)² + (y-1/3)² = 5^2n-1/9 проходит ровно через 2n узлов решетки. Эти узлы соответствуют решениям диофантова уравнения (3x-1)² + (3y-1)² = 5^2n-1.
Как известно, количество представлений числа 5^2n-1 в виде u² + v² равно 4[(2n-1) + 1] = 4n.
5^2n-1 == 2 (mod 3), поэтому u² == v² == 1 (mod 3). Значит, решения «ходят» четверками (u,v), (u,-v), (-u,v), (-u,-v). Но из каждой такой четверки нас устраивет всего одна пара, в которой оба числа сравнимы с единицей по модулю 3.

Окружность (x-1/3)² + (y-1/3)² = 2*5²ⁿ/9 проходит ровно через 2n+1 узлов решетки. Доказательство этого факта практически дословно совпадает с вышеприведенным. Множитель 2 потребовался, поскольку 5²ⁿ == 1 (mod 3), а нам нужна сравнимость с двойкой.

Обсуждение

Разумеется, существуют и другие серии однотипных уравнений, обеспечивающие решение задачи. Например, число 5 можно безболезненно заменить на любое простое число, сранимое с 5 по модулю 12. Центр окружностей можно перенести в точку (0; 1/2) для четного числа узлов и в точку (0; 1/3) - для нечетного. И т.д.

Олег Полубасов пишет: «Если оценивать эту задачу в изоляции от других задач, то есть если бы задачи 83 не было, тогда, конечно, задача 85 заслуживает своих баллов и наивысшей эстетической оценки, так как она красивее задачи 83. Но ведь задача 83 была, и в ходе её решения всё равно уже пришлось решить задачу 85 (по крайней мере, мне).»

Соглашусь с этим мнением. Я тоже решил задачу 85, решая задачу 83. Точнее, ее последний пункт. Он появился «на злобу дня», в последний момент и решать его мне пришлось уже после опубликования задачи 83.

С другой стороны, оценивать цадачу 85 малым числом баллов лишь на том основании, что ранне уже была опубликована задача 83, я посчитал неправильным: вдруг кто-то из нерешавших задачу 83, возьмется за 85. Как выяснилось, эта возможность так и осталась гипотетической. Но заранее я этого не знал.

Награды

За правильное решение задачи 85 Олег Полубасов и Анатолий Казмерчук получают по 8 призовых баллов.

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

---