Problem

Source: India Postal Set 3 P3 2016

Tags: combinatorics, optimization



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.