MathDB

C2

Part of 2008 Balkan MO Shortlist

Problems(1)

Cities in countries, maximum no. of flights offered

Source: Balkan MO ShortList 2008 C2

4/5/2020
In one of the countries, there are n≥5n \geq 5 cities operated by two airline companies. Every two cities are operated in both directions by at most one of the companies. The government introduced a restriction that all round trips that a company can offer should have atleast six cities. Prove that there are no more than ⌊n23⌋\lfloor \tfrac{n^2}{3} \rfloor flights offered by these companies.