MathDB

5

airway companies operate in a country consisting of

36

cities. Between any pair of cities exactly one company operates two way flights. If some air company operates between cities

A, B

and

B, C

we say that the triple

A, B, C

is properly-connected. Determine the largest possible value of

k

such that no matter how these flights are arranged there are at least

k

properly-connected triples.

Problem Statement