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

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

Условие

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

Решение

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

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

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

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