32
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Forgive my ignorance but is there a constraint on the size of the houses? Can they not be made arbitrarily small and placed around the headman's house? Also, are we assuming that the headman takes no time to tell them about the gathering? $\endgroup$ – Jam Sep 3 '16 at 22:07
  • 1
    $\begingroup$ Also, could you elaborate on where $2+\sqrt{2}$ came from please? I've been trying it for about an hour now and if I've understood the problem correctly, it seems insanely hard. The fastest time I've got for houses at the corners of the unit square, centre $(0.5,0.5)$, so far is $1+2\sqrt{2}$, which is about $0.4$ more than your conjectured minimum. $\endgroup$ – Jam Sep 4 '16 at 0:10
  • 3
    $\begingroup$ @Jam When there are four houses, one at each corner: the headman goes first to one corner. Then the headman goes to one adjacent corner, and the resident of the first house goes to the other adjacent corner. Then (for simplicity) they both travel to the final corner (directly opposite of the first house.) Then everyone goes to the center. Total distance for headman: $2 + \sqrt 2$. $\endgroup$ – Yakov Shklarov Sep 4 '16 at 0:35
  • 2
    $\begingroup$ @kim123: Then what does "minimum is $2+\sqrt{2}$" mean? How can any one (non-zero) value be "the" answer? With just one house (or none), the time to gather everyone can be made arbitrarily smaller than any (non-zero) value you care to name. $\endgroup$ – Blue Sep 4 '16 at 7:05
  • 4
    $\begingroup$ We need the worst-case minimum. The best-case minimum is of course 0. $\endgroup$ – Ivan Neretin Sep 4 '16 at 7:11
3
+100
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ up to $2484$ means it should work for $0,1,2,3,4,\ldots,10,11,\ldots,2484$ villagers. Then you can use that one to make a strategy that works for $2485$ and more villagers. $\endgroup$ – mercio Dec 24 '16 at 10:12
  • $\begingroup$ I see now, thanks. $\endgroup$ – klm123 Dec 24 '16 at 10:26
0
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Imagine a spiral street. The distance between neighbouring turns being Epsilon. Houses are placed along the street in groups, the distance between groups being Epsilon/10. Each group (starting from the centre) has twice as many houses as the previous one. Everybody will just walk along the spiral, which can be made as long as needed. $\endgroup$ – klm123 Dec 24 '16 at 8:44
  • $\begingroup$ @klm123 Do they have to follow the street or could they just walk across the group? Also, they can split up, correct? $\endgroup$ – AlgorithmsX Dec 24 '16 at 8:49
  • $\begingroup$ what do you mean? The closest house will be always next house along the street, so your algorithm is forcing them to follow the street. May be i've missunderstood your algorithm? There are no constraints on their path in the problem condition itself. $\endgroup$ – klm123 Dec 24 '16 at 8:53
  • 1
    $\begingroup$ @klm123 My algorithm deals with the closest two houses at every meeting. So what would end up happening is the headman goes to the first house, then the headman goes to the second house, but thenew head man would go to the third house or move up a layer. You end up with four headmen, who go to the next four houses, etc. Eventually, you will always end up with more headmen than houses in the layer, so they will end up on another layer, which will end up with even more headmen, etc. $\endgroup$ – AlgorithmsX Dec 24 '16 at 8:59
  • $\begingroup$ This method is basically the method I asked about in the comments, which will fail every time you construct a village with a path where each next group of houses is twice as big, forcing all villagers to go to the next group each time, making the path and time as big as you like. This is resolved if you algorithm goes to the last group of houses (which is the one furthest away) and then you have enough villagers to take the rest from there. But your algorithm follows the CLOSEST house, not the OPTIMAL house as it should. $\endgroup$ – Vepir Dec 24 '16 at 9:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.