Kvant Math Problem 1113
Model the situation as a graph on $21$ vertices, the cities.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m11s
Source on kvant.digital
Problem
There are 21 cities in a country. Air service between them is provided by several airlines, each of which operates 10 nonstop routes connecting pairwise some five cities (more than one airline may operate flights between the same two cities). Every pair of cities is connected by at least one nonstop route. What is the smallest possible number of airlines?
D. V. Fomin
Exploration
Model the situation as a graph on $21$ vertices, the cities. Every airline chooses $5$ cities and operates all $10=\binom52$ routes among them, so each airline contributes a copy of the complete graph $K_5$. The condition that every pair of cities is connected by at least one nonstop route means that the complete graph $K_{21}$ must be covered by these $K_5$'s.
The question asks for the minimum number of $K_5$'s whose edge sets cover all edges of $K_{21}$.
A counting lower bound comes first. The graph $K_{21}$ has
$$\binom{21}{2}=210$$
edges. Each airline contributes at most $10$ distinct edges. Hence at least
$$210/10=21$$
airlines are necessary.
The issue is whether $21$ airlines can actually suffice. Equality in the counting bound would force every edge of $K_{21}$ to belong to exactly one airline, because $21$ copies of $K_5$ provide exactly $21\cdot10=210$ edge appearances. Thus we need a decomposition of $K_{21}$ into $21$ copies of $K_5$.
This resembles a block design. If every edge is contained in exactly one $5$-set, then counting incidences of blocks with a fixed vertex gives
$$r(5-1)=20,$$
so $r=5$. Thus each city would belong to exactly $5$ airlines.
Can such a design exist? The parameters are
$$v=21,\qquad k=5,\qquad \lambda=1.$$
The standard formulas give
$$b=\frac{v(v-1)}{k(k-1)} =\frac{21\cdot20}{5\cdot4} =21,$$
and
$$r=\frac{v-1}{k-1} =\frac{20}{4} =5.$$
These are exactly the parameters of the projective plane of order $4$: $21$ points, $21$ lines, $5$ points on each line, every two points on a unique line.
Hence the lower bound is attainable if one uses the lines of the projective plane of order $4$ as the airlines.
The only potentially delicate point is proving rigorously that this construction indeed covers every pair of cities exactly once.
Problem Understanding
We have $21$ cities. Each airline selects $5$ cities and operates all $\binom52=10$ nonstop routes among those cities. Several airlines may use the same route. Every pair of cities must be connected by at least one nonstop route.
Interpreting cities as vertices and airline networks as copies of $K_5$, the problem asks for the smallest number of copies of $K_5$ whose union contains all edges of $K_{21}$.
This is a Type C problem, a determination of a minimum value.
The core difficulty is showing that the obvious counting lower bound is actually achievable. The answer is
$$21.$$
The reason is that equality in the counting bound corresponds to a decomposition of $K_{21}$ into $21$ edge-disjoint copies of $K_5$, and such a decomposition is provided by the projective plane of order $4$.
Proof Architecture
First claim: at least $21$ airlines are necessary, because $K_{21}$ has $210$ edges while each airline contributes only $10$ edges.
Second claim: the projective plane of order $4$ has $21$ points and $21$ lines, each line contains $5$ points, and every two points lie on exactly one line.
Third claim: if cities are identified with the points and airlines with the lines of this projective plane, then each airline operates exactly the $10$ routes among the $5$ cities on its line.
Fourth claim: every pair of cities is served by exactly one airline, because every two points of the projective plane lie on a unique line.
The hardest direction is the construction attaining the lower bound. The lemma most likely to fail under scrutiny is the verification that every pair of cities belongs to exactly one airline.
Solution
Let $N$ be the number of airlines.
The complete graph on the $21$ cities has
$$\binom{21}{2}=210$$
edges.
Each airline serves exactly five cities and operates all routes between them. Hence the routes of one airline form a copy of $K_5$, containing
$$\binom52=10$$
edges.
Since every edge of $K_{21}$ must be covered by at least one airline,
$$10N\ge 210.$$
Therefore
$$N\ge 21.$$
It remains to show that $21$ airlines are sufficient.
Consider a projective plane of order $4$. It has $21$ points and $21$ lines. Every line contains $5$ points, and every two points lie on exactly one line.
Identify the $21$ cities with the $21$ points of the projective plane. For each line, introduce one airline serving exactly the five cities corresponding to the points on that line. Since a line contains five points, each airline operates exactly
$$\binom52=10$$
routes, as required.
Take any two cities. They correspond to two points of the projective plane. By the defining property of the projective plane, there is a unique line containing those two points. The airline associated with that line operates the route between the two cities.
Hence every pair of cities is connected by at least one nonstop route. In fact, each pair is connected by exactly one airline.
Thus $21$ airlines suffice. Combined with the lower bound $N\ge 21$, this yields the minimum possible number of airlines:
$$\boxed{21}.$$
Verification of Key Steps
The counting lower bound uses only edge counts. The graph $K_{21}$ contains
$$\frac{21\cdot20}{2}=210$$
edges. One airline contributes exactly
$$\frac{5\cdot4}{2}=10$$
edges. Even if no overlaps occur, fewer than $21$ airlines can cover at most $20\cdot10=200$ edges, which is insufficient.
The attainment of the bound requires more than matching numbers. If there are exactly $21$ airlines, then the total number of edge appearances equals
$$21\cdot10=210,$$
which is the total number of edges of $K_{21}$. Any repeated coverage of an edge would force some other edge to be uncovered. Thus equality can occur only when the $K_5$'s form an edge decomposition of $K_{21}$.
For the projective-plane construction, the critical property is that every two points lie on a unique line. Given two cities, the corresponding points determine exactly one line, hence exactly one airline containing both cities. Consequently every edge of $K_{21}$ is covered once, neither omitted nor duplicated.
Alternative Approaches
The same solution can be phrased entirely in the language of block designs. Equality in the counting bound would require a collection of $21$ five-element subsets of a $21$-element set such that every pair of elements belongs to exactly one subset. This is a Steiner system with parameters $S(2,5,21)$, equivalently a balanced incomplete block design with parameters
$$(v,k,\lambda)=(21,5,1).$$
A projective plane of order $4$ is precisely such a design, so its blocks provide the airlines.
The graph-theoretic formulation in terms of decomposing $K_{21}$ into copies of $K_5$ is preferable because the lower bound and the objective are expressed directly in terms of edges and route coverage, making the counting argument and the role of the projective plane especially transparent.