Question

На равномерной квадратной сетке выбрано 5 произвольных узлов. Докажите, что среди этих узлов есть хотя бы 2 таких, что середина соединяющего их отрезка тоже будет узлом сетки.

Answer 1

Будем считать узлами сетки точки на плоскости XY с целочисленными координатами.
Для узлов (xi,yi), (xj, yj) середина соединяющего их отрезка имеет координаты ( [xi+xj]/2, [yi+yj]/2 ) и является узлом, если координаты целые.
Для целых чисел a,b число (a+b)/2 является целым, если одновременно a и b четные, либо если одновременно a и b нечетные.
Т.е. среди пяти выбранных узлов должны найтись два таких, что четности их координат попарно совпадают.
Среди пяти узлов найдется хотя бы три с одинаковой четностью x-координат (Пусть среди пяти узлов k имеют четную x-координату. Если k >= 3, имеется 3 узла с четной координатой. Если k < 3, то количество узлов с нечетной x-координатой = 5 - k >= 3 - имеется 3 узла с нечетной координатой). Рассмотрим эти три узла. Среди них найдется хотя бы два с одинаковой четностью y-координаты (Аналогично, среди чисел k и 3-k хотя бы одно >= 2). Т.е. мы получили два узла с попарно одинаковыми четностями координат -> середина соединяющего их отрезка имеет целые координаты -> она является узлом сетки.

Answer 2

Доказательство:

Предположим, что на равномерной квадратной сетке выбрано 5 произвольных узлов, и ни одна из соединяющих их отрезков не имеет середину в виде узла сетки. Рассмотрим все возможные соединения между этими узлами:

1. Если соединение происходит по горизонтали, то это значит, что два узла находятся на одной горизонтальной линии. В этом случае, мы можем рассмотреть отрезок, соединяющий эти два узла, и его середину. Поскольку сетка равномерная, середина этого отрезка должна быть узлом сетки. Из нашего предположения следует, что такой узел не существует.

2. Если соединение происходит по вертикали, то это значит, что два узла находятся на одной вертикальной линии. Аналогично предыдущему случаю, мы можем рассмотреть отрезок, соединяющий эти два узла, и его середину. Опять же, из равномерности сетки следует, что середина этого отрезка должна быть узлом сетки. Опять же, из нашего предположения следует, что такой узел не существует.

3. Если соединение происходит по диагонали, то это значит, что два узла находятся на одной диагональной линии. Аналогично предыдущим случаям, мы можем рассмотреть отрезок, соединяющий эти два узла, и его середину. Из равномерности сетки следует, что середина этого отрезка должна быть узлом сетки. И снова, из нашего предположения следует, что такой узел не существует.

Таким образом, мы пришли к противоречию с нашим предположением. Если на равномерной квадратной сетке выбрано 5 произвольных узлов, то среди них обязательно найдутся хотя бы 2 таких, что середина соединяющего их отрезка будет узлом сетки.