Problem 11.7. In a country, there are 110 cities. Between any two of them, there is either a road or there is not.

A motorist was in a certain city, from which there was exactly one road. After driving along this road, he arrived at a second city, from which there were already exactly two roads. Driving along one of them, he arrived at a third city, from which there were already exactly three roads, and so on. At some point, after driving along one of the roads, he arrived at the $N$-th city, from which there were already exactly $N$ roads. At this point, the motorist ended his journey. (For each $2 \leqslant k \leqslant N$, from the $k$-th city, there were exactly $k$ roads, including the one by which the motorist arrived in this city.)

What is the largest value that $N$ can take?
Answer: 107.

Solution. Let's number the cities in the order they are visited by the motorist: $1,2,3, \ldots, N$.

Suppose $N \geqslant 108$. From city 1, there is a road only to city 2, so from city 108, all roads lead to all 108 cities, except for 1 and 108. But then from city 2, there are at least three roads: to cities 1, 3, and 108. This is a contradiction, so $N \leqslant 107$.

Let's provide an example for $N=107$. Suppose the cities are numbered $1,2,3, \ldots, 109,110$. Let

- for all $1 \leqslant i \leqslant 54$, there is a road from city $i$ to city $i+1$;
- for all $56 \leqslant j \leqslant 107$, there are roads from city $j$ to all cities from 110 - $j$ to 110 inclusive, except for city $j$ itself;
- from city 55, there are roads to cities 109 and 110;
- there are no other roads in the country.

It is not difficult to verify that for all $1 \leqslant k \leqslant 107$, there are exactly $k$ roads from city $k$. The motorist could have driven through these cities.