Quickest general strategy for village meeting

Question

Here is a problem, which neither I nor my friends (very experienced in solving things like this) can't solve. But it was used for a competition several years ago and one guy solved it there, as far as I know. Unfortunately the solution (and the guy) is lost.

You have a village. It is shaped as a square 1 by 1. The headman lives at the exact center of the square. Other houses are spread throughout the area of the village, and there is only one person per house. There are finite number of houses, they all have size 0 and everyone is aware of their placement.

The headman needs to organise a meeting, which collects all villagers. To do this, he goes to some other house and tells about the meeting, then go to the another, etc. Each villager is of course is guaranteed to be found in his house; once informed, he can either participate in the gathering or go to the meeting place at the headman house. They all travel at the speed of 1 and it takes 0 time to inform someone, once you've reached his(-er) house.

You need to find the minimum time $T_{\text{MinMax}}$ in which all villagers (including headman) can be collected at the centre of village, regardless of their number and initial placement.

The answer should come together with proof, i.e. you need to:
a) provide a strategy (who goes where) and prove that it will work for any village in time $t \le T_{\text{MinMax}}$
b) prove that for all other strategies there must a village, which will be "collected" in time $t \ge T_{\text{MinMax}}$.

Can anyone here solve it?

You can be sure, that $T_{\text{MinMax}} < \infty$. For example, the following strategy works in $T_{\text{Max}} < 3\sqrt{5}+3\sqrt{2}/2$:
1) The village area is divided into 4 square subareas 0.5 by 0.5.
2) The headman goes to a closest house in one subarea and assings its host to be a subheadman and asks him to do the same strategy in his subarea.
3) Then the headman goes to another, neighboring subarea and does the same. And repeats this with the rest of 2 subareas.
4) The headman comes back to the centre of village.
5) If some subarea has no houses inside the headman just skips it.
Let's say that in the worst case scenario it will take time $X$. Then for subheadmen it will take time $X/2$. The first subheadman is assigned in at most $\sqrt{2}/2$ time, the next in $\sqrt{2}/2+\sqrt{5}/2$ and the last in $\sqrt{2}/2+3\sqrt{5}/2$. Then at time $\sqrt{2}/2+3\sqrt{5}/2+X/2$ the last subarea is collected it its center and in $\sqrt{2}/4$ time it can be at village center. Which means $X < \sqrt{2}/2+3\sqrt{5}/2+X/2+\sqrt{2}/4$. So $T_{Max} = X < 3\sqrt{5}+3\sqrt{2}/2$.

It is easy to prove that $T_{\text{MinMax}} \ge 2+\sqrt{2}$ (consider a village with 4 houses in the corners), and I am almost sure that $T_{\text{MinMax}} = 2+\sqrt{2}$, it was the result of that guy from the competition.

Answer 1

This is not a complete answer, but a proof that a good enough partial strategy for "few" villagers is sufficient.

If the only villagers are only located in two groups at two opposite corners of the square, then the best (and only) strategy takes time $2\sqrt 2 < 2+\sqrt 2$.

Suppose you have a not necessarily optimal strategy that takes time at most $T \ge 2+\sqrt 2$ to solve any square. (we know that those exist by the divide and conquer argument presented in the question)

If you can reach out to $n^2-1$ enough people in time $\frac 12 \sqrt 2 + \varepsilon$, then you can separate the square in $n^2$ small squares, use the strategy on the small squares, then return to the center, which gives you a strategy with a total time of $(\frac 12 \sqrt 2 + \varepsilon) + (1- \frac 1{2n})\sqrt 2 + \frac 1n T + (\frac 12 - \frac 1 {2n}) \sqrt 2$.

As $n \to \infty$, this converges down to $2\sqrt 2 + \varepsilon$.
Under the assumption that given enough people in the square you can make $\varepsilon$ converge to $0$, you can start with any reasonable strategy and turn it into a new strategy whose worst time converges to $2\sqrt 2$ as the number of villagers gets large.

And from the previous worst-case examples, we know that $2\sqrt 2$, and the time $\frac 12 \sqrt 2 + \varepsilon$ are the best possible.

