Fastest way to collect an arbitrary army

Question

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:

1. When solder decides to go to some house he "reserves" it.
2. 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.

It doesn't work.

Answer 1

I have the following results that lead some of the way towards an answer:

1. If a knight starts at the middle of a square of sidelength $a$ then he can collect all the knights in that square and bring them to its centre in time at most $Ca$, for some constant $C$ not depending on $a$ or the number of knights. (This proves that we can't slow down the first knight for ages just by putting loads of knights closely surrounding the castle.)
2. For all $\varepsilon>0$ there exists some $N\in \mathbb{N}$ such that for all $n>N$, $n$ knights can always be collected from the kingdom in time $2\sqrt{2}+\varepsilon$. (If we put the knights in two opposite corners it will take at least time $2\sqrt{2}$. So we can see that for large numbers of knights the time needed tends to $2\sqrt 2$.)
3. There exists some $p$ and some arrangement of $p$ knights such that collecting the knights from that arrangement takes at least as long as collecting any number of knights from any other arrangement. (So the problem actually has an answer!)
4. The times needed for small numbers of knights are:
   • 1 knight: $0$
   • 2 knights: $\sqrt 2$
   • 3 knights: $2\sqrt 2$
   • 4 knights: $2\sqrt 2$
   • 5 knights: $2+\sqrt 2$
5. Collecting $6$ knights (including the first one from the castle) can always be done in time $\frac{1}{2}+2\sqrt 2$, which is less than $2+\sqrt 2$, the time needed to collect $5$ knights.

I'll give the proofs when I get round to writing them up. (Hints: 1. splits the square into 4 and uses recursion, 2. splits the square into $k^2$ small squares and uses the pigeonhole principle to find a small square with enough knights that each one can be sent to each of the other squares, 3. uses 2 to produce an upper bound on $p$ and then uses a compactness argument to show that the bound is achieved, 4. just involves looking at each case in detail, and 5. splits the square into 4 and starts at the quarter with 2 knights in it)

Answer 2

I've already shown how you can force my other answer to fail. Hopefully this one will not have such an exploit.

• Step 1: First knight goes to the extreme house on the map. (Equivalent to just going the the north house if there is a house there.) (Maximum time $\frac{\sqrt{2}}{2}$) For a sometimes faster but harder to visualize strategy, instead have him go to the closest house and divide the entire map by the line along which he just travelled.

• Step 2: Old knight updates his map by drawing two lines to the houses on his left and right with a minimal angle between the such that all other houses on his map are between these lines. He then divides this map into two halves by bisecting this angle.

  Step 3: The old knight and the new knight proceed to the closest houses that is on their halves of the map.

  Step 4: Each knight follows steps 2 and 3 until he is awarded a map with no houses on it (and as a result no area). (Maximum time $2$)

  Step 5: Knight proceeds back to the castle. (Maximum time $\frac{\sqrt{2}}{2}$)

A potentially simpler to state step 2 would be to merely divide the current map into two equal halves along a line which passes through the current location. Unfortunately, already emptied space would remain on one of these maps making them less useful.

Step 2 is easier than is sounds as it is usually trimming an emptied triangle off a triangle then bisecting the new triangle.

This seems to work for every answer so far. One can imagine on map getting repeatedly divided into halves until nothing remains. It is area filling so it resolves any issues from house bunches (More at Does this strategy work?). No knight can be eliminated without removing at least one house and significantly reducing the number of houses. (what killed my other answer).

So far I've been completely unable to create a counter example or a proof. I welcome any input.

This (rather rough) diagram shows several moves of steps 2 and 3 for a random pattern of houses. the original map is bounded by black. They second map pink. This continues through green and blue. The houses are red and the path traveled is purple. Original location is black.

Answer 3

Here's an algorithm that doesn't always work (see a counter-example at the end). A slight adjustment (if a knight has no houses in his region he can take a portion of the other knight at his house's region) seems like it would fix this but it is not in this answer.

Step 1: Determine the lower bound:
If the knights are located at the 4 corners it will take: $\sqrt{(1/2)^2+(1/2)^2}+1+1+\sqrt{(1/2)^2+(1/2)^2} = 2+\sqrt{2}$.
The first one goes to a corner, he and the corner liver goes to the other two closest corner, someone of those 4 go to the last corner, and then everyone goes to the center.

Step 2: Show the lower bound works for any pattern:
Assume that there is a knight in a corner as this is the furthest point away from the king. If no one is further than that it should make the solution faster but more complicated. Use the following strategy as it is easier to show but slowest. For this algorithm one knight goes to a corner, they progress to the other corner and when everyone is notified, go to the castle. If every house is reached within 2 time after the first house is reached, they can all get back as they are at most $\sqrt{1/2}$ away.

Send the first knight to a corner call the corner in this direction North (N) for simplicity. You will then have two knights. Have them go to houses by this algorithm:

The knight divide the map into two regions by the East/West location of their current house. One knight goes to the northmost house which has not been visited, no other knight is headed towards, and is to the East of the current location. If multiple houses are the same distance north, he goes to the closer one. If there are no houses to the East he should go to the castle. The other knight follows the same algorithm but to the West. If there is a house directly South, it can count as either East or West but don't send both to the same house!.

Each time you visit a house, repeat the same algorithm with the two knights then at the house except no knight may move into a region which was excluded by one of his predecessors.

As no knight goes north again (until they are going to the castle) and the knights are interchangeable, the shortest path connecting the north and south corner houses via this algorithm will be taken. The maximum distance for this shortest path is $2$. This is because there is at least one path taken by which $\Delta S \ge |\Delta E|$ for every trip between houses. Similarly paths will go to the East most and West most houses that will never go in the other direction and, therefore, will have a path length of at most $2$.

There are likely faster algorithms than this for a particular setup but this one goes to all within the lower bound. Essentially each knight will take his map, draw two vertical lines based on his location and the history of his messenger, and go to the closest northmost house in his region. As the regions get smaller, they can be filled faster.

In the example above (which only shows the house covering part of the algorithm), purple is the paths knights take, blue the region dividers, and red the houses. If the houses not at the corners are $0.05$ from the corners and $22.5^\circ$ degrees from the edge, it takes $1.42$ units of time to go from N to S and $1.004$ units to get to either other corner.

This second example does not work by this algorithm. If the house near the south corner is slightly to the west of the house near the center (labeled). The limit of the time to complete this algorithm as d goes to zero is: $2\sqrt{.5}+1 \approx 2.4$. Several other knights are available to get to that last house before the knight that does but is not defined in the algorithm.

Answer 4

(Note: This answer is a work in progress. See relevant meta discussion if you would rather answers such as this did not exist.)

I don't like complicated things so I immediately chose to solve some simple variants of this problem before scaling up to the full deal. The simplest variant adds these assumptions:

1. No more than one house can occupy the same place
2. All houses are located on a straight line
3. The castle is located on the "end" of the line
4. There is no size restriction for the kingdom

This is a trivial variant of the problem and the solution is to send the original solider along the line until it reaches the last house on the line. Every other solider immediately returns to the castle. The time taken will be $t = 2x$ where $x$ is the distance between the castle and the house farthest away.

---

The next variant follows these assumptions instead:

1. No more than one house can occupy the same place
2. All houses are located on a straight line
3. The castle can be located anywhere on the line
4. There is no size restriction for the kingdom

To start digging for patterns, I used the following example (X is the castle; other letters are houses):

A---B-X--C

The optimal strategy will always be:

• Send Solider 1 ($SX$) to $B$, generating Solider 2 ($SB$)
• Send $SX$ to $A$, send $SB$ to $C$
• Send all soldiers home

The cost for this will be:

• $\overline{BX} + \max(\overline{AB}+\overline{AB}+\overline{BX}, \overline{BX}+\overline{CX}+\overline{CX})$
• $= \overline{BX} + \max(2*\overline{AB}+\overline{BX}, \overline{BX}+2*\overline{CX})$
• $= 2*\overline{BX} + \max(2*\overline{AB}+\overline{BX}, \overline{BX}+2*\overline{CX})$
• $= 2*(\overline{BX} + \max(\overline{AB}, \overline{CX}))$

The second example for this variant is:

A---B-X--C--D

The optimal strategy is no longer static and requires knowledge about the distance between the various houses. Specifically, there are two potential options.

OPTION 1

• $S_X$ to $B$
• $S_X$ to $A$, $S_B$ to $C$
• $S_X$, $S_A$, $S_C$ to X, $S_B$ to $D$
• Send all soldiers home

OPTION 2

• $S_X$ to $C$
• $S_X$ to $D$, $S_C$ to $B$
• $S_X$, $S_D$, $S_B$ to X, $S_C$ to $A$
• Send all soldiers home

Therefore, the optimal time will be:

$\min(\overline{XB}+\max(2*\overline{AB}+\overline{XB},\overline{XB}+2*\overline{XC}+2*\overline{CD}), \overline{XC}+\max(2*\overline{CD}+\overline{XC},\overline{XC}+2*\overline{XB}+2*\overline{AB}))$

$= \min(\max(2*\overline{AB}+2*\overline{XB},2*\overline{XB}+2*\overline{XC}+2*\overline{CD}), \max(2*\overline{CD}+2*\overline{XC},2*\overline{XC}+2*\overline{XB}+2*\overline{AB}))$
$= 2*\min(\max(\overline{AB}+\overline{XB},\overline{XB}+\overline{XC}+\overline{CD}), \max(\overline{CD}+\overline{XC},\overline{XC}+\overline{XB}+\overline{AB}))$
$= 2*\min(-\min(-\overline{AB}-\overline{XB},-\overline{XB}-\overline{XC}-\overline{CD}), -\min(-\overline{CD}-\overline{XC},-\overline{XC}-\overline{XB}-\overline{AB}))$
$= 2*(\min(\min(-\overline{CD}-\overline{XC},-\overline{XC}-\overline{XB}-\overline{AB}), \min(-\overline{AB}-\overline{XB},-\overline{XB}-\overline{XC}-\overline{CD}))-\min(-\overline{AB}-\overline{XB},-\overline{XB}-\overline{XC}-\overline{CD})-\min(-\overline{CD}-\overline{XC},-\overline{XC}-\overline{XB}-\overline{AB}))$
$= 2*(\min(-\overline{CD}-\overline{XC},-\overline{XC}-\overline{XB}-\overline{AB}, -\overline{AB}-\overline{XB},-\overline{XB}-\overline{XC}-\overline{CD})-\min(-\overline{AB}-\overline{XB},-\overline{XB}-\overline{XC}-\overline{CD})-\min(-\overline{CD}-\overline{XC},-\overline{XC}-\overline{XB}-\overline{AB}))$
$= 2*(\min(-\overline{XC}-\overline{XB}-\overline{AB},-\overline{XB}-\overline{XC}-\overline{CD})-\min(-\overline{AB}-\overline{XB},-\overline{XB}-\overline{XC}-\overline{CD})-\min(-\overline{CD}-\overline{XC},-\overline{XC}-\overline{XB}-\overline{AB}))$
$= 2*(-\max(\overline{XC}+\overline{XB}+\overline{AB},\overline{XB}+\overline{XC}+\overline{CD})+\max(\overline{AB}+\overline{XB},\overline{XB}+\overline{XC}+\overline{CD})+\max(\overline{CD}+\overline{XC},\overline{XC}+\overline{XB}+\overline{AB}))$
$= 2*(\overline{XB}+\overline{XC}+\max(\overline{AB},\overline{XC}+\overline{CD})+\max(\overline{CD},\overline{XB}+\overline{AB})-\overline{XC}-\overline{XB}-\max(\overline{AB},\overline{CD}))$

$= 2*(\max(\overline{AB},\overline{XC}+\overline{CD})+\max(\overline{CD},\overline{XB}+\overline{AB})-\max(\overline{AB},\overline{CD}))$

Using some quick numbers:

$\overline{AB}=3, \overline{BX}=1, \overline{XC}=2, \overline{CD}=2$ then:

• $t=2*(\max(3,2+2)+\max(2,1+3)-\max(3,2))$
• $t=2*(4+4-3)=2*5=10$

Presumably this pattern can be extended to apply to all scenarios where the houses fit on a line. The second example for this variant is:

A---B-X--C--D---E

Similarly to the second example, we really only have two potential options:

OPTION 1

• $S_X$ to $B$
• $S_X$ to $A$, $S_B$ to $C$
• $S_X$, $S_A$, $S_C$ to X, $S_B$ to $D$
• $S_B$ to $E$
• Send all soldiers home

OPTION 2

• $S_X$ to $C$
• $S_X$ to $D$, $S_C$ to $B$
• $S_D$, $S_B$ to X, $S_X$ to $E$, $S_C$ to $A$
• Send all soldiers home

$t = \min(\overline{XB}+\max(\overline{XB}+2*\overline{AB},\overline{XB}+2*\overline{XC}+2*\overline{CD}+2*DE), \overline{XC}+\max(\overline{XC}+2*\overline{CD}+2*DE,\overline{XC}+2*\overline{XB}+2*\overline{AB}))$

If we treat $2*\overline{CD}+2*DE$ as $2*CE$ we get this form:

$t = \min(\overline{XB}+\max(\overline{XB}+2*\overline{AB},\overline{XB}+2*\overline{XC}+2*CE), \overline{XC}+\max(\overline{XC}+2*CE,\overline{XC}+2*\overline{XB}+2*\overline{AB}))$

Which matches our previous formula letting us jump to the reduced form:

$= 2*(\max(\overline{AB},\overline{XC}+CE)+\max(CE,\overline{XB}+\overline{AB})-\max(\overline{AB},CE))$ $= 2*(\max(\overline{AB},\overline{XC}+\overline{CD}+CE)+\max(\overline{CD}+CE,\overline{XB}+\overline{AB})-\max(\overline{AB},\overline{CD}+CE))$

At this point, one pattern does reveal itself. The only lines that really matter are $XA = \overline{XB}+\overline{AB}$, $XE = \overline{XC}+\overline{CD}+DE$, $\overline{XB}$ and $\overline{XC}$:

$= 2*(\max(\overline{AB},XE)+\max(\overline{CD}+CE,XA)-\max(\overline{AB},\overline{CD}+CE))$ $= 2*(\max(XA-\overline{XB},XE)+\max(XE-\overline{XC},XA)-\max(XA-\overline{XB},XE-\overline{XC}))$

This form seems likely to apply to all scenarios where the houses fit on a line. If we redefine the points in our example:

A1---A0-X--B0--B1---B2

We can write the formula as:

$= 2*(\max(XA-XA_0,\overline{XB})+\max(\overline{XB}-\overline{XB}_0,XA)-\max(XA-XA_0,\overline{XB}-\overline{XB}_0))$ where $XA=XA_0+A_0A_1+A_1A_2...$ and $\overline{XB}=\overline{XB}_0+B_0B_1+B_1B_2...$

This solution makes intuitive sense. The only real choice in a lined scenario is which direction to go first. Everything after that presents us with the trivial problem noted at the beginning of this post. The primary reason this formula works, however, is because we know that each $XA_0 ... XA_N$ is less than $B_0A_0 ... B_0A_N$ since any solider travelling from $B_0$ to $A_0$ has to pass through $X$. Therefore, this formula is only true if and only if $X$ perfectly splits two sections of the kingdom such that $X$ is always closer to each house in section $A$ compared to each house in section $B$ and the houses in each section form a line.

This last clause seems like a good place to extend our approach.

---

The next variant follows these assumptions instead:

1. No more than one house can occupy the same place
2. All houses exist in either section A or section B such that there is no line between a house in section A and a house in section B that is shorter than travelling from that house to the castle
3. All house in a given section $S$ follow the rule that $S_N$ is closer to $S_{N-1}$ and $S_{N+1}$ than any other houses or the castle unless the house is $S_0$
4. The castle can be located anywhere on the line
5. There is no size restriction for the kingdom

This set of assumptions removes the restriction that all houses exist on a line. It should make the math significantly more complicated but let's work it through.

A1   A0
           X   B0

This example moves $A_0$ and $A_1$ off of a line but preserves Assumption 3 which states that $A_1$ cannot be closer to $X$ than $A_0$. Let's see how this affects the math. The strategy is still the same:

• Send $S_X$ to $A_0$
• Send $S_X$ to $A_1$, send $SA_0$ to $S_{B_0}$
• Send all soldiers home

The two major differences are that $\overline{A_1X}$ no longer passes through $A_0$ and $\overline{A_0B_0}$ no longer passes through $X$. Here is our new formula:

• $\overline{XA_0} + \max(\overline{A_0A_1}+\overline{XA_1}, \overline{A_0B_0}+\overline{XB_0})$

Sadly, we don't get to reduce this at all since we don't get to replace $\overline{A_0B_0}$ with $\overline{XA_0} + \overline{XB_0}$. Let's extend section $A$ again and see what happens:

   A1   A0
              X   B0
A2

Is the optimal strategy still the same?

• Send $S_X$ to $A_0$
• Send $S_X$ to $A_1$, send $S_{A_0}$ to $B_0$
• Send $S_X$ to $A_2$, send $S_{A_0}$, $S_{A_1}$, $S_{B_0}$ home
• Send all soldiers home

I can see two alternative strategies and it may be tricky to determine if there is a case where one of those strategies outperforms this one. To make this easier to understand, I'll start using the notation $S_X \to A_0 \to A_1 \to A_2 \to X$ to describe one soldier's entire cycle. The above strategy expressed this way:

OPTION 1

• $S_X \to A_0 \to A_1 \to A_2 \to X$
• $S_{A_0} \to {B_0} \to X$
• $S_{A_1} \to X$
• $S_{A_2} \to X$
• $S_{B_0} \to X$

OPTION 2

• $S_X \to A_0 \to A_2 \to A_1 \to X$
• $S_{A_0} \to {B_0} \to X$
• $S_{A_1} \to X$
• $S_{A_2} \to X$
• $S_{B_0} \to X$

OPTION 3

• $S_X \to A_1 \to A_2 \to X$
• $S_{A_1} \to A_0 \to B_0 \to X$
• $S_{A_0} \to X$
• $S_{A_2} \to X$
• $S_{B_0} \to X$

How do we confirm that OPTIONS 2 & 3 are suboptimal for all positions of $A_0...A_N$?

Answer 5

The quickest method of message passing is usually broadcast - e.g. blowing a horn (or a relay of horns). All soldiers proceed to the castle simultaneously, so the last soldiers to arrive would be ones at the corners, which happens in time $\sqrt{0.5^2 + 0.5^2} = \sqrt{0.5}$.

If the king's soldier must notify everyone in person or by proxy (via other soldiers), then it depends on the distribution of houses.

Suppose the houses are arranged in expanding concentric squares around the castle, with the nearest a negligible distance away. Then the king's soldier goes first to the nearest 'ring' of houses, they go together to notify the next ring and so on, then return. In other words, the wave of soldiers moves out from the castle to the perimeter and then returns to the middle.

The longest path is from the castle to each corner of the square. To get there and back takes $2\sqrt{0.5}$ time. Everyone else travels a shorter distance, so this is also the total muster time.

Other search patterns will be needed if the distribution is sparse. The worst case might be 5 soldiers, 1 at the castle and the other 4 at the corners of the square. The king's soldier travels to 3 of them in turn, sending the first to notify the remaining soldier. This traverses the entire diagonal and 2 sides for the longest path time-wise, taking $2 + \sqrt{2}$ time. I suspect (but am prepared to stand corrected) that in all other cases, some soldiers can be recruited to reduce the total muster time.

Answer 6

I have written an algorithm to find minimal time for a specific kingdom.

1. We need to start by creating a table/map/lookup etc. of distances between every single pair of knights' houses.

2. We then need to generate all the permutations of the ways that the "news" can spread. i.e. Knight0 can go first to Knight1, but could also start by going to Knight2 etc.

   For the Knight at each extreme point example mentioned in the question, I used the notation 0(1(4),2(),3()) to mean:

   • Knight0 travelled to Knight1's house ($\frac{\sqrt{2}}{2}$)
   • Knight0 then travelled to Knight2's house ($1$)
   • Knight0 then travelled to Knight3's house ($1$)
   • Knight0 then travelled back to the castle ($\frac{\sqrt{2}}{2}$)

   Meanwhile, after Knight0 had travelled to Knight1's house,

   • Knight1 then travelled to Knight4's house ($1$)
   • Knight1 then travelled back to the castle ($\frac{\sqrt{2}}{2}$)

3. Once we have every possibility (336 for the above example), we need to calculate the time taken for each of those possibilities.

   For the above example, this would be the distance travelled by Knight0

   $$=\frac{\sqrt{2}}{2}+1+1+\frac{\sqrt{2}}{2} = 2 + \sqrt{2}$$

4. Once we have all the times of all the possibilities, we can then pick out the smallest time. (There is always more than one answer, as there is always a choice between two knights as to who visits the final knight before returning to the castle.)

I have written this algorithm in C#. It doesn't take a long time to run, but it cannot handle more than 6 Knights in a kingdom at the moment due to memory problems, but am working on that.

Using the algorithm, $2 + \sqrt{2}$ (or 3.414...) was output as the shortest distance in the above example. So far, randomly generating house positions for 6 Knights has produced no higher values.

Answer 7

It could be ~1.707 if the King helps.

s4 ----- s1 --+
 |       |    |
 |       |    |
 |   K   |    1
 |       |    |
 |       |    |
s3-------s2 --+

 |       |
 +---1---+

 Route taken
 K  -> S1 -> C  => 2 * SQR(((1/2)^2)+((1/2)^2))
 S0 -> S3 -> C  => 2 * SQR(((1/2)^2)+((1/2)^2)) (Aka the Soldier at the castle.)
 S1 -> S2 -> C  => 1 + SQR(((1/2)^2)+((1/2)^2))
 S2 -> C        =>     SQR(((1/2)^2)+((1/2)^2))
 S3 -> S4 -> C  => 1 + SQR(((1/2)^2)+((1/2)^2))
 S4 -> C        =>     SQR(((1/2)^2)+((1/2)^2))

Think about it this way the King and S0 take half of the list of house. King:= S1, S2 S0:= S3, S4 When they get to the first house. They cross that house of the list and first divide the list. If there is only one house on the list, the soldier who house it is go and fetches them, whilst the solider who originally brought the list heads back.

If there is only 1 additional soldier then the answer is 2 x Distance To Solider Eg There and back.