Комбинаторика, теорвер и теория чисел на Физтехе

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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