Клуб любителей пораскинуть мозгами

Окружность на листочке в клетку

Требуется нарисовать окружность на листе бумаги так, чтобы она проходила через максимальное число узлов клеток.
Например окружность с центром (2,2) и радиусом 1 проходит только через 4 такие точки: (1,2)(3,2) (2,1) (2,3).

Имеет ли такая задача конечное решение(да/нет – обосновать)?
Найти окружность, у которой это число наибольшее.
PS. Ответа не знаю. У меня пока что 12 максимум.

Ответы: 20 → “Окружность на листочке в клетку”

  1. Гипотенуза любого пифагорова треугольника даёт значение радиуса окружности, при котором будет 12 точек.
    a^2 + b^2 = c^2
    Точки:
    (0, +-c)
    (+-c, 0)
    (+-a, +-b)
    (+-b, +-a)

  2. Да, но вот 12 точек предел или нет?
    В общем виде нужно найти макс кол-во целых корней уравнения:
    (x-x0)^2+(y-y0)^2=R^2. Проблема в том, что x0 и y0 не обязаны должны быть целыми…

  3. мыслим пятимерно =) координатное пространство OR x0 y0 x y. Ищем графики функций x(R,x0,y0) и y(R,x0,y0), узнаём, где они пересекаются при одинаковых наборах аргументов, всё отлично! Надеюсь, ничего не напутал :P

  4. можно поподробнее?

  5. сходу придумал, чтоб через 16. Думаю, что если размеры листа не ограничены, то можно сделать, чтоб проходил через более чем дохрена точек :)

  6. пример в студию)

  7. Короче вся задача сводится к нахождению всех натуральных решений
    a^2+b^2=c^2. Причем чтоб каждое из них нельзя было получить умножением a,b и c на N.(3^2+4^2=5^2 и6^2+8^2=10^2 по сути одно и то же).Насколько я знаю таких решений бесконечное множество. так вот R – это наименьшее общее кратное всех с.
    (Все что я тут написал касается только случая, когда центр окружности тоже в узле).
    Так что я считаю, что конечное решение может быть только на конечной площади. :))

  8. пример
    0^2+1^2=1^2
    3^2+4^2=5^2
    5^2+12^2=13^2
    r – наименьшее общее кратное из 1,5,13 = 65.
    Вот. Окружность с радиусом 65, центр которой в узле проходит минимум через 20 узлов.
    Понаходить еще решений – будет еще :))
    (Сорри что много буков :)) )

  9. 28^2+96^2=100^2и тд и тп. :))

  10. #8, "Насколько я знаю" – не аргумент. Надо хоть как то доказать, обосновать…
    Приводить центр в (0,0) не всегда можно. Вдруг будет супер пупер решение, у которого центр будет где нибудь в (2П*cos(1), 2П*sin(1))? Я конечно утрирую, но все же

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

  12. ну выпишите хотя бы эти 15 или сколько у вас там получилось? по моему все те же 12 получается

  13. для радиуса 1105 – 28 узлов.
    для 27625 – 36.
    Что выписать? координаты?
    ну для радиуса 65 – 20 узлов может и выпишу если надо. больше – нет уж :))

  14. Поподробнее…
    Трудно представить пятимерное пространство, но на определённом уровне абстракции это всё же возможно.
    Координатные оси: OR, Ox, Oy, Ox0, Oy0. Всё это переменные.
    Пусть имеется функция y(x,x0,y0,R) – она описывает множество окуржностей. Для каждого фиксированного набора (x0, y0, R) при переменном x получаем функцию
    y(x) = +- sqrt(R^2 – (x – x0)^2) + y0
    и, соответственно, график окружности. Затем по какому-то алгоритму надо найти число заветных точек.
    Достаточно рассматривать значения x0 [0; 1), y0[0; 1), R (0; ~)
    ~ – типа бесконечность :)

    Пример алгоритма: для каждой конкретной y(x) просмотреть все целые x и для каждого из них найти y(x)-[y(x)], где [y(x)] – целая часть значения функции.
    Таким образом, если найти зависимость числа целых точек от параметров окружности (x0, y0, R), то можно узнать наибольшее =) Но, боюсь, это не будет плавная красивая функция, а скорее всё будет жутко скакать

  15. Другой вариант – тоже не вижу способа реализации…

    Пускай окружность радиуса R лежит (для простоты) в начале координат O.

    Нетрудно убедиться, что при увеличении радиуса в целое количество раз C, окружность радиуса C * R будет проходить через узлы клеток в точках с теми же фазами, что и окружность радиуса R. (надеюсь, что ясно выразился :P)

    (Если не очевидно – поясню: для любой точки (x; y) с целыми x, y на окружности радиуса R, справедливо:
    точка (C*x; C*y) лежит на окружности радиуса C*R, где C – целое,
    и тоже имеет целые координаты)

    Тогда получим: если существует точка окружности, имеющая нецелые рациональные координаты

    (a / b;m / n), где a, b, m, n – целые,

    то увеличение радиуса окружности в C = b * n раз приведёт к появлению точки

    (a * n; m * b),

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

    Получаем (ввиду симметрии окружности) четыре новые точки, проходящие через узел, при этом не теряя ни одной старой.

    Вывод: пока есть хоть одна точка с рациональными координатами, можно наращивать радиус и увеличивать число захваченных узлов.

  16. последнее сообщение Андрея, как мне показалось, имеет много общего с тем, что я писал до этого. Только мне кажется, что в каждом таком случае мы найдем не 4 узла, а 8. Так как помимо симметрии относительно осей есть еще симметрия относительно их биссектрис. (то есть в каждом из квадрантов (x,y) и (y,x), если конечно x<>y)

  17. Олег Кожемякин, ваще доказательство понял. Со всем согласен в полной мере. На вики подробно описаны Пифагоровы числа.

    Т.о. можно нарисовать окружность с заранее заданным минимальным числом таких точек.

    На этом думаю все! Всем спасибо)

  18. obat kutil kelamin di cirebon

    we are only limited to inform we sell genital warts, condyloma akuminata

  19. Nama Penyakit Kutil Kelamin

    Kutil kelamin adalah salah satu penyakit menular yang terjadi karena penderita melakukan hubungan seksual yang salah melalui vaginal, anal atau oral dengan orang yang terinfeksi. Kutil kelamin disebabkan oleh Human Papillomavirus (HPV). Dan penelitian…