I am looking for solution of this puzzle:
There is a kingdom with a square shape with sides of length 1. The castle is located at the center of the square. At the castle the king lives under the protection of one soldier. There are other soldiers, but each soldier is at his own house. Houses are spread throughout the area of the kingdom, and everyone is aware of where they are.
A war has been declared with a neighboring kingdom, and the king needs to collect all the soldiers at the castle urgently. To do this, he sends the soldier at the castle with the news to gather troops from the other places. Each soldier who learned the news, if necessary, can participate in the gathering. They can travel at the speed of 1.
What is the minimum time in which the king can collect all solders, regardless of their number and initial placement? (Number of soldiers is finite).
I see that the time should satisfy:
$$T_{min} \geq 2+\sqrt{2} = 3.4142...$$ This is the minimum time to gather solders from 4 houses in square's corners. $T = 2+\sqrt{2}$ feels to be the minimum: somehow with help of new solders everyone in a middle zone should be gathered while the very first solder goes via 3 corners.
But I have no idea how to find a generic algorithm for $T_{\mathrm{min}}$, which will achieve such a time for arbitrary number of houses.
P.S. Please be aware when you formulate your algorithm and prove it that there are so many possibilities that it is easy to miss something. I tried many times already, feeling that I've almost got it. But my solutions always had some small unclearness, and when I investigated the "proof" more explicitly and carefully I would find a gap in it...
P.P.S. I tried the following strategy:
- When solder decides to go to some house he "reserves" it.
- Once a solder is free (has delivered the news to another house) he takes the closest house from all unreserved and goes there. If there are several closest houses he chooses at random.
No comments:
Post a Comment