![]() |
![]() |
|
![]() | ![]() |
Целые числа и решетки.Вот две задачи.
1. Даны два взаимно простых целых числа
2. В плоской квадратной решетке через два узла проведена прямая. Найти узлы, которые находятся на минимальном (не равном нулю) расстоянии от этой прямой. Это разные формулировки одной и той же задачи. Прежде чем читать дальше попробуйте сами разобраться в этом и найти решение задачи. Эквивалентность задач. В решетке можно ввести различные системы координат, каждая из которых определяется элементарной ячейкой в виде параллелограмма, внутри которого нет ни одного узла. Из очевидных соображений следует, что все типы элементарных ячеек имеют одинаковую площадь.
Введем прямоугольную систему координат, в которой элементарной ячейкой является квадрат (это возможно, так как решетка квадратная). Пусть сторона квадрата будет единицей меры расстояний. Не ограничивая общность, будем считать, что два узла, через которые проходит прямая, являются соседними на этой прямой. Перенесем начало координат в один из этих узлов. Координаты второго узла зададим вектором
Т.е. Расстояние от искомого узла до прямой равно
Здесь S - площадь параллелограмма, построенного на векторах
Величина a фиксированная. Поэтому минимум S приводит к минимуму R . Минимальность R означает, что внутри нашего параллелограмма нет ни одного узла и он может служить элементарной ячейкой. Его площадь равна площади элементарного квадрата и значит минимум S должен быть равен единице. В результате приходим к уравнению (1). Попутно мы показали, что это уравнение имеет решение. Решение задачи. Решить уравнение (1) можно, используя некоторые теоремы из теории неп- рерывных дробей. Мы приведем развернутое решение, которое будет понят- но и человеку незнакомому с этой теорией. Достаточно иметь представление о целой части и остатке результата деления одного числа на другое. Не ограничивая общность, положим
При других вариантах решение получается соответствующей заменой знаков и индексов у Однозначно определяется следующая цепочка разложений (все вводимые ниже числа являются целыми и положительными):
где
Методом математической индукции нетрудно доказать, что
В силу (6) при каком-то k = n получим
Т.е. b1 = An , b2 = Dn (10) является решением уравнения (1). Нетрудно показать, что множество пар вида
где k - любое целое число, составляет полный набор решений уравнения (1). При этом (10) выделяется тем, что приводит к минимуму модуля вектора b. .Более того, можно доказать, что
при всех целых k. Равенство в (12) будет лишь при Обобщения. Геометрическая интерпретация дает больший простор для модификаций и обобщений задачи. Ниже приведен ряд возможных вариантов.
![]() Доказательство этого другими методами будет довольно сложным. Однако, следует подчеркнуть, что простота геометрического доказательства обязана тому, что в нем неявно используется предельный переход. Найдите где и как. |
|