Задача 58185

Тема:    [ Шахматная раскраска ]

Сложность: 5 Классы: 8,9

Условие

Дан квадратный лист клетчатой бумаги размером 100×100 клеток. Проведено несколько несамопересекающихся ломаных, идущих по сторонам клеток и не имеющих общих точек. Эти ломаные идут строго внутри квадрата, а концами обязательно выходят на границу. Докажите, что кроме вершин квадрата найдется еще узел (внутри квадрата или на границе), не принадлежащий ни одной ломаной.

Решение

Раскрасим узлы клетчатой бумаги в шахматном порядке (рис.). Так как концы любого единичного отрезка разноцветны, то ломаная с одноцветными концами содержит нечетное число узлов, а с разноцветными — четное. Предположим, что из всех узлов границы (кроме вершин квадрата) выходят ломаные. Докажем, что тогда все ломаные вместе содержат четное число узлов. Для этого достаточно доказать, что число ломаных с одноцветными концами четно. Пусть на границе квадрата расположено 4m белых и 4n черных узлов (вершины квадрата не учитываются). Обозначим число ломаных, у которых оба конца белые, через k. Тогда имеется 4m - 2k ломаных с разноцветными концами и  [4n - (4m - 2k)]/2 = 2(n - m) + k ломаных с черными концами. Поэтому ломаных с одноцветными концами будет k + 2(n - m) + k = 2(n - m + k) — четное число. Остается заметить, что квадратный лист бумаги размером 100×100 клеток содержит нечетное число узлов. Поэтому ломаные, содержащие четное число узлов, не могут проходить через все узлы.

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

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