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