Клетчатая решётка (координатная плоскость) и точки, отрезки, прямые на ней

Перенесём треугольник одной вершиной в начало координат. Тогда его можно представлять как точку , из которой выходят вектора и .

Тогда внутренность треугольника можно представить как где — действительные числа, и

Вопрос о целых точках на треугольнике, получается, стоит так: при каких целых система:

имеет решения , удовлетворяющие условиям выше.

Мы выделили внутренность, потому что стороны легче рассмотреть отдельно. Три целочисленные вершины лежат в треугольнике по определению. На сторонах точки подсчитать тоже просто — стороны это вектора и третья сторона . Получить целочисленную точку можно только на середине вектора , а у остальных сторон нет общих делителей координат, и через целые точки они не проходят. Значит, на периметре лежат точки.

Переходим к внутренней части треугольника. Конечно, нет гарантий, что там будет хотя бы одна целочисленная точка — но если такая есть, то её проекции на координатные плоскости тоже будут целочисленные. Поэтому давайте рассмотрим проекцию треугольника на плоскость , и отберём на ней потенциально подходящие пары а после выкинем лишние.

Проецируем треугольник на — получается треугольник на плоскости с вершинами Внутрь него точки попадут такие:

Решаем систему, состоящую из двух первых уравнений:

Получаем следующие решения:

Полученные значения подставляются в третье уравнение , и если оказывается целым — точка найдена. После подстановки получается выражение:

то есть должна быть чётной. Из кандидатов подойдут только .

Плюс точки на сторонах, и всего точек на треугольнике

Раскрасим узлы в 10 цветов так, чтобы узлы одного цвета образовывали сетку из квадратов со стороной . Например, пусть цвет узла с координатами ( ) определяется остатком от деления числа на 10 (считаем, что деревья растут в центрах квадратов):

По принципу Дирихле, в какой-то из десяти цветов окрасились более 100 тысяч ёлок. Тогда все эти ёлки можно срубить, поскольку расстояние между любыми двумя из них не меньше .

Запишем исходное условие на координаты точек и в виде

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

соответственно. Найдём подходящие значения параметра

Стороны и параллелограмма лежат на прямых

поэтому они параллельны прямым, на которых лежат точки и Эти прямые пересекают параллелограмм при

Выясним количество точек с целочисленными координатами на каждой из прямых вида

Рассмотрим несколько вариантов:

