Задача 069 — Задачи на Графы

В стране 100 городов. Некоторые из них соединены дорогами, причем между любыми двумя городами есть не более одной дороги. Города пронумерованы числами от 1 до 100. Петя совершил 100 путешествий по дорогам страны, каждый раз начиная путешествия в разных городах. Все свои путешествия он осуществляет по следующему правилу. Оказавшись в каком-либо городе $A$ , Петя находит среди всех городов, соединенных с $A$ , город $B$ с наименьшим номером. Если город $B$ уже был посещен в этом путешествии, или из $A$ вообще нет ни одной дороги, путешествие тут же заканчивается в $A$ . $B$ противном случае, Петя перемещается из $A$ в $B$ и продолжает путешествие по этому же правилу. Оказалось, что совершив 100 путешествий, Петя посетил все города страны поровну раз. При каком наибольшем количестве дорог в стране такое возможно?

Подсказка

Рассмотрим город номер 100. Он может быть посещен в двух случаях: 1) мы начали путешествие с него; 2) мы начали путешествие с города $i<100$ и город $i$ соединен только с городом 100.

Решение

Ответ: 2500.

Решение. Оценка. Рассмотрим город номер 100. Он может быть посещен в двух случаях: 1) мы начали путешествие с него; 2) мы начали путешествие с города $i<100$ и город $i$ соединен только с городом 100. Предположим, что все города были посещены хотя бы три раза. Тогда есть хотя бы два города, которые соединены только с городом 100 . Но наибольший из таких городов может быть посещен только один раз (когда путешествие начинается в нем). Если все города посещены 1 раз, то в стране вообще нет дорог, что нас не устраивает. Значит, все города посещены ровно два раза. Удалим город 100 и город $i$ , соединенный только с ним. Мы удалили не более $98+1$ дорог. Для оставшейся части страны всё ещё верно утверждение, что при путешествиях с началом в каждом из городов, все города посещаются поровну раз, так как города $i$ и 100 посещались ровно 2 раза в путешествиях с началом $i$ и 100. Повторяя такие рассуждения, мы будем удалять пары городов, удаляя не более $97,95, \ldots, 1$ дорог. Значит, изначально в стране было не более $1+3+\ldots+99=$ 2500 дорог. Пример: при $i \leqslant 50$ город $i$ соединим с городами с номерами хотя бы $101-i$ . Также соединим попарно города с номерами, большими 50. Тогда начиная в городе $i$ мы перемещаемся в город $101-i$ и останавливаемся. Значит, все города будут посещены дважды. И количество ребер равно $1+2+\ldots+50+50 \cdot 49 / 2=2500$ .