Математикадан «Туймаада» олимпиадасы. Кіші лига. 2000 жыл

Мемлекетте әрбір қаладан басқа 3 қалаға жол салынған 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$. Другими словами, у нас двудольный граф, следовательно, не существует цикла с нечетным числом ребер (дорог).