Если кратно трём (т.е. то получаем прямую

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

При любом этому неравенству удовлетворяет целых значений

Если не делится на 3, т.е. при где имеем

Учитывая, что получаем

Значит, этому неравенству удовлетворяет целочисленных значений.

Если (таких значений то на каждой из двух прямых

можно выбрать по точек — всего пар.

Если (таких значений то на каждой из двух прямых можно выбрать по точек — имеем пар.

Итого получаем

Первое решение.

Разобьём плоскость на единичные квадраты линиями целочисленной решетки. Проведем прямую через начало координат и точку Поскольку она имеет рациональный угловой коэффициент и проходит через какой-то узел решетки. Точка вида — это любая рациональная точка этой прямой. Проведем прямую через такую точку и левый нижний угол той клетки, в которую попала эта точка. Угловой коэффициент этой прямой равен как раз

Совместим между собой все единичные квадраты, в которых есть точки прямой В полученном квадрате прямая отобразится конечным количество отрезков, параллельных исходной прямой.

Предположим, что и одного знака. Тогда полученные отрезки имеют положительный угловой коэффициент. Один из них выходит из левого нижнего узла квадрата. Ясно, что из этого узла можно провести луч с положительным рациональным коэффициентом который пересечет верхнюю или нижнюю сторону квадрата, не встретив по дороге точек ни одного из наших отрезков. Это число нельзя представить в нужном виде.

Пусть, наоборот, числа и разного знака. Тогда наши отрезки имеют отрицательный угловой коэффициент. Один из них выходит из левого верхнего узла квадрата. Несложно понять, что один из этих отрезков соединяет точку на левой стороне квадрата с точкой на его нижней стороне. На рациональных точках этого отрезка реализуются все возможные положительные рациональные угловые коэффициенты!

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение.

Так как в качестве можно взять любое положительное рациональное число, можно считать, что числа и целые. В этом случае замена числа на его дробную часть не изменит отношения значит, можно дополнительно считать, что Наконец, замена r на соответствует смене знаков чисел и поскольку

Таким образом, достаточно рассмотреть лишь случай, когда — натуральное число.
Пусть также является натуральным числом. Покажем, что уравнение

не имеет решений относительно Домножив на знаменатели и выразив дробную часть через целую, получим уравнение

или, что то же самое,

Но это уравнение не может иметь решений, поскольку левая часть положительна и меньше а правая часть целая. Следовательно, если числа и одного знака, то требуемое не найдётся.
Пусть является отрицательным целым числом. Достаточно показать, что уравнение

для любых натуральных чисел и имеет вещественное решение Тогда

и, значит, является решением линейного уравнения

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

При правая часть равна нулю и поэтому меньше левой. А при близких к обе дробные части также будут близки к поэтому правая часть будет близка к и, в частности, будет больше левой. Следовательно, при некотором промежуточном правая часть будет равна левой. Поэтому если числа и разных знаков, то требуемое обязательно найдётся.

Пусть — данный прямоугольник. Без ограничения общности можно считать, что — начало координат: иначе сместим начало координат в точку а в конце сделаем сдвиг на целочисленный вектор Обозначим векторы где , — целые числа. Поскольку и взаимно перпендикулярны, их скалярное произведение равно нулю, т.е. (этот факт также следует из соотношения для угловых коэффициентов перпендикулярных прямых и ).

Рассмотрим сначала случай, когда и не взаимно просты. Тогда НОД( В этом случае рассмотрим на стороне промежуточные точки где Проведём через точки прямые, параллельные стороне Они пересекут сторону в точках где

Таким образом, точки и имеют целочисленные координаты и тем самым, прямые разбивают прямоугольник на прямоугольников с целочисленными вершинами. Назовем это разбиением первого типа.

Аналогично, если и не взаимно просты, то прямыми, параллельными стороне разобьем на меньшие прямоугольники с целочисленными вершинами. Назовем это разбиением второго типа; прямые этого разбиения проходят через промежуточные точки на стороне где а — наибольший общий делитель и Заметим, что в случае, когда одновременно и прямые первого и второго разбиений разбивают прямоугольник на равных прямоугольников с вершинами в точках где т.е. все вершины имеют целочисленные координаты.

Итак, приходим к случаю, когда координаты каждого из векторов взаимно просты. Но тогда из равенства получим, что (действительно, из этого равенства следует, что делится на и, в то же время, делится на значит, аналогично, с учетом знака в данном равенстве). В этом случае стороны прямоугольника равны: и наш прямоугольник квадрат.

Докажем, что каждая из рассматриваемых величин равна площади многоугольника Проверим это для суммы длин горизонтальных отрезков. Проведём эти отрезки. Тогда разобьётся на два треугольника и несколько трапеций, причём высоты этих фигур будут равны Осталось выразить площади этих фигур через основания и высоты по известной формуле и сложить. Видно, что каждый горизонтальный отрезок войдёт в сумму два раза, то есть с коэффициентом единица, что и требовалось.

Заметим, что какая-то прямая пересекает прямоугольник хотя бы по двум точкам. Тогда угловой коэффициент всех прямых рационален. Не нарушая общности, можно считать, что он положителен (иначе можно просто сделать симметрию относительно оси ординат). Пусть он равен где — натуральные числа, и Обозначим через количество прямых из нашего множества, которые пересекают прямоугольник ровно по целым точкам. Тогда нам известно, что Мы знаем, что Заметим, что если прямая проходит через целых точек прямоугольника, то она проходит ровно через пару соседних целых точек прямоугольника (то есть точек таких, что , ). Заметим, что всего таких пар точек в нашем прямоугольнике ровно (можно считать, что меньшая сторона прямоугольника параллельна оси ординат). Но с другой стороны из нашего наблюдения следует, что их ровно Тогда имеем равенства

вычитая равенства, получаем, что

откуда причем и Тогда возможны варианты или Тогда либо или По аналогичным соображениям мы знаем, что количество прямых в удачном множестве, перпендикулярном данному, равно Тогда в множестве может быть либо прямых, либо прямых.

Прямая образует с одной из осей координат угол, не превосходящий поскольку сумма углов между прямой и осями координат равна Пусть для определённости угол с осью абцисс не превосходит обозначим его через Нарисуем сетку, образованную прямыми и при всех целых Она разбивает плоскость на единичные квадратики. Рассмотрим квадратик, который пересекает прямая Тогда она пересекает одну из горизонтальных сторон. Их точка пересечения делит сторону на две части. Рассмотрим меньшую из них, соответствующую ей вершину квадратика обозначим через

Тогда Расстояние от точки до прямой равно длине перпендикуляра, опущенного из точки на значит, оно равно

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