---

Now I will prove that if you have enough people in the square, then you can reach $N$ villagers in close to $\frac 12 \sqrt 2$ time.

Suppose you have $N$ villagers located in a tiny rectangular band of length $\frac 12 \sqrt 2$ and width $w$ and the headsman is starting in the middle of one extremities of the band.

Then by visiting every villager in order and branching, you can reach out to them in time at worst $\frac 12 \sqrt 2 + (\frac 12 + \lfloor \log_2(N) \rfloor )w$ : the amount of "zigzagging" needed is spread out to all the villagers thanks to the branching.

Finally, since the rectangle "covers" an angle of $2\arctan (w/\sqrt 2)$, you can cover a whole circle of radius $\sqrt 2/2$ with $\lceil \pi / \arctan (w / \sqrt 2) \rceil$ rectangles.

Therefore, if there is $\lceil \pi / \arctan (w / \sqrt 2) \rceil (N-1)+1$ villagers in total, then by the pigeonhole principle there is a band containing $N$ of them, and thus there is a way to reach out to $N$ villagers in time $\frac 12 \sqrt 2 + (\frac 12 + \lfloor \log_2(N) \rfloor )w$

---

Picking $n=5$ and $T = 2+\sqrt 2$ we obtain a recursive strategy that works in time $2+\sqrt 2$ as long as we can reach $24$ people in time $(16-5\sqrt 2)/10 = 0.892893\ldots$

To manage this we need bands with width $w = (8/5-\sqrt 2)/(\frac 12+4) = (16/5 - 2\sqrt 2)/9 = 0.041286\ldots$

So we need $108$ bands, and finally $2485$ villagers.

If you can devise a strategy that works in time $2+\sqrt 2$ for up to $2484$ villagers, then this method gives you a strategy that always works in this time.

Answer 2

I'll give the algorithm first, then the proof.

1. The headman goes to the house nearest to him.
2. The headman makes the villager at that house a temporary headman.
3. Both the people at the house then go to the nearest two houses that have an unnotified villager that no one else is going to (i.e. if two headsmen are closest to the same house, the closer one will get it) and make each villager they meet a temporary headman.
4. The last step repeats until there are no more houses for them to go to. For instance, if there are five houses besides the headman's house, the headsman would go to the first house, then they would go to the second and third houses, and then two of the three people would go to the fourth and fifth house, but one of them would go to the town center.

As you pointed out with the houses at the four corners, $T_{MinMax}\ge2+\sqrt2$. However, because of the branching nature of this problem, adding another person to the mix generally reduces the time it takes. Consider the four houses again, but this time, add another house directly North of the headman's house. With this algorithm, the headman will visit this house to the North, then they will split up to visit the upper corners, then one of the two people currently at each of the upper corners will go directly South to the remaining two people and the other two people who have been visited will go directly to the middle of the town. This will take $\frac12+\frac12+1+\frac{\sqrt2}2=2+\frac{\sqrt2}2$ time total. Now, you could actually put that fifth house anywhere and it would still produce something less than $2+\sqrt2$. To see this, draw the original path, add another house, and draw a new house. You should be able to see that the original path is longer than the new path.

This is basically a proof by induction. You have two cases when you add a house:

Case 1: By the time you reach the extra house in the algorithm, you have enough people to cover the extra house without losing any time. This would be in the case with six or seven houses, as instead of the two people at the corners going back to the center of town, they would go pick up the other people. We know that they will not add any time by the triangle inequality, as the point where they meet and the two houses form a triangle and it will always be faster for them to split up and visit both places than for one to go back to town and the other person to take care of them both.

Case 2: The extra house introduces a branching point, as in the case with five houses as detailed earlier. In this case, adding an extra house can decrease the time if it is placed near the beginning of the run and increase it if it is placed at the end of the run. The closer you put that first branching point to the center of town, the more time you save, but doing so allows you more room to put that last branching point house, which allows you to increase the time. The farther you put it from the center of town, the less time you save, but you don’t have to go out of your way as much because the last house must be closer to the last corner.

I feel as if I'm missing something, so if anyone sees any errors, please let me know.