MathDB

Five airlines operate in a country consisting of

36

cities. Between any pair of cities exactly one airline operates two way flights. If some airlines operates between cities

A,B

and

B,C

we say that the ordered 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