In a country with $n$ cities, there is a recurrent one-way flight between every pair of cities. Every flight has a constant price in the range $\$ 100, \$ 120, \$ 140, \$ 160, \$ 180$. A $\$ N$ flight ticket gives unlimited access to flights which cost $\$ N$, and tickets can be traded for tickets of lower prices. For example, with a $\$ 160$ ticket, Bob could take a $\$ 160$ flight, trade his ticket for a $\$ 120$ ticket, then take a $\$ 120$ flight.

Aerith loves flying and wonders how many successive flights she can take with one ticket. What is the minimum $n$ needed to guarantee that she can take 4 such flights in a row?
For each city $C$, let $f_{C}(\$ N)$ be the maximum distance one can travel starting at $C$ with an $\$ N$ ticket. If Aerith cannot take 4 flights in a row, $f_{C}$ is an nondecreasing function that remains between 0 and 3 , of which there are $\left(\left(\begin{array}{l}4 \\ 5\end{array}\right)\right)=\left(\begin{array}{l}8 \\ 5\end{array}\right)=56$. No two cities $C_{1}$ and $C_{2}$ can have the same $f$, because if there is a flight of price $\$ N$ from $C_{1}$ to $C_{2}, f_{C_{1}}(\$ N) \geq f_{C_{2}}(\$ N)+1.57$ thus forces there to be a chain of 4 flights in a row.

To show that it is possible for all chains of flights to have length at most 3 for 56 cities, we reverse this proof - correspond each city $C$ to one non-decreasing function
$F$ from tickets to $\{0,1,2,3\}$, and for every two cities where $N$ is maximal so that $f_{C_{1}}(\$ N) \neq f_{C_{2}}(\$ N)$, let there be a flight from $C_{1}$ to $C_{2}$ with price $\$ N$. One can see that $f_{C}=F_{C}$, giving the desired.