Printable View
Please, I need the solution of a problem, and I can only find it in Russian. I don't know russian and it's not prabably that I will learn it in time to understand the solution. I'll post the link where I found it:
http://kvant.mirror1.mccme.ru/1989/11/r ... nta_ma.htm
It's the problem M1168, the third on the list.
I only need the solution ( don't worry about the mathmatical symbols, the text is what is important)
Please I need this fast.
Thank you very much :D
Let's call a town "out-of-the-way", if there are no more than two roads, which go out of it. Let's erase from a mapany out-of-the-way town with roads going from it. Let's clean in the same way a new map and let's go on to erase out-of-the-way towns until they'll disappear. Number of roads we can erase with that is no more than 2*1989? which is less than 4000; so there will stay at least one town.
Let's choose any of the remaining towns. Out of it as from any other go no less than three roads. Let's follow one of them and every time we come to another town, we'll follow one of the roads, different from the one we came. If some two routes, consisting less than of 10 roads will be finished in the same town, we'll have the required route consisting of less than 20 roads. But it cannot be otherwise, since the number of such routes is no less than 3+3*3+3*2^2+...
I wonder, how did you find the solution if you don't speak Russian. :D
1168 There are 1989 towns in the country with 4000 roads (each road connects two towns). Prove that there is at least one closed trace passing through not more than 20 towns.
Let us call a town "village" if it is connected to not more than 2 roads. Remove all villages (if exist) with all roads connected to them. Repeat the operation until there are no villages. The total number of removed roads is not more than 2*1989 so several towns remains anyway.
Take any remained town. It is connected to at least 3 roads (as well as all other remained towns). Take one of those roads and move. From the next town take another road (different from that used to arrive) and continue moving. If any 2 such traces not more than 10 roads long are finished in one town then here is a closed trace according to the task (see Fig.). But the opposite situation is impossible because the total number of such traces is not less than 3+..........=3096 and the number of towns (ending points) is not more than 1989.
This solution can be generalized for the case of n towns and m roads. As a result of map cleaning there remain towns with not less than s roads connected, where s is the minimum integer such as s>=m/n. The speculation about non-crossed traces allows one to prove the existance of cycles (closed traces) of l roads where l<=(see formula 1) (square brackets mean an integer fraction of real number). Namely with n=1989 and m=4000 we have s=3 and l<=20.
Another interesting task is: which number of towns n and roads m allows to construct a system of roads without cycles of length d? With rather complicated estimations of mean number of roads it is possible to show that it is possible with m< (see formula 2).
A.A.Razborov
Edit: I am late but my translation is more complete. *)
Thank you very much guys :)