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.
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.