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

Проект МЦНМО
при участии
школы 57
Задача 65548
Темы:    [ Четность и нечетность ]
[ Степень вершины ]
Сложность: 3+
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

Имеется несколько городов, некоторые из них соединены автобусными маршрутами (без остановок в пути). Из каждого города можно проехать в любой другой (возможно, с пересадками). Иванов купил по одному билету на каждый маршрут (то есть может проехать по нему один раз всё равно в какую сторону). Петров купил n билетов на каждый маршрут. Иванов и Петров выехали из города A. Иванов использовал все свои билеты, новых не покупал и оказался в другом городе B. Петров некоторое время ездил по купленным билетам, оказался в городе X и не может из него выехать, не купив новый билет. Докажите, что X – это либо A, либо B


Решение

Пусть Петров в некоторый момент оказался в городе C, отличном от A и B. Из C выходит чётное число маршрутов (поскольку Иванов выезжал из него столько же раз, сколько въезжал). Значит, у Петрова вначале было чётное число билетов на маршруты из C. Но израсходовал он к этому моменту только нечётное число из них (въехал в C на один раз больше, чем выехал), поэтому выехать из C Петров может.

Замечания

4 балла

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

олимпиада
Название Турнир городов
Турнир
Номер 26
Дата 2004/2005
вариант
Вариант осенний тур, тренировочный вариант, 8-9 класс
задача
Номер 3

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

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