Версия для печати
Убрать все задачи

---

Клетки доски 2001×2001 раскрашены в шахматном порядке в чёрный и белый цвета так, что угловые клетки чёрные. Для каждой пары разноцветных клеток рисуется вектор, идущий из центра чёрной клетки в центр белой. Докажите, что сумма нарисованных векторов равна 0.

   Решение

Темы:    [ Обход графов ] [ Шахматная раскраска ] [ Четность и нечетность ] [ Целочисленные решетки (прочее) ]

Сложность: 4 Классы: 6,7,8,9

Прислать комментарий

Условие

Любознательный турист хочет прогуляться по улицам Старого города от вокзала (точка A на плане) до своего отеля (точка B). Турист хочет, чтобы его маршрут был как можно длиннее, но дважды оказываться на одном и том же перекрестке ему неинтересно, и он так не делает. Нарисуйте на плане самый длинный возможный маршрут и докажите, что более длинного нет.

Решение

  Пример. Один из возможных маршрутов туриста изображён на рисунке слева. Двигаясь по этому пути, турист пройдёт 34 улицы (улицей мы называем отрезок между двумя соседними перекрёстками).

  Оценка. Всего в Старом городе 36 перекрёстков. Всякий раз, когда турист проходит очередную улицу, он попадает на новый перекрёсток. Таким образом, больше 35 улиц турист пройти не сможет (начальный перекрёсток A не считается). Покажем, что посетить 35 перекрёстков (и, следовательно, пройти 35 улиц) турист тоже не сможет. Для этого раскрасим перекрёстки в чёрный и белый цвета в шахматном порядке (рис. справа). Всякий раз, проходя улицу, турист попадает на перекрёсток другого цвета. И отель, и вокзал расположены на белых перекрёстках. Поэтому любой маршрут содержит чётное число улиц, а число 35 нечётно.

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