MathDB

5

Part of 2016 Japan MO Finals

Problems(1)

Classifying roads

Source: Japan Mathematical Olympiad 2016 Q5

4/1/2016
m,nm,n are positive integers such that m≥2m\ge 2, n<32(m−1)n< \frac{3}{2}(m-1). In a country there are mm cities and nn roads, each road connect two different cities, and there can be multiple roads between two cities. Prove that there exist a way to separate the cities into two groups α\alpha and β\beta, where all roads connecting a city in α\alpha to a city in β\beta is converted to a highway, and satisfies the following conditions: [*]Both groups have at least one city, and [*]for each city, the number of highways coming out from that city does not exceed 11.
combinatorics