Условие
В таблице n*n отмечены некоторые 2n клеток. Докажите, что
найдется параллелограмм с вершинами в центрах отмеченных клеток.
Подсказка
Докажите, что найдется параллелограмм, у которого есть пара
сторон,
параллельных строке таблицы.
Решение
Докажем, что найдется параллелограмм, у которого есть
пара сторон, параллельных строке таблицы.
Рассмотрим в каждой строке самую левую из отмеченных клеток
(если там имеются отмеченные клетки).
Пусть в некоторой строке самая левая отмеченная клетка находится
на k-ом месте слева. Сдвинем тогда все отмеченные клетки этой
строки на (k-1) клетку влево, после этого самая левая отмеченная
клетка в этой строке будет находиться в самом левом столбце.
Проделаем такие сдвиги отмеченных клеток с каждой строкой, в
которой есть хотя бы одна отмеченная клетка.
От проделанных сдвигов свойство таблицы "иметь 4 отмеченные
клетки в вершинах параллелограмма, сторона которого параллельна
строке таблицы" не меняется. Поэтому достаточно доказать, что этим
свойством обладает уже новая таблица.
В первом столбце новой таблицы не более n отмеченных клеток.
В оставшихся (n-1) столбцах не менее n отмеченных клеток.
Тогда по
принципу Дирихле
найдутся две отмеченные клетки в одном столбце, отличном от первого
слева.
Эти две клетки, а также две клетки, расположенные в тех же строках
и в первом слева столбце, образуют искомую четверку отмеченных клеток.
Источники и прецеденты использования
