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

---

В первом пенале лежат лиловая ручка, зелёный карандаш и красный ластик; во втором – синяя ручка, зелёный карандаш и жёлтый ластик; в третьем – лиловая ручка, оранжевый карандаш и жёлтый ластик. Содержимое этих пеналов характеризуется такой закономерностью: в каждых двух из них ровно одна пара предметов совпадает и по цвету, и по назначению. Что должно лежать в четвёртом пенале, чтобы эта закономерность сохранилась? (В каждом пенале лежит ровно три предмета: ручка, карандвш и ластик.)

   Решение

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

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

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

Условие

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

Решение

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

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

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