Задача 98443

Темы:    [ Шахматные доски и шахматные фигуры ] [ Четность и нечетность ] [ Деревья ] [ Доказательство от противного ] [ Многоугольники и многогранники с вершинами в узлах решетки ] [ Замощения костями домино и плитками ] [ Раскраски ] [ Теорема Пика ]

Сложность: 5+ Классы: 9,10,11

Условие

Авторы: Шаповалов А.В., Садыков Р.

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

Решение 1

  Предположим противное: ладье удалось обойти доску, сделав 32 горизонтальных и 32 вертикальных хода. Соединив центры полей в порядке обхода их ладьей, получим замкнутую ломаную с углами 90° между звеньями. Поскольку область D, ограниченная такой ломаной, не содержит ни одного поля целиком, на ломаной обязательно имеется двойной поворот (рис. слева; см. решение задачи 98365), причём такой, что "узел" a находится внутри D.

  Закроем среднюю часть двойного поворота доминошкой 1×2. При этом в ломаной образуется разрыв, который можно устранить, "связав" оборванные звенья (рис. в центре). При этом длина ломаной уменьшится на 2, причем если на доске появилась вертикальная доминошка (как на рисунке), то стало меньше на два горизонтальных хода и наоборот. На новой ломаной снова есть двойной поворот. Поступим с ним аналогично и т. д. Описанную процедуру можно повторять до тех пор, пока ломаная не превратится в единичный квадрат (рис. справа). Так как стало меньше на 30 вертикальных и 30 горизонтальных ходов, то на доске появилось 15 горизонтальных и 15 вертикальных доминошек. Оставшийся квадрат закроем двумя вертикальными доминошками. В результате мы получим разбиение шахматной доски на доминошки, в котором вертикальных доминошек нечётное число.
  Но такое разбиение невозможно – см. задачу 88042.

Решение 2

  Рассмотрим координатную сетку, узлы которой соответствуют центрам полей доски (теперь все вершины многоугольника D лежат в узлах). По известной формуле Пика (см. задачу 58208) площадь S области D равна  n + ^m/₂ – 1,  где n – количество узлов, находящихся внутри D, а m – количество узлов, находящихся на её границе. В нашем случае  n = 0,  m = 64,  то есть S = 31.
  Рассмотрим полосатую раскраску доски: нечётные горизонтали – чёрные, чётные – белые. Разрежем область D на прямоугольники ширины 1, проведя вертикальные прямые через центры всех полей. Каждый из них ограничен сверху и снизу горизонтальными отрезками-ходами. Площадь каждого прямоугольника – целое число, причем оно нечётно тогда и только тогда, когда ограничивающие его горизонтальные ходы находятся в горизонталях разного цвета.
  Поскольку площадь S нечётна, количество прямоугольников нечётной площади нёчетно. Значит, нечётно и количество k ходов, сделанных в чёрных горизонталях (такие ходы "входят" по одному в прямоугольники нечётной площади и по два в некоторые прямоугольники чётной площади).
  Всего из 32 чёрных полей сделано 32 хода. При этом k из них (горизонтальных) сделаны снова на чёрные поля, а  32 – k  (вертикальных) – с чёрных полей на белые. Но ладья после обхода доски вернулась на поле того же цвета, поэтому количество ходов с чёрных полей на белые равно количеству ходов с белых полей на чёрные. Таким образом количество всех вертикальных ходов равно  64 – 2k,  а количество горизонтальных ходов равно 2k и, следовательно, не может равняться 32 (ведь k нечётно).

Замечания

баллы: 8-9 кл. – 9, 10-11 кл. – 8

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

олимпиада
Название	Турнир городов
Турнир
Дата	1998/1999
Номер	20
вариант
Вариант	весенний тур, основной вариант, 8-9 класс
Задача
Номер	6
олимпиада
Название	Турнир городов
Турнир
Дата	1998/1999
Номер	20
вариант
Вариант	весенний тур, основной вариант, 10-11 класс
Задача
Номер	6