MathDB

10.8

Part of 2000 All-Russian Olympiad Regional Round

Problems(1)

2000 cities, 2N +2 republics - All-Russian MO 2000 Regional (R4) 10.8

Source:

9/26/2024
There are 20002000 cities in the country, some pairs of cities are connected by roads. It is known that no more than NN different non-self-intersecting cyclic routes of odd length. Prove that the country can be divided into 2N+22N +2 republics so that no two cities from the same republic are connected by a road.
combinatorics