===== №85 =====

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


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

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


** Решение **

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

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

Окружность (x-1/3)<sup>2</sup> + (y-1/3)<sup>2</sup> = 2*5<sup>2n</sup>/9 проходит ровно через 2n+1 узлов
решетки.
Доказательство этого факта практически дословно совпадает с вышеприведенным.
Множитель 2 потребовался, поскольку 5<sup>2n</sup> == 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 балла **
----