In some country there are cities and roads, every road connects two different cities and between any two cities there is at most one road. Roads are named by numbers . Tonči travels along some roads in such a way that, when he writes down the names of the roads in the order he passes through them, he obtains an ascending sequence of numbers.
Show that there is a city such that starting from it Tonči can pass through at least roads.
Solution
We place one of Tonči's friends in every city. In the step () friends which are at that moment in the cities connected by the road switch their positions. In each step we have exactly two shifts from one city to another, and all together shifts. Hence at least one of the friends has shifted at least times.
If Tonči starts in the city where this friend was placed he can satisfy the condition of the problem.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.