ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 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

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .