МОШ 2022, 10 класс, задача 3
Среди любых пяти узлов обычной клетчатой бумаги обязательно найдутся два, середина отрезка между которыми — тоже узел клетчатой бумаги. А какое минимальное количество узлов сетки из правильных шестиугольников необходимо взять, чтобы среди них обязательно нашлось два, середина отрезка между которыми — тоже узел этой сетки?
(А. Кулыгин)
Ответ. .
Лемма. Среди любых пяти узлов сетки из правильных треугольников найдутся два, середина отрезка между которыми — тоже узел сетки.
Доказательство. Введём начало отсчёта в одном из узлов сетки и обозначим за и радиус-векторы к двум ближайшим узлам (см. картинку). Тогда узлы сетки суть точки вида для целых и . По принципу Дирихле из пяти точек найдутся две точки и , у которых одновременно совпадает чётность и и чётность и . Середина отрезка, соединяющего эти две точки, есть точка . Она является узлом сетки в силу одинаковой чётности и , и .
Решение. На первой картинке можно увидеть пример расположения узлов сетки, среди которых нет двух, середина отрезка между которыми — узел сетки. Докажем, что девяти узлов достаточно. Заметим, что шестиугольная сетка разбивается в объединение двух треугольных (см. вторую картинку). По принципу Дирихле среди любых девяти узлов по крайней мере пять окажутся в одной из этих двух треугольных сеток. По лемме среди этих пяти узлов найдутся два искомых.
