Олимпиада Туймаада по математике. Младшая лига. 2000 год

В стране 2000 городов, из каждого из которых ведут ровно три дороги в другие города. Докажите, что можно закрыть 1000 дорог так, чтобы в стране не осталось ни одного замкутого маршрута, состоящего из нечетного числа дорог.

Комментарий/решение

Очевидно, что количество дорог составляет $3000$. Разобьем города на две группы $A, B$, каждая группа содержит ровно $1000$ городов, таких, что число всех дорог, соединяющих город в $A$ с городом в $B$, максимально.

Предположим, существуют два города $a_1\in A$ и $b_1\in B$, такие что $a_1$ имеет не более одного соседа в $B$, а $b_1$ имеет не более одного соседа в $A$. Тогда, поменяв местами $a_1$ и $b_1$, мы получим конфигурацию с большим количеством перекрестков, чем раньше, что противоречило бы максимальному свойству разбиения $A,B$.

Таким образом, таких двух городов не существует. Это просто означает, что в одной из групп, WLOG говорит $A$, все города имеют как минимум двух соседей в $B$. Следовательно, количество перекрестков составляет не менее $2000$. Из них выбираем ровно $2000$ и закрываем остальные $1000$.

Обратите внимание, что все оставшиеся дороги соединяют город $A$ с городом $B$. Другими словами, у нас двудольный граф, следовательно, не существует цикла с нечетным числом ребер (дорог).