The towns in one country are connected with bidirectional airlines, which are paid in at least one of the two directions. In a trip from town A to town B there are exactly 22 routes that are free. Find the least possible number of towns in the country.
It is easily seen that that the number of towns $n$ is greater than 5, since for $n=2,3,4,5$ the number of all routes from $A$ to $B$ is less than 22.
Now for $n=6$ it should be shown that the maximum number of free routes between A and B is 24. We denote with $a_1, a_2, a_3, a_4$ the other 4 towns in the country. An example showing that the upper statement is true:
$a_1 \rightarrow a_2$, $a_1 \rightarrow a_3$, $a_4 \rightarrow a_1$, $a_3 \rightarrow a_2$, $a_2 \rightarrow a_4$, $a_4 \rightarrow a_3$ are free routes as well as the routes from $A$ to any of the other towns and from $A, a_1, a_2, a_3, a_4$ to $B$.We note that making any of these routes "paid" (except $A\rightarrow B$) would make at least 3 other routes "paid". Thus it is not possible for $n=6$ to have exactly 22 free routes from $A$ to $B$.
We move to $n=7$ where the following example shows that it is possible to have exactly 22 free routes from $A$ to $B$ (We add a town $a_5$):
$A\rightarrow a_k$ for $k=1,2,3,4,5$, $\quad$ $a_i\rightarrow a_j$ for $i<j$, and $a_l\rightarrow B$ for $l=1, 3, 5$ are free.
Hence the answer is 7.