MathDB
Cities in countries, maximum no. of flights offered

Source: Balkan MO ShortList 2008 C2

April 5, 2020

Problem Statement

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.
Back to ProblemsView on AoPS