Problem

Source: Romanian TST 5 2007, Problem 3

Tags: inequalities, quadratics, combinatorics proposed, combinatorics



Three travel companies provide transportation between $n$ cities, such that each connection between a pair of cities is covered by one company only. Prove that, for $n \geq 11$, there must exist a round-trip through some four cities, using the services of a same company, while for $n < 11$ this is not anymore necessarily true. Dan Schwarz