Here is a kind of long solution that I think works (ETA: for the case n=3)
This was posted on our house puzzle slack before, it was one of the few problems that wasn’t solved though it didn’t get as much love as some of the harder problems.
I’d expect that a fairly large fraction of working mathematicians wouldn’t get it in 2 hours (and similarly for most of the hard Putnam problems) though I may be underestimating their ability to solve contest-like problems or it may have a simpler solution than this one.
Every paratrooper will use their radar as soon as they wake.
Suppose I see the points A, B, C. If ABC are collinear, then I’ll walk to the median paratrooper, detonate, and then stay in place. In particular, if two paratroopers are at the same location, then I walk towards that location and detonate.
Otherwise, we’ll assume that ABC has distinct edge lengths. (We’ll revisit this assumption and see if we can ensure it at the end.)
So suppose WLOG that the edge lengths are AB < BC < AC. We are going to try to end up at paratrooper A. I’m going to hold fixed the names A, B, C at this point, from my perspective.
Note that other paratroopers may assign the labels A, B, C differently. But we’ll guarantee that they don’t, by ensuring everyone takes paths that preserve the ordering AB < AC < BC until everyone is on the same line. (And that once everyone is on the same line, A is in between B and C, and everyone who has already used their radar is already trying to get to A. There are some more technicalities but I think this is fine.)
I’ll assign coordinates so that A is at (0, 0) and B is at (0, 1), and I’m at a location (x, y) with y > 0. Note that different paratroopers my assign coordinates differently depending on when they wake up.
If I am paratrooper A, I simply detonate and stay still.
If I am paratrooper C, I am going to first walk north 1 unit, then west 1 unit, then south until I reach the x-axis, then east to paratrooper A. Then I detonate and stand still. I’ll maintain a constant speed of 1 unit per hour over that whole path.
If I’m paratrooper B, I am going to move very quickly to paratrooper A’s position while preserving AB < AC < AC. Then I’ll detonate and stand still.
If C is at (x, y) with x < 0, then I just walk straight to A. It’s easy to see this maintains our invariant no matter how C moves. So assume that C is at (x, y) with x > 0.
Then I pick a path which is strictly outside of circle CA and strictly inside of AC (i.e. never touches the boundaries except at the endpoint of A). I think it’s easy to see that such a path exists but I don’t like geometry.
I then walk along this path extremely quickly. That is, I have an upper bound for the speed at which paratrooper C will ever walk (in 1 hour they will cover the max distance between me and paratrooper A), and I know that paratrooper A will never move at all as long as the rest of the scheme goes according to plan. That means there is a maximum speed at which the circles AC and CA can shift. Since my path was strictly in the interior, if I walk fast enough I can ensure that I remain in the safe region until possibly at the very end of my path.
To make the end of my path fine I just need to be careful about how I approach A. Fortunately, I know that if C is moving, it will either be north or west (since once it’s done moving west we’ll have x < 0). That means if I approach A while moving northwest, the last part of my trajectory will also be safe. This leads to a slightly more constrained geometry problem: I need a path from (1, 0) to (0, 0) that approaches (0, 0) from the southeast quadrant, while staying inside of AC and outside of CA. But this is still pretty easy.
Now we can check that everything works out, assuming my claims about geometry are OK:
The initial configuration ABC is scalene with probability 1.
We’ll maintain the invariant that either (i) AB < AC < BC, (ii) ABC are collinear with A in between B and C (with perhaps A and B coincident).
Therefore paratrooper A will never move.
Paratrooper C’s trajectory maintains this property until B wakes up.
If paratrooper B wakes up while the points aren’t collinear, then they are able to walk a path that preserves the property no matter who C is moving, until A and B are on top of one another. After that point, we’ve won.
If B wakes up while the points are collinear, they they just start walking towards A, which preserves the invariant.
This is kind of fiddly so I likely overlooked some things, but I’d be surprised if the basic idea didn’t work. It seems like we only need either (i) the waking times aren’t equal, or (ii) the paratroopers can randomize the timing of their radar use, (iii) the paratroopers can walk a short distance in a random direction before using their radar, (iv) the initial configuration isn’t an isosceles triangle. I’m very unclear on whether it’s possible to handle the case of equilateral triangles where multiple people can wake up simultaneously and we don’t have access to randomization, but I don’t see an impossibility proof.
Note on this solution (potential bug in the solution / problem statement, depending on exactly what you meant, this would also break the other proposed solution):
I need to assume that either the points are in generic position or the wakeup times are unequal, which follows from them being continuous w.r.t. lebesgue measure, but it sounds like you are assuming a lower-bound on the probabilities rather than an upper bound. But I don’t see how “nonzero density everywhere” can possibly be useful: if there is a distribution of locations/times for which the problem is impossible, then I could just take an equal mixture of that distribution and the uniform distribution, which would also guarantee a non-zero probability of failure (since it has a 1/26 probability of drawing all quantities from the failure distribution) and also has non-zero density everywhere.
My solution works if the paratroopers can randomly choose when to use their radar such that they have 0 probability of using it at the same time. In that case if I use my radar and see an isosceles triangle, I can immediately start moving to make it scalene (e.g. by walking very slowly for 1 second in an appropriate direction). No matter how close after me someone else wakes, they won’t see an isosceles triangle. So with this assumption we didn’t need any further restriction on the density of the paratroopers, in fact it seems like their locations can just be chosen adversarially. Not sure if you intended to allow this.
Small bug in solution that is easy to patch:
When charting paratrooper B’s path, I said that paratrooper C could only be walking north or west. This was needed for analyzing whether paratrooper B would potentially end up inside the circle AC no matter how fast they walk, which might cause paratrooper A to choose the wrong Schelling point if they wake up during that short interval. But if paratroooper C wakes up in the middle of paratrooper B’s path, they could end up walking at a different angle in the northeast quadrant. This is a flaw in the proof but very easy to fix, here are two options:
Paratrooper B can ensure they always complete their path in <1 hour. And paratrooper C can stay still for 1 hour after using their radar. That ensures that if paratrooper C starts moving during paratrooper B’s path, they will be using stale information about paratrooper B’s location and will always start moving north.
If paratrooper B stays strictly in the southeast quadrant, then paratrooper C will only ever be moving northeast, due north, northwest, or due west. So we could just have paratrooper B chart a path that approaches A along a circular arc tangent to the y-axis.
Overall this entire part of the proof is annoying but seems incredibly loose.
I would currently guess that the problem is solvable with adversarially chosen points / wakeup times, and with no access to randomization. But it’s very unclear and it involves a much more annoying argument.
The assumption that the densities are nonzero everywhere is supposed to rule out some kinds of solutions. The assumption of absolute continuity with respect to the Lebesgue measure is to make sure any event like “all three points forming an equilateral triangle” will be of null probability, while the nonzero density assumption is to make sure that the positions/arrival times aren’t compactly supported.
Without this assumption (and with the requirement of a maximum speed) there are alternative ways to solve the problem. For example, if the arrival times are compactly supported then in some solutions a “pivot player” around which everyone coordinates can determine some finite amount of time to wait before starting to move to ensure everyone else already used the radar and got his original position. There’s something similar with the original positions if we assume a speed limit on how fast people can move.
In short, this is an assumption that’s meant to make the problem harder, not easier. I mention it explicitly so people don’t give solutions which work in the special case of when some distributions are compactly supported.
The exact assumptions I mentioned in the problem are far from tight, and there are a variety of different solutions that work against adversaries of different capabilities. Any solution you end up finding will probably still work under more restrictive assumptions than the ones I outlined in the OP.
This solution only works for n=3. I think it’s probably possible to adapt it to n>3, but it’s clearly much more complicated and I suspect a different approach is easier.
Compared to DaemomicSigil’s solution, I think the main advantages in the n=3 case are:
My approach works for almost all configurations of initial points even if two people wake up simultaneously. It also works for adversarially chosen configurations of points as long as no two people wake up at the same time. So in that way it only uses one of the two assumptions instead of both of them.
It also works for noisy radars and constant movement speeds (I stated a version where people move arbitrarily fast, but it’s easy to just have paratrooper C move slowly enough that paratrooper B never needs to move at a speed >1 unit/time), with the error probability dropping continuously to 0 as radar error goes to 0, instead of leaning hard on the infinite-precision assumption.
(ETA: actually this version checks whether ABC are exactly collinear so doesn’t quite work, but this is very nonessential and you could have an analogous solution where the paratroopers’ movements are continuous functions of their observations.)
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.)
Here is a kind of long solution that I think works (ETA: for the case n=3)
This was posted on our house puzzle slack before, it was one of the few problems that wasn’t solved though it didn’t get as much love as some of the harder problems.
I’d expect that a fairly large fraction of working mathematicians wouldn’t get it in 2 hours (and similarly for most of the hard Putnam problems) though I may be underestimating their ability to solve contest-like problems or it may have a simpler solution than this one.
Every paratrooper will use their radar as soon as they wake.
Suppose I see the points A, B, C. If ABC are collinear, then I’ll walk to the median paratrooper, detonate, and then stay in place. In particular, if two paratroopers are at the same location, then I walk towards that location and detonate.
Otherwise, we’ll assume that ABC has distinct edge lengths. (We’ll revisit this assumption and see if we can ensure it at the end.)
So suppose WLOG that the edge lengths are AB < BC < AC. We are going to try to end up at paratrooper A. I’m going to hold fixed the names A, B, C at this point, from my perspective.
Note that other paratroopers may assign the labels A, B, C differently. But we’ll guarantee that they don’t, by ensuring everyone takes paths that preserve the ordering AB < AC < BC until everyone is on the same line. (And that once everyone is on the same line, A is in between B and C, and everyone who has already used their radar is already trying to get to A. There are some more technicalities but I think this is fine.)
I’ll assign coordinates so that A is at (0, 0) and B is at (0, 1), and I’m at a location (x, y) with y > 0. Note that different paratroopers my assign coordinates differently depending on when they wake up.
If I am paratrooper A, I simply detonate and stay still.
If I am paratrooper C, I am going to first walk north 1 unit, then west 1 unit, then south until I reach the x-axis, then east to paratrooper A. Then I detonate and stand still. I’ll maintain a constant speed of 1 unit per hour over that whole path.
If I’m paratrooper B, I am going to move very quickly to paratrooper A’s position while preserving AB < AC < AC. Then I’ll detonate and stand still.
If C is at (x, y) with x < 0, then I just walk straight to A. It’s easy to see this maintains our invariant no matter how C moves. So assume that C is at (x, y) with x > 0.
Then I pick a path which is strictly outside of circle CA and strictly inside of AC (i.e. never touches the boundaries except at the endpoint of A). I think it’s easy to see that such a path exists but I don’t like geometry.
I then walk along this path extremely quickly. That is, I have an upper bound for the speed at which paratrooper C will ever walk (in 1 hour they will cover the max distance between me and paratrooper A), and I know that paratrooper A will never move at all as long as the rest of the scheme goes according to plan. That means there is a maximum speed at which the circles AC and CA can shift. Since my path was strictly in the interior, if I walk fast enough I can ensure that I remain in the safe region until possibly at the very end of my path.
To make the end of my path fine I just need to be careful about how I approach A. Fortunately, I know that if C is moving, it will either be north or west (since once it’s done moving west we’ll have x < 0). That means if I approach A while moving northwest, the last part of my trajectory will also be safe. This leads to a slightly more constrained geometry problem: I need a path from (1, 0) to (0, 0) that approaches (0, 0) from the southeast quadrant, while staying inside of AC and outside of CA. But this is still pretty easy.
Now we can check that everything works out, assuming my claims about geometry are OK:
The initial configuration ABC is scalene with probability 1.
We’ll maintain the invariant that either (i) AB < AC < BC, (ii) ABC are collinear with A in between B and C (with perhaps A and B coincident).
Therefore paratrooper A will never move.
Paratrooper C’s trajectory maintains this property until B wakes up.
If paratrooper B wakes up while the points aren’t collinear, then they are able to walk a path that preserves the property no matter who C is moving, until A and B are on top of one another. After that point, we’ve won.
If B wakes up while the points are collinear, they they just start walking towards A, which preserves the invariant.
This is kind of fiddly so I likely overlooked some things, but I’d be surprised if the basic idea didn’t work. It seems like we only need either (i) the waking times aren’t equal, or (ii) the paratroopers can randomize the timing of their radar use, (iii) the paratroopers can walk a short distance in a random direction before using their radar, (iv) the initial configuration isn’t an isosceles triangle. I’m very unclear on whether it’s possible to handle the case of equilateral triangles where multiple people can wake up simultaneously and we don’t have access to randomization, but I don’t see an impossibility proof.
Note on this solution (potential bug in the solution / problem statement, depending on exactly what you meant, this would also break the other proposed solution):
I need to assume that either the points are in generic position or the wakeup times are unequal, which follows from them being continuous w.r.t. lebesgue measure, but it sounds like you are assuming a lower-bound on the probabilities rather than an upper bound. But I don’t see how “nonzero density everywhere” can possibly be useful: if there is a distribution of locations/times for which the problem is impossible, then I could just take an equal mixture of that distribution and the uniform distribution, which would also guarantee a non-zero probability of failure (since it has a 1/26 probability of drawing all quantities from the failure distribution) and also has non-zero density everywhere.
My solution works if the paratroopers can randomly choose when to use their radar such that they have 0 probability of using it at the same time. In that case if I use my radar and see an isosceles triangle, I can immediately start moving to make it scalene (e.g. by walking very slowly for 1 second in an appropriate direction). No matter how close after me someone else wakes, they won’t see an isosceles triangle. So with this assumption we didn’t need any further restriction on the density of the paratroopers, in fact it seems like their locations can just be chosen adversarially. Not sure if you intended to allow this.
Small bug in solution that is easy to patch:
When charting paratrooper B’s path, I said that paratrooper C could only be walking north or west. This was needed for analyzing whether paratrooper B would potentially end up inside the circle AC no matter how fast they walk, which might cause paratrooper A to choose the wrong Schelling point if they wake up during that short interval. But if paratroooper C wakes up in the middle of paratrooper B’s path, they could end up walking at a different angle in the northeast quadrant. This is a flaw in the proof but very easy to fix, here are two options:
Paratrooper B can ensure they always complete their path in <1 hour. And paratrooper C can stay still for 1 hour after using their radar. That ensures that if paratrooper C starts moving during paratrooper B’s path, they will be using stale information about paratrooper B’s location and will always start moving north.
If paratrooper B stays strictly in the southeast quadrant, then paratrooper C will only ever be moving northeast, due north, northwest, or due west. So we could just have paratrooper B chart a path that approaches A along a circular arc tangent to the y-axis.
Overall this entire part of the proof is annoying but seems incredibly loose.
I would currently guess that the problem is solvable with adversarially chosen points / wakeup times, and with no access to randomization. But it’s very unclear and it involves a much more annoying argument.
Responding to the points in your note:
The assumption that the densities are nonzero everywhere is supposed to rule out some kinds of solutions. The assumption of absolute continuity with respect to the Lebesgue measure is to make sure any event like “all three points forming an equilateral triangle” will be of null probability, while the nonzero density assumption is to make sure that the positions/arrival times aren’t compactly supported.
Without this assumption (and with the requirement of a maximum speed) there are alternative ways to solve the problem. For example, if the arrival times are compactly supported then in some solutions a “pivot player” around which everyone coordinates can determine some finite amount of time to wait before starting to move to ensure everyone else already used the radar and got his original position. There’s something similar with the original positions if we assume a speed limit on how fast people can move.
In short, this is an assumption that’s meant to make the problem harder, not easier. I mention it explicitly so people don’t give solutions which work in the special case of when some distributions are compactly supported.
The exact assumptions I mentioned in the problem are far from tight, and there are a variety of different solutions that work against adversaries of different capabilities. Any solution you end up finding will probably still work under more restrictive assumptions than the ones I outlined in the OP.
I didn’t sanity check this solution yet but it’s a very different idea from what I had in mind. Does it only work in the case n=3?
This solution only works for n=3. I think it’s probably possible to adapt it to n>3, but it’s clearly much more complicated and I suspect a different approach is easier.
Compared to DaemomicSigil’s solution, I think the main advantages in the n=3 case are:
My approach works for almost all configurations of initial points even if two people wake up simultaneously. It also works for adversarially chosen configurations of points as long as no two people wake up at the same time. So in that way it only uses one of the two assumptions instead of both of them.
It also works for noisy radars and constant movement speeds (I stated a version where people move arbitrarily fast, but it’s easy to just have paratrooper C move slowly enough that paratrooper B never needs to move at a speed >1 unit/time), with the error probability dropping continuously to 0 as radar error goes to 0, instead of leaning hard on the infinite-precision assumption.
(ETA: actually this version checks whether ABC are exactly collinear so doesn’t quite work, but this is very nonessential and you could have an analogous solution where the paratroopers’ movements are continuous functions of their observations.)
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.)