Browse · MathNet
Print62nd Ukrainian National Mathematical Olympiad, Third Round, Second Tour
Ukraine counting and probability
Problem
There is a central train station at point , which is connected to other train stations with tracks. There is also a track between stations and for each (here ). The length of each track is equal to , and the length of each track is equal to , for each .
There are also trains , the speed of the train is . Trains can move only by the tracks above, in both directions. No time is wasted on changing directions. If two or more trains meet at some point, they will move together from now on, with the speed equal to that of the fastest of them.
Is it possible to arrange trains into stations (each station has to contain one train initially), and to organize their movement in such a way, that all trains arrive at in time ?
There are also trains , the speed of the train is . Trains can move only by the tracks above, in both directions. No time is wasted on changing directions. If two or more trains meet at some point, they will move together from now on, with the speed equal to that of the fastest of them.
Is it possible to arrange trains into stations (each station has to contain one train initially), and to organize their movement in such a way, that all trains arrive at in time ?
Solution
Answer: yes.
Arrange the trains clockwise as following: and . Now let's show how they should move to meet in time.
Let move through the station of (at this time stays at place and is waiting for ), and they arrive to in time .
Let train move through the station of (at this time stays at place and is waiting for ), and they arrive to in time .
Let train move through the station of (at this time stays at place and is waiting for ) and they arrive to in time .
goes to right away in time .
goes to right away in time .
Now we see that two groups — and — arrive at the time , but the groups and arrive faster than in , and their speeds are larger than those of first groups. So, the group upon its arrival to goes to the group , unites with it, and goes to the point with its speed. Similarly, group will get to faster.
It's possible to find the time of arrival of each group to . For example, for the last group this time is . Indeed, group arrives at at , at this time has travelled in the direction of point . The time before their meet is , and it's equal to the time spent to arrive back to .
Arrange the trains clockwise as following: and . Now let's show how they should move to meet in time.
Let move through the station of (at this time stays at place and is waiting for ), and they arrive to in time .
Let train move through the station of (at this time stays at place and is waiting for ), and they arrive to in time .
Let train move through the station of (at this time stays at place and is waiting for ) and they arrive to in time .
goes to right away in time .
goes to right away in time .
Now we see that two groups — and — arrive at the time , but the groups and arrive faster than in , and their speeds are larger than those of first groups. So, the group upon its arrival to goes to the group , unites with it, and goes to the point with its speed. Similarly, group will get to faster.
It's possible to find the time of arrival of each group to . For example, for the last group this time is . Indeed, group arrives at at , at this time has travelled in the direction of point . The time before their meet is , and it's equal to the time spent to arrive back to .
Final answer
yes
Techniques
AlgorithmsGames / greedy algorithms