For n = 3 you can exploit that the soldiers land on a circle for a neat solutions (meet at the soldier opposite to the longest circle segment walking along the arcs).
Oh man, that’s a way better solution. Seems like the same basic idea as mine (and converges to the same point), it just uses a super natural/clean set of trajectories instead of a handwaving argument that they must exist. It seems like you can probably also generalize that to n>3.
What’s your idea for generalizing this to n>3? Seems nontrivial to me.
I would be interested if something like this ended up working for large n because my solution leans very hard into the fact that the radar has infinite precision. I’ll post it in spoiler tags as a direct comment to the question so people can examine it, maybe it helps inspire some ideas.
Definitely doesn’t seem trivial to generalize, and I’m not sure if this is actually easier or harder than my solution.
It seems pretty interesting to find something that works for imprecise radar (in the sense that the error probability goes to 0 as radar error approaches 0).
Idea for n=4:
Let AB be the closest together pair of points. Let AC be the second-shortest distance involving either A or B. Then we all decide to approach point A.
If I’m not one of ABC, then I start by moving very far away from everyone else so that I won’t disrupt anything. Then I circle around until I get on the other side of A, and finally I approach A in such a way that I’m always closer to A than either B or C. This guarantees that A will remain the target point.
Hopefully it’s also possible to define approaches for B and C that preserve the fact that A is the target:
Point B would need to ensure that it’s always further than AC away from any non-A point, and that it’s always closer to A than the next-closest distance between a pair of points. So the valid region for B to walk in is a circle centered at A minus a bunch of circles centered at other points, and the question is whether those other circles can disconnect A and B
Point C needs to ensure that it never gets within AB of any non-B point, so its valid region is the complement of a union of circles, and the question is whether it can be disconnected from A.
I think I can use the same tricks from my original solution to avoid worrying about the possibility of multiple points moving at once. You still have to deal with the final instant of the trajectory just as before, which is another annoying geometry problem.
I’m maybe 50-50 that this exact approach would work, but it feels like something will.
If I wanted to solve in general I’d probably just keep trying larger and larger n and see if any general solution became clear.
Designating “one of the two points in the closest pair” breaks down immediately for n=5 since the target point could be surrounded from all sides by 3 other points, making it impossible for the 5th point to approach without messing up the target. My inclination would be to instead designate one of the vertices of the triangle with smallest max side length. (I.e. the one that is opposite the longest side fo that triangle). Then I think you are probably OK for n=5 but not larger n.
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 = 3 you can exploit that the soldiers land on a circle for a neat solutions (meet at the soldier opposite to the longest circle segment walking along the arcs).
Oh man, that’s a way better solution. Seems like the same basic idea as mine (and converges to the same point), it just uses a super natural/clean set of trajectories instead of a handwaving argument that they must exist. It seems like you can probably also generalize that to n>3.
What’s your idea for generalizing this to n>3? Seems nontrivial to me.
I would be interested if something like this ended up working for large n because my solution leans very hard into the fact that the radar has infinite precision. I’ll post it in spoiler tags as a direct comment to the question so people can examine it, maybe it helps inspire some ideas.
Definitely doesn’t seem trivial to generalize, and I’m not sure if this is actually easier or harder than my solution.
It seems pretty interesting to find something that works for imprecise radar (in the sense that the error probability goes to 0 as radar error approaches 0).
Idea for n=4:
Let AB be the closest together pair of points. Let AC be the second-shortest distance involving either A or B. Then we all decide to approach point A.
If I’m not one of ABC, then I start by moving very far away from everyone else so that I won’t disrupt anything. Then I circle around until I get on the other side of A, and finally I approach A in such a way that I’m always closer to A than either B or C. This guarantees that A will remain the target point.
Hopefully it’s also possible to define approaches for B and C that preserve the fact that A is the target:
Point B would need to ensure that it’s always further than AC away from any non-A point, and that it’s always closer to A than the next-closest distance between a pair of points. So the valid region for B to walk in is a circle centered at A minus a bunch of circles centered at other points, and the question is whether those other circles can disconnect A and B
Point C needs to ensure that it never gets within AB of any non-B point, so its valid region is the complement of a union of circles, and the question is whether it can be disconnected from A.
I think I can use the same tricks from my original solution to avoid worrying about the possibility of multiple points moving at once. You still have to deal with the final instant of the trajectory just as before, which is another annoying geometry problem.
I’m maybe 50-50 that this exact approach would work, but it feels like something will.
If I wanted to solve in general I’d probably just keep trying larger and larger n and see if any general solution became clear.
Designating “one of the two points in the closest pair” breaks down immediately for n=5 since the target point could be surrounded from all sides by 3 other points, making it impossible for the 5th point to approach without messing up the target. My inclination would be to instead designate one of the vertices of the triangle with smallest max side length. (I.e. the one that is opposite the longest side fo that triangle). Then I think you are probably OK for n=5 but not larger n.
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.)