MathDB

Let

n

be an integer greater than

1

, and let

p

be a prime divisor of

n

. A confederation consists of

p

states, each of which has exactly

n

airports. There are

p

air companies operating interstate flights only such that every two airports in different states are joined by a direct (two-way) flight operated by one of these companies. Determine the maximal integer

N

satisfying the following condition: In every such confederation it is possible to choose one of the

p

air companies and

N

of the

np

airports such that one may travel (not necessarily directly) from any one of the

N

chosen airports to any other such only by flights operated by the chosen air company.

Problem Statement