Задача 35753

Темы:    [ Принцип Дирихле (прочее) ] [ Целочисленные решетки (прочее) ]

Сложность: 3 Классы: 8,9,10

Условие

В выпуклом многоугольнике на плоскости содержится не меньше m²+1 точек с целыми координатами. Докажите, что в нем найдется m+1 точек с целыми координатами, которые лежат на одной прямой.

Подсказка

Раскрасьте целые точки плоскости в m² цветов. Найдутся две точки одного цвета.

Решение

По принципу Дирихле среди m²+1 точек с целыми координатами найдутся такие две точки (k, l) и (k₁, l₁), что k=k₁ (mod m) и l=l₁ (mod m). Тогда m+1 точек , , имеют целые координаты и лежат на отрезке, соединяющем точки (k, l) и (k₁, l₁).

Источники и прецеденты использования

web-сайт

задача