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

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

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

Всего векторов.

Фигура составленная из векторов обязана быть замкнутой и выпуклой.

1.

Замкнутость: Сумма векторов сторон должна быть нулевой:

2.

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

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

Разделим полученные векторы на

Заметим, что у любого из данных векторов одна компоненты четна, вторая нечетна. Условие замкнутости поделим на получим:

что не возможно при нечетном Для все четных построим искомый выпуклый многоугольник. Если делится на то возьмем векторы с неотрицательными координатами, кроме “выстроим” их по возрастанию угла, это построит четверть фигуры, затем из четырех таких частей получим всю фигуру.

Если не делит на построение такое: аналогично первому пункту встроим вектора, используя в начале Затем отразим все векторы, кроме относительно прямой а затем всю фигуру отразим относительно верхней границы.

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

Пусть стороны данного параллелепипеда не параллельны осям, тогда они имеют длины вида откуда

Пусть не делятся на тогда из

получаем противоречие с малой теоремой Ферма. Поделим тождество на получим

аналогично заключаем, что делятся на

— противоречие.

Докажем сначала, что на окружности с центром не может лежать более одной целочисленной точки. Если и — целые числа, то

где Поэтому из равенства

следует, что По теореме Виета сумма корней уравнения равна поэтому лишь один корень может быть целочисленным. Расположим теперь радиусы окружностей с центром проходящих через целочисленные точки, в порядке возрастания: Если то внутри окружности радиуса с центром лежит ровно целочисленных точек.

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

Пусть покажем, что точку с координатами видно из центра. Пусть это не так, тогда существует точка такая, что где — расстояние от точки до прямой

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

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

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

Остаётся проверить, что совпадает с площадью Если многоугольник разрезан на части и с вершинами в узлах решётки, то так как углы в узлах складываются. Следовательно, если формула верна для и она верна и для

Рассмотрим прямоугольник со сторонами и параллельными осям решётки. Внутренних узлов: граничных узлов: Тогда:

Формула верна для прямоугольников. Разрежем прямоугольник диагональю на два треугольника. Для каждого треугольника что совпадает с его площадью.

Любой многоугольник можно триангулировать непересекающимися диагоналями. Поскольку формула аддитивна и верна для треугольников, она верна и для всего многоугольника. Таким образом,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Без ограничения общности будем считать, что в трехмерный шар вписывается куб с ребром единичной длины. Разобьем каждое ребро на равных частей и построим кубическую решетку, в которой узлов. Расстояние между двумя любыми узлами не менее Рассмотрим образ этой решетки при отображении. Расстояние между двумя любыми точками из образа должно быть так же не меньше

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

По принципу Дирихле среди точек с целыми координатами найдутся такие две точки и что и Тогда точки

имеют целые координаты и лежат на одном отрезке между точками и