M1722. Количество целых точек

Задача из журнала «Квант»(2000, №5)

Условие

Пусть [latex]a,b[/latex] — натуральные числа. Проведем через точку [latex](a;b)[/latex] прямую, отсекающую от первого координатного угла треугольник.
а) Докажите, что количество точек с целыми неотрицательными координатами, которые лежат внутри или на сторонах этого треугольника, больше, чем [latex]2 \cdot a \cdot b + a + b[/latex].
б) Докажите, что эта оценка точная: через точку [latex](a;b)[/latex] можно провести прямую, отсекающую от первого координатного угла треугольник, внутри и на сторонах которого всего [latex]2 \cdot a \cdot b + a + b[/latex] точек с целыми неотрицательными координатами.

Решение

Рассмотрим прямоугольник [latex]OABC[/latex] с центром в точке [latex]P(a;b)[/latex], и сторонами, параллельными осям координат(рис.1). Внутри и на сторонах этого прямоугольника всего [latex](2 \cdot a + 1) \cdot (2 \cdot b+1) = [/latex] [latex] 4\cdot a \cdot b + 2\cdot a + 2 \cdot b +1[/latex] целочисленных точек.
 
method-draw-image (8)
Pис.1
 
Чуть-чуть сдвинем точку [latex]A[/latex] вправо. Через полученную точку [latex]A'[/latex] и точку [latex]P[/latex] проведем прямую до пересечения с осью ординат в точке [latex]C'[/latex]. Если сдвиг был достаточно мал, то в треугольнике [latex]OA’C'[/latex] не появится ни одной точки с целыми координатами, которой не было бы в треугольнике [latex]OAC[/latex].
При центральной симметрии относительно [latex]P[/latex] любая целочисленная точка прямоугольника [latex]OABC[/latex] переходит в целочисленную точку этого же прямоугольника. Поэтому все отличные от [latex]P[/latex] целочисленные точки прямоугольника разбиваются на пары точек, симметричных относительно [latex]P[/latex].
Итак, если [latex]A'[/latex] достаточно близка к точке [latex]A[/latex], то внутри и на границе треугольника [latex]OA’C'[/latex] расположена ровно половина отличных от [latex]P[/latex] целочисленных точек, т.е. [latex]2 \cdot a \cdot b + a + b[/latex] точек. Вместе с точкой [latex]P[/latex] получаем всего [latex]2 \cdot a \cdot b + a + b + 1[/latex] точек. Мы решили пункт б).
 
Теперь займемся пунктом а). Для определенности, пусть прямая отсекает от первого координатного угла треугольник [latex]OA_1C_1[/latex], где точка [latex]A_1[/latex] расположена правее точки [latex]A[/latex](рис.2).
 
method-draw-image (9)
Рис.2
 
Чтобы получить треугольник [latex]OA_1C_1[/latex] из треугольника [latex]OAC[/latex], достаточно «отрезать» от последнего треугольник [latex]CC_{1}P[/latex] и добавить треугольник [latex]AA_{1}P[/latex].
Но при центральной симметрии относительно точки [latex]P[/latex] треугольник [latex]CC_{1}P[/latex] переходит в треугольник, являющийся частью треугольника [latex]AA_{1}P[/latex](закрашенный на рисунке 2). Целочисленные координаты при этом переходят в целочисленные. Задача решена.

M1722. Количество целых точек: 2 комментария

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *