Условие
Дан квадратный лист клетчатой бумаги размером
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 |
