Задача
Дан квадратный лист клетчатой бумаги размером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 клеток содержит нечетное число узлов. Поэтому ломаные, содержащие четное число узлов, не могут проходить через все узлы.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь