Задача 116211

Темы:    [ Ломаные ] [ Четность и нечетность ] [ Целочисленные решетки (прочее) ]

Сложность: 4- Классы: 7,8,9

Условие

Автор: Шаповалов А.В.

Каждое звено несамопересекающейся ломаной состоит из нечётного числа сторон клеток квадрата 100×100, соседние звенья перпендикулярны.
Может ли ломаная пройти через все вершины клеток?

Решение

Предположим, что ломаная, обладающая указанными свойствами, существует. Рассмотрим ту из сторон квадрата, которой не принадлежит ни один из концов ломаной. Если такой стороны нет, то есть ломаная идёт из одного угла квадрата в другой, то рассмотрим ту из сторон, вдоль которой направлено первое звено ломаной (см. рис.). Каждый из узлов этой стороны принадлежит некоторому (причём ровно одному) звену ломаной, идущему вдоль стороны квадрата. Действительно: если узел не является концом ломаной, то есть два звена, его содержащие, и одно из них обязано идти вдоль стороны. Если же узел является концом ломаной, то выполнение этого свойства гарантировано выбором стороны.

Так как длина каждого звена нечётна, то каждому звену принадлежит чётное число узлов, следовательно, и общее число узлов на стороне квадрата должно быть чётным. Однако это число равно 101. Противоречие.

Ответ

Не может.

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

олимпиада
Название	Московская математическая олимпиада
год
Год	2011
Номер	74
класс
Класс	8
задача
Номер	4