For n = 4 the following trick works, but does not really have the same flavor as the n = 3 case:
If the soldiers land in a convex position (they are the corners of a convex quadrilateral) then meet at the intersection of the straight lines connecting the opposite soldiers. If they land in a triangle with one soldier in the interior, meet at the soldier in the middle.
Here the soldiers are forced to walk in straight lines.
It would not surprise me if there are tricks like these for some more n, but I don’t see a general strategy. I think there is something you can do for odd n that is quite different from the other solutions so far, but I have not checked it fully yet and worked out what it requires from the radar.
move on a straight line to the geometric median of the n points, i.e. the point that minimizes the sum of the distances to all the paratroopers?
Suppose that X was previously the geometric median, with a total distance of k, and I walk 1 unit towards X. Then the total distance from all points to X is now (k-1). Suppose for a contradiction that some other point X’ is now the median, i.e. it has a total distance k’ < (k-1). But by the triangle inequality, the total distance from X’ to the old set of points is at most k’ + 1 < k, contradicting the fact that X was the old median.
This suggests that moving on a straight line to the median never changes the median. So everyone will always see the same median and end up there.
We have trouble if there are multiple medians, but for n > 2 that seems like it should happen with probability 0. (And indeed, for n = 2 I think it’s easy to prove that there is no continuous strategy that works with probability 1.)
ETA: for n = 3 this corresponds to moving to the Fermat point. For n = 4 it corresponds exactly to your solution though I didn’t know this until looking at the wikipedia page for geometric median. For n=3 on a circle it corresponds to your solution. I think this was a situation where examining small cases led very directly to the general answer.
I thought of this idea before but I believed there was a problem with it which I can’t immediately see now—probably having to do with something that happens when multiple people are moving at once. If I can figure out what the problem was I’ll let you know.
EDIT: Yeah, I can’t see what the problem with it is. I think I convinced myself for some reason that this invariance would break if multiple people were moving at once but it doesn’t, so I think this works.
Yeah, to make this explicit we can just apply the same argument over and over again to show that moving any set of points any distance towards the median preserves the median.
Now I feel silly again for having such an ugly solution.
I do feel like we can probably generalize the super ugly solutions: it seems like we have plenty of degrees of freedom and so the challenge is about how to compactly describe a strategy rather than coping with any fundamental difficulty.
(But of course there may be some fundamental obstruction that just isn’t obvious yet.)
By the way, as a bit of trivia about the problem: I don’t know who came up with it but the person who gave the problem to me said that there is a nice solution which works for all n≥3 and only fails when n is even and everyone’s starting positions are collinear. I haven’t made much headway into finding such a solution yet.
I’m wondering how helpful it is to try cases with small n and hope a general pattern is going to emerge instead of trying to find a solution from scratch that at least works for all sufficiently large n. It’s difficult to decide which you want to spend your time doing.
Oh, I think I just found that solution in parallel (or at least I found a solution with exactly the same failure condition). It was directly inspired by PatrikN’s solution. (Although I didn’t realize until after writing it that it is literally a generalization of PatrikN’s solution.)
For n = 4 the following trick works, but does not really have the same flavor as the n = 3 case:
If the soldiers land in a convex position (they are the corners of a convex quadrilateral) then meet at the intersection of the straight lines connecting the opposite soldiers. If they land in a triangle with one soldier in the interior, meet at the soldier in the middle.
Here the soldiers are forced to walk in straight lines.
It would not surprise me if there are tricks like these for some more n, but I don’t see a general strategy. I think there is something you can do for odd n that is quite different from the other solutions so far, but I have not checked it fully yet and worked out what it requires from the radar.
Wait, can we just
move on a straight line to the geometric median of the n points, i.e. the point that minimizes the sum of the distances to all the paratroopers?
Suppose that X was previously the geometric median, with a total distance of k, and I walk 1 unit towards X. Then the total distance from all points to X is now (k-1). Suppose for a contradiction that some other point X’ is now the median, i.e. it has a total distance k’ < (k-1). But by the triangle inequality, the total distance from X’ to the old set of points is at most k’ + 1 < k, contradicting the fact that X was the old median.
This suggests that moving on a straight line to the median never changes the median. So everyone will always see the same median and end up there.
We have trouble if there are multiple medians, but for n > 2 that seems like it should happen with probability 0. (And indeed, for n = 2 I think it’s easy to prove that there is no continuous strategy that works with probability 1.)
ETA: for n = 3 this corresponds to moving to the Fermat point. For n = 4 it corresponds exactly to your solution though I didn’t know this until looking at the wikipedia page for geometric median. For n=3 on a circle it corresponds to your solution. I think this was a situation where examining small cases led very directly to the general answer.
That’s pretty cool, I wonder why I did not remember this concept.
I thought of this idea before but I believed there was a problem with it which I can’t immediately see now—probably having to do with something that happens when multiple people are moving at once. If I can figure out what the problem was I’ll let you know.
EDIT: Yeah, I can’t see what the problem with it is. I think I convinced myself for some reason that this invariance would break if multiple people were moving at once but it doesn’t, so I think this works.
Yeah, to make this explicit we can just apply the same argument over and over again to show that moving any set of points any distance towards the median preserves the median.
Now I feel silly again for having such an ugly solution.
I do feel like we can probably generalize the super ugly solutions: it seems like we have plenty of degrees of freedom and so the challenge is about how to compactly describe a strategy rather than coping with any fundamental difficulty.
(But of course there may be some fundamental obstruction that just isn’t obvious yet.)
By the way, as a bit of trivia about the problem: I don’t know who came up with it but the person who gave the problem to me said that there is a nice solution which works for all n≥3 and only fails when n is even and everyone’s starting positions are collinear. I haven’t made much headway into finding such a solution yet.
I’m wondering how helpful it is to try cases with small n and hope a general pattern is going to emerge instead of trying to find a solution from scratch that at least works for all sufficiently large n. It’s difficult to decide which you want to spend your time doing.
Oh, I think I just found that solution in parallel (or at least I found a solution with exactly the same failure condition). It was directly inspired by PatrikN’s solution. (Although I didn’t realize until after writing it that it is literally a generalization of PatrikN’s solution.)