Задача 58205

Тема:    [ Многоугольники и многогранники с вершинами в узлах решетки ]

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

Условие

Существует ли замкнутая ломаная с нечетным числом звеньев равной длины, все вершины которой лежат в узлах целочисленной решетки?

Решение

Предположим, что существует замкнутая ломаная A₁...A_n с нечетным числом звеньев равной длины, все вершины которой лежат в узлах целочисленной решетки. Пусть a_i и b_i — координаты проекций вектора на горизонтальную и вертикальную оси. Обозначим длину звена ломаной через c. Тогда c² = a_i² + b_i², поэтому c² при делении на 4 дает остаток 0, 1 или 2. Если c² делится на 4, то a_i и b_i делятся на 4 (это доказывается простым перебором всех возможных остатков, которые a_i и b_i дают при делении на 4). Поэтому при гомотетии с центром A₁ и коэффициентом 0, 5 наша ломаная перейдет в ломаную с меньшей длиной звена, вершины которой по-прежнему лежат в узлах решетки. После нескольких таких операций придем к ломаной, у которой c² не делится на 4, т. е. дает остаток 1 или 2. Разберем эти варианты, предварительно заметив, что a₁ +...+ a_m = b₁ +...+ b_m = 0.
1. c² при делении на 4 дает остаток 2. Тогда числа a_i и b_i оба нечетны, поэтому число a₁ +...+ a_m нечетно и не может равняться нулю.
2. c² при делении на 4 дает остаток 1. Тогда одно из чисел a_i и b_i нечетно, а другое четно, поэтому число a₁ +...+ a_m + b₁ +...+ b_m нечетно и не может равняться нулю.

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

книга
Автор	Прасолов В.В.
Год издания	2001
Название	Задачи по планиметрии
Издательство	МЦНМО
Издание	4*
глава
Номер	24
Название	Целочисленные решетки
Тема	Целочисленные решетки
параграф
Номер	1
Название	Многоугольники с вершинами в узлах решетки
Тема	Многоугольники и многогранники с вершинами в узлах решетки
задача
Номер	24.004