Задания
Версия для печати и копирования в MS Word
В пунктах A и B находится по автомобилю. Каждую минуту эти два автомобиля одновременно переезжают в какой-либо соседний пункт (пункты, соединённые отрезками, называют соседними). Докажите, что автомобили никогда не окажутся одновременно в одном пункте.
Решение.
Выделим некоторые вершины графа, обведя их в кружочек. Изначально, один из автомобилей находится в выделенной вершине, а второй нет. Из выделенной вершины можно попасть только в невыделенную и наоборот (двудольный граф). Поэтому в одной вершине автомобили оказаться не могут.
?
Межрегиональная олимпиада школьников на базе ведомственных образовательных организаций, 9 класс, 2 тур (заключительный), 2016 годКлассификатор: Разное. Логические задачи