56. Misha came to a country with $n$ cities, and every two cities are directly connected by a road. He plans to start from some city and drive through several cities without visiting any city twice. Each time Misha drives on a road, the president destroys $k$ roads leading from the city to which this road leads. (If there are not that many surviving roads, the president destroys all remaining roads except the one Misha is driving on.) What is the maximum number of cities Misha can drive through, regardless of the president's actions?

(P. Khodunov, A. Kuznetsov, I. Losев)
56. Answer: Misha will be able to visit $n-k$ cities if $k \leqslant n-3$, and 2 cities otherwise (these answers coincide when $k=n-2$).

In the case $k \geqslant n-2$, while Misha is traveling from the first city to the second, the President will destroy all the other $n-2$ roads leading from the second city, and Misha will be able to visit only these two cities.

Suppose $k \leqslant n-3$. Let Misha arrive at city $X$, and at this moment there are $k+1$ cities he has not yet visited. Then Misha will be able to continue his journey by going to one of them. Indeed, the roads leading from $X$ to these cities could have been destroyed only during Misha's last trip (while he was traveling to $X$), but the President could not destroy all these roads at once, since there are more than $k$ of them.

Thus, Misha can get stuck only if there are no more than $k$ unvisited cities left, i.e., if he has already visited at least $n-k$ cities.

On the other hand, the President can initially choose some $k$ "especially valuable" cities in his country, and during each of Misha's movements, erase the roads from the city Misha is traveling to, to these $k$ cities. This way, he will prevent Misha from visiting these cities, i.e., Misha will visit no more than $n-k$ cities.