Cool problem, I think I may have (at least a sketch of) a solution. The way the paratroopers are allowed to move wasn’t specified in the problem, but it would be too easy if they were allowed to just teleport around to arbitrary locations, so I’ll assume that their movement has to be described by continuous functions.
Everyone will head towards a point chosen by the first paratrooper to wake up. Thus the first paratrooper to wake up must somehow “mark” himself. Further, he must mark himself instantly, right after waking up. This seems impossible, since the only available information he can mark himself with is his position relative to the others. Moving anywhere takes time doesn’t it? It’s not obvious how you can mark yourself instantly if you’re constrained to move in a continuous manner. In any case, all the troopers will use their infinite precision radar as soon as they wake up, so that they can find out instantly whether or not they are the first trooper, and mark themselves instantly if it turns out they are. (You can check if you’re the first trooper by checking the map your radar gives you to see if anyone else is marked already. If no one is, you’re first.)
My general solution works only for n≥3, so as a warmup, let’s solve n=2. In this case, there is a line between the troopers. My chosen strategy will never have the troopers move off that line, so this reduces to a problem in R. With probability 1, the troopers will be an irrational distance apart. The first trooper to wake up will instantly mark himself by moving to be a rational distance from the other trooper. How to accomplish this is kind of tricky. He can pick a particular nearby rational point to move to, but it will take him finite time to get there by moving continuously, and the other trooper might wake up during that time.
The trick is a construction very similar to how the Minkowski Question Mark Function is constructed. I recommend taking a look at that Wikipedia article; there’s a good picture of the function, and it will help with understanding the following. The first trooper to wake up will move to the position of the second trooper, taking 1 second to do so, and then stay there. At a random time t (for any probability density function on t), ?(t) is rational. We’ll describe this by saying that ? is “rational almost everywhere”. Similarly, we’d like to construct a continuous function f(t):[0,1]→R that is a rational distance from the position of the second trooper almost everywhere. We’d also like f(0) to equal the starting position of the first trooper, and f(1) to equal the starting position of the second trooper.
Just as when constructing the Minkowski Question Mark Function, we proceed by recursively defining f on middle thirds. WLOG suppose f(0)<f(1). Pick a point a to be a rational distance from f(1) such that f(0)<a<f(1), and set f([1/3,2/3])=a. Pick a+ and a− to be a rational distance from f(1) such that f(0)<a−<a<a+<f(1). Set f([1/9,2/9])=a− and f([7/9,8/9])=a+. Proceed in this way, until f is defined everywhere on [0,1] except for the middle-thirds Cantor set. The values of f on those remaining Cantor set points are determined by the constraint that f must be continuous. Also, f(t) is a rational distance from f(1) whenever t is not in that Cantor set, that is to say, almost everywhere.
So now we have that the first trooper can instantly mark himself, by being a rational distance from the second trooper. So even if the second trooper wakes up while the first trooper is still moving, the first trooper manages to be a rational distance away with probability 1.
For this n=2 case, the rendezvous point will be the location of the second trooper to wake up. So overall, the first trooper wakes up, notices he is an irrational distance from the second trooper, and concludes he is the first to wake up. He makes a Minkowski-style movement to the location of the second trooper, and presses his detonation button once he gets there. The second trooper wakes up, notices that the first trooper is a rational distance away (this has probability 1, even if the first trooper is still in the process of moving), and concludes that his current location is the final destination. He presses his detonation button without moving anywhere.
Handling n≥3 is similar. The only tricky thing is that the first trooper must now mark not only himself, but the destination. He’ll mark the destination by choosing another trooper at random to be the destination, and moving to that trooper over the course of 1 second, always staying a rational distance away. Upon reaching the destination, he’ll press his detonation button, but continue moving without pausing, still always staying a rational distance away. He’ll stop moving at a position 1 unit north of the destination, after a total elapsed time of 2 seconds. He’ll mark himself, and distinguish himself from the destination by also staying at a distance of π times a rational number from some randomly chosen third paratrooper (we’ll call this third trooper the “tail”). (In 2 dimensions, this kind of Minkowski movement where you stay a rational and π times rational distance from 2 points is possible, details left as an exercise.) Anyone waking up and using their radar after the first trooper starts moving can tell (with probability 1) who is the first trooper, who is the destination, and who is the tail. The destination and tail have special instructions, everyone else will move towards the destination in a straight line at constant speed, press their detonation buttons as they pass over, and keep going in that direction at that speed afterwards. As for special instructions, the destination will press their button right away, and will never move. The tail will wait 2 seconds before moving, so he can be absolutely sure that the first trooper is 1 unit north of the destination. Then he will first move to the destination, making sure to stay π times a rational distance from the first trooper. He passes through and presses his detonation button, and ends at a position π+1 units north of the destination.
I think this solution works and it uses a lot of the same ideas as the solution I had in mind.
Here is a way you can try to improve the solution: what if the motion of the paratroopers has to be smooth and their maximum speed is bounded by an absolute constant K>0?
Isn’t moving after reaching the destination superfluous? Everyone can see where to go as the radar gives position with multiplicity and with probability 1 there won’t be another pair on the same point.
I get that, I am talking specifically about DaemonicSigil’s solution.
I understand that you need to move to know who is the tail and the first trooper, but knowing who those are is not necessary to know the destination, so I’m wondering why they keep moving.
Cool problem, I think I may have (at least a sketch of) a solution. The way the paratroopers are allowed to move wasn’t specified in the problem, but it would be too easy if they were allowed to just teleport around to arbitrary locations, so I’ll assume that their movement has to be described by continuous functions.
Everyone will head towards a point chosen by the first paratrooper to wake up. Thus the first paratrooper to wake up must somehow “mark” himself. Further, he must mark himself instantly, right after waking up. This seems impossible, since the only available information he can mark himself with is his position relative to the others. Moving anywhere takes time doesn’t it? It’s not obvious how you can mark yourself instantly if you’re constrained to move in a continuous manner. In any case, all the troopers will use their infinite precision radar as soon as they wake up, so that they can find out instantly whether or not they are the first trooper, and mark themselves instantly if it turns out they are. (You can check if you’re the first trooper by checking the map your radar gives you to see if anyone else is marked already. If no one is, you’re first.)
My general solution works only for n≥3, so as a warmup, let’s solve n=2. In this case, there is a line between the troopers. My chosen strategy will never have the troopers move off that line, so this reduces to a problem in R. With probability 1, the troopers will be an irrational distance apart. The first trooper to wake up will instantly mark himself by moving to be a rational distance from the other trooper. How to accomplish this is kind of tricky. He can pick a particular nearby rational point to move to, but it will take him finite time to get there by moving continuously, and the other trooper might wake up during that time.
The trick is a construction very similar to how the Minkowski Question Mark Function is constructed. I recommend taking a look at that Wikipedia article; there’s a good picture of the function, and it will help with understanding the following. The first trooper to wake up will move to the position of the second trooper, taking 1 second to do so, and then stay there. At a random time t (for any probability density function on t), ?(t) is rational. We’ll describe this by saying that ? is “rational almost everywhere”. Similarly, we’d like to construct a continuous function f(t):[0,1]→R that is a rational distance from the position of the second trooper almost everywhere. We’d also like f(0) to equal the starting position of the first trooper, and f(1) to equal the starting position of the second trooper.
Just as when constructing the Minkowski Question Mark Function, we proceed by recursively defining f on middle thirds. WLOG suppose f(0)<f(1). Pick a point a to be a rational distance from f(1) such that f(0)<a<f(1), and set f([1/3,2/3])=a. Pick a+ and a− to be a rational distance from f(1) such that f(0)<a−<a<a+<f(1). Set f([1/9,2/9])=a− and f([7/9,8/9])=a+. Proceed in this way, until f is defined everywhere on [0,1] except for the middle-thirds Cantor set. The values of f on those remaining Cantor set points are determined by the constraint that f must be continuous. Also, f(t) is a rational distance from f(1) whenever t is not in that Cantor set, that is to say, almost everywhere.
So now we have that the first trooper can instantly mark himself, by being a rational distance from the second trooper. So even if the second trooper wakes up while the first trooper is still moving, the first trooper manages to be a rational distance away with probability 1.
For this n=2 case, the rendezvous point will be the location of the second trooper to wake up. So overall, the first trooper wakes up, notices he is an irrational distance from the second trooper, and concludes he is the first to wake up. He makes a Minkowski-style movement to the location of the second trooper, and presses his detonation button once he gets there. The second trooper wakes up, notices that the first trooper is a rational distance away (this has probability 1, even if the first trooper is still in the process of moving), and concludes that his current location is the final destination. He presses his detonation button without moving anywhere.
Handling n≥3 is similar. The only tricky thing is that the first trooper must now mark not only himself, but the destination. He’ll mark the destination by choosing another trooper at random to be the destination, and moving to that trooper over the course of 1 second, always staying a rational distance away. Upon reaching the destination, he’ll press his detonation button, but continue moving without pausing, still always staying a rational distance away. He’ll stop moving at a position 1 unit north of the destination, after a total elapsed time of 2 seconds. He’ll mark himself, and distinguish himself from the destination by also staying at a distance of π times a rational number from some randomly chosen third paratrooper (we’ll call this third trooper the “tail”). (In 2 dimensions, this kind of Minkowski movement where you stay a rational and π times rational distance from 2 points is possible, details left as an exercise.) Anyone waking up and using their radar after the first trooper starts moving can tell (with probability 1) who is the first trooper, who is the destination, and who is the tail. The destination and tail have special instructions, everyone else will move towards the destination in a straight line at constant speed, press their detonation buttons as they pass over, and keep going in that direction at that speed afterwards. As for special instructions, the destination will press their button right away, and will never move. The tail will wait 2 seconds before moving, so he can be absolutely sure that the first trooper is 1 unit north of the destination. Then he will first move to the destination, making sure to stay π times a rational distance from the first trooper. He passes through and presses his detonation button, and ends at a position π+1 units north of the destination.
I think this solution works and it uses a lot of the same ideas as the solution I had in mind.
Here is a way you can try to improve the solution: what if the motion of the paratroopers has to be smooth and their maximum speed is bounded by an absolute constant K>0?
Isn’t moving after reaching the destination superfluous? Everyone can see where to go as the radar gives position with multiplicity and with probability 1 there won’t be another pair on the same point.
For some solutions it is. I wanted to allow it anyway in case someone found a solution which requires it.
I get that, I am talking specifically about DaemonicSigil’s solution. I understand that you need to move to know who is the tail and the first trooper, but knowing who those are is not necessary to know the destination, so I’m wondering why they keep moving.
Ah, then yes, I think it’s superfluous.