Задача 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