Задача 78246

Темы:    [ Четность и нечетность ] [ Шахматные доски и шахматные фигуры ] [ Шахматная раскраска ] [ Обход графов ]

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

Условие

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

Решение

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

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

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

олимпиада
Название	Московская математическая олимпиада
год
Номер	24
Год	1961
вариант
	1
Класс	8
Тур	1
задача
Номер	4