Областная олимпиада по математике, 2000 год, 10 класс

На шахматной доске $n\times n$ расставлены $2n$ пешек (пешка ставится в центр клетки). Докажите, что найдутся четыре пешки, которые находятся в вершинах некоторого параллелограмма.

Комментарий/решение

Пусть $k$ это количество строк в которых есть хотя бы одна пешка($k \le n$). Очевидно что если расстояние каких то пар пешек в двух различных строках будут совпадать, то он будет параллелограммом.

Пусть $a_1$ количество пешек в первой из вышеуказанных $k$ строк. Любая строка где $a_i$ пешек, образует не менее $a_i-1$ различных расстояний. Теперь посчитаем все расстояния

$a_1 - 1 + a_2 - 1+...+ a_k - 1 = 2n-k \le n$

Но расстояний у нас всего от 1 до $n-1$, а значит какие то две будут совпадать.

Ещё с прошлого века задачи решай