===== №83 ===== Эта задача навеяна рядом известных задач Гуго Штейнгауза. **Конкурсная задача №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)2 + (y-1/6)2 = 25/18 проходит через узлы (1; 1), (-1; 0) и (0; -1). 2. R = 5/2.\\ Ясно, что центр выгодно поместить в точку, одна из координат которой - целое число, а другая - полуцелое. Тогда достаточно подобрать рациональный радиус (это обеспечит два узла), квадрат которого представим в виде суммы квадратов целого и полуцелого положительных чисел (это даст еще четыре узла). Подходящей окружностью будет (x-1/2)2 + y2 = 25/4. Она проходит через целочисленные узлы (3; 0), (-2; 0), (2; 2), (-1; 2), (2; -2), (-1, -2).\\ Минимальность можно обосновать перебором. Но, по сути, она очевидна в силу минимальности пифагоровой тройки (3, 4, 5), на базе которой сконструирована наша окружность. Несимметричные же варианты заведомо приводят к бОльшим радиусам. 3. R = 5/sqrt(2).\\ Взяв центр с целыми (полуцелыми) координатами и R2, представимое в виде суммы суммы различных целых (полуцелых) квадратов, получим окружность, проходящую через восемь узлов (за счет вариации знаков и транспозиции x и y). Еще четыре узла можно получить, взяв в в качестве R2 полный квадрат (этот способ годится только для целых кооординат), или взяв R2, являющееся удвоенным квадратом.\\ Первый способ приводит к минимальному R = 5: окружность x2 + y2 = 25 проходит через 12 узлов (восемь получены модификацией узла (3; 4), а еще четыре модификацией узла (5; 0)).\\ Второй способ приводит к окружности (x-1/2)2 + (y-1/2)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)2, допускающее два существенно различных представления в виде суммы квадратов различных нечетных чисел. Наименьшим таким числом будет 130 = 32 + 112 = 72 + 92. На окружности x2 + y2 = 130 будет лежать 16 узлов решетки: (3; 11), (7; 9) и еще четырнадцать точек полученных из данных вариацией знаков и транспозицией x и y.\\ Перенося центр в точку с полуцелыми кооординатами, можно уменьшить радиус вдвое. Вот пример уравнения окружности, проходящей через 16 узлов решетки: (x-1/2)2 + (y-1/2)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. Тогда количество целочисленных решений уравнения x2 + y2 = a равно b = 4*(s_1 + 1)*(s_2 + 1)*...*(s_k + 1) (см. любой учебник по теории чисел). Уравнение x2 + y2 = 2*a имеет столько же решений. Но все подходящие иксы и игреки нечетны, что позволяет нам, сместить центр в точку с полуцелыми координатами и уполовинить радиус.\\ Остается подобрать p_i и s_i так, чтобы b было не меньше 2008 при как можно меньшем a. Легко убедиться, что наименьшее такое a получается при b = 2048 и равно 5^3*13*17*29*37*41*53*61.\\ Окружность (x-1/2)2 + (y-1/2)2 = 5^3*13*17*29*37*41*53*61/2 проходит через 2048 узлов целочисленной решетки. В пользу минимальности полученного радиуса говорят следующие убедительные (но не абсолютно строгие) соображения: возможное уменьшение радиуса за счет смещения центра в точку, координаты которой не будут ни целыми, ни полуцелыми, будет менее существенным, чем его увеличение, вызванное уменьшением числа симметрий при таком расположении центра. ** Обсуждение ** Олег Полубасов получил следующую последовательность наискорейшего роста количества целых точек на окружности в зависимости от радиуса: N = 2, 4R2 = 1\\ N = 4, 4R2 = 2\\ N = 8, 4R2 = 2 * 5 = 10\\ N = 12, 4R2 = 2 * 25 = 50\\ N = 16, 4R2 = 2 * 5 * 13 = 130\\ N = 24, 4R2 = 2 * 25 * 13 = 650\\ N = 32, 4R2 = 2 * 5 * 13 * 17 = 2210\\ N = 36, 4R2 = 2 * 25 * 169 = 8450\\ N = 48, 4R2 = 2 * 25 * 13 * 17 = 11050\\ N = 64, 4R2 = 2 * 125 * 13 * 17 = 55250\\ N = 72, 4R2 = 2 * 25 * 169 * 17 = 143650\\ N = 80, 4R2 = 2 * 625 * 13 * 17 = 276250\\ N = 96, 4R2 = 2 * 125 * 169 * 17 = 718250\\ N = 128, 4R2 = 2 * 125 * 13 * 17 * 29 = 1602250\\ N = 144, 4R2 = 2 * 25 * 169 * 17 * 29 = 4165850\\ N = 160, 4R2 = 2 * 625 * 13 * 17 * 29 = 8011250\\ N = 192, 4R2 = 2 * 125 * 169 * 17 * 29 = 20829250\\ N = 256, 4R2 = 2 * 125 * 13 * 17 * 29 * 37 = 59283250\\ N = 288, 4R2 = 2 * 25 * 169 * 17 * 29 * 37 = 154136450\\ N = 320, 4R2 = 2 * 625 * 13 * 17 * 29 * 37 = 296416250\\ N = 384, 4R2 = 2 * 125 * 169 * 17 * 29 * 37 = 770682250\\ N = 512, 4R2 = 2 * 125 * 13 * 17 * 29 * 37 * 41 = 2430613250\\ N = 576, 4R2 = 2 * 25 * 169 * 17 * 29 * 37 * 41 = 6319594450\\ N = 640, 4R2 = 2 * 625 * 13 * 17 * 29 * 37 * 41 = 12153066250\\ N = 768, 4R2 = 2 * 125 * 169 * 17 * 29 * 37 * 41 = 31597972250\\ N = 864, 4R2 = 2 * 25 * 169 * 289 * 29 * 37 * 41 = 107433105650\\ N = 1024, 4R2 = 2 * 125 * 13 * 17 * 29 * 37 * 41 * 53 = 128822502250\\ N = 1152, 4R2 = 2 * 25 * 169 * 17 * 29 * 37 * 41 * 53 = 334938505850\\ N = 1280, 4R2 = 2 * 625 * 13 * 17 * 29 * 37 * 41 * 53 = 644112511250\\ N = 1536, 4R2 = 2 * 125 * 169 * 17 * 29 * 37 * 41 * 53 = 1674692529250\\ N = 1728, 4R2 = 2 * 25 * 169 * 289 * 29 * 37 * 41 * 53 = 5693954599450\\ N = 2048, 4R2 = 2 * 125 * 13 * 17 * 29 * 37 * 41 * 53 * 61 = 7858172637250. Задача допускает целый ряд естественых обобщений, но я буду приводить их, поскольку планирую вернуться к обсуждаемой ситуации в одной из следующих задач Марафона. ** Награды ** За правильное решение задачи 83 Владислав Франк, Олег Полубасов и Анатолий Казмерчук получают по 8 призовых баллов. За неполное решение задачи Галина Крюкова получает 5 призовых баллов, а Николай Дерюгин - 4 балла. ** Эстетическая оценка задачи - 5 баллов ** ----