There are n paratroopers that simultaneously land on the plane R2 at independently and identically distributed positions, drawn from a distribution with density p. After landing, each paratrooper sleeps for independent and identically distributed times drawn from a distribution with density q on the positive real numbers. Before they wake up they are unable to take any action other than standing at the position they’ve landed on.
All paratroopers have two devices with them: an infinite precision radar and a detonation button, both of which can only be used once.
Using the radar tells them the exact positions of all other paratroopers relative to the current position of the radar user. (This is important—the paratroopers don’t have a compass to fix global directions such as north and south, and the radar only gives them information about relative positions.) This is the only way the paratroopers have of getting information about each other’s locations: aside from all of them being able to use the radar once, they have no other way of getting information about the location of other paratroopers even if they are standing on the same spot at the same time. The radar also doesn’t tell the user which paratroopers are at which locations, it only displays every location (possibly with multiplicity in the case of coincidence) at which there is a paratrooper.
The mission of the paratroopers is to press their detonation buttons all at the same location on the plane, though not necessarily at the same time. In other words, they all need to coordinate to go to the same point and press the detonation button once they are there, after which they are once again free to move as they please until the mission is either a success or a failure.
As a final technical detail, both density functions p and q are nonzero on their whole domain: this is R2 for p and R≥0 for q.
Assuming that the paratroopers can agree on a strategy before the mission begins, show that there is a strategy with which they can win almost surely (with probability equal to 1).
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.
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.)
Does the radar tell the paratroopers which other paratrooper is where, or just that there is some unknown paratrooper at each spot? In other words, are the paratroopers labeled on the radar?
They aren’t, otherwise the problem would be trivial since everyone could just agree on a person to be the target beforehand. I’ve edited the question to clear this up.
Pick the paratrooper nearest to centroid of all paratroopers and go directly towards their location in a straight line.
As you move, the location of the centroid will change, but which paratrooper is nearest won’t change. This is because your contribution to the average distance to that paratrooper will decrease by at least as much as your contribution to the average distance to any other paratrooper (because you’re moving in a straight line towards them).
(For n equals two, you have to pick one of you to move and one to stay fixed ahead of time. For n is three or more, except for in measure zero cases, there will be exactly one paratrooper who is nearest to the centroid, with no ties.)
EDIT: Actually I think there’s a flaw in this, but I don’t see which part is wrong. The reason I think there’s a flaw is that 1) I think the centroid moves away from you as you move towards it, but 2) it seems like my argument about the delta in your contribution to the average distance to a point applies to the location of the centroid itself, in which case the location of the centroid shouldn’t move as you move towards it. So there’s a contradiction...
EDIT2: Oh, I see the flaw. The centroid moves away from you in your direction of travel. The magnitude of the decrease in average distance to the centroid is maximized along the line connecting you and the centroid, but it’s negative for points in between you two. So, if you move towards a point that point’s distance from the center of mass is actually increasing the most, not the least.
EDIT3: Wait, actually, I think we can rescue this. What if we ignore the centroid altogether, and just choose the paratrooper that has the lowest average distance to each of the other paratroopers. Then I think maybe my original line of reasoning works?
EDIT4: I figured out what I was missing here — when you move towards a point, it’s true that the average distance of that point to all other points is shrinking at least as much as for any other point, as I was saying above, except for yourself. You might be moving closer to multiple points, meaning that you might become the point with the least average distance to other points!
So a general bit of advice for this problem is that the solution I have in mind is not trivial at all—it involves plenty of cleverness to come up with and some careful accounting of all of the edge cases to prove that it works. My solution is most likely not the simplest possible but my suspicion is that no solution is going to be as simple as the ones people have proposed thus far.
If you think you have a simple solution, your solution is probably wrong.
For n=2 the solution is easy, as others have pointed out.
For n≥3, everyone executes the following algorithm (which works even if everyone has to move at a constant speed):
when you wake up:
if (there exists a rational angle):
let angle = ABC
if you're B:
press the button, then stand still
else:
walk towards B in a straight line
press button at the point B
else:
let {B, C} be the pair of points with the shortest distance
let B be the one with the larger distance from the center of mass of points outside {B, C}
if you're B:
press the button, then stand still
if you're C:
walk towards B in a straight line
press button at the point B
walk back an infinitesimal distance
if neither:
say you're A
walk an infinitesimal distance to make angle ABC rational
then walk towards B in a straight line
press button at the point B
walk back an infinitesimal distance
The idea is similar to DaemonicSigil’s, except I use rational angles to communicate information instead of rational distances. Since my motion trajectories are more regular (piecewise linear), I face the additional problem that someone can wake up and use their radar while the first person to wake up is moving some fixed distance ε to make some angle rational. To fix this, I have everyone coordinate on a point which with probability 1 won’t be affected by small perturbations of the configuration of points.
The rest is just working out the technical details to ensure that this solution always works. To implement it as a proper algorithm I also have to say how to calculate these infinitesimal distances depending on the configuration of points displayed by the radar, and essentially you need to pick ε small enough such that even if everyone moves by that distance, the following two are left invariant almost surely:
The rank order relation of distances to the center of mass
The pair of points with the smallest distance between them
There’s going to be such a valid choice of ε almost surely, so this solution works.
I’m not seeing what the time delays have to do with it, nor the probability distributions. Cannot they win with certainty (not just almost surely) by going to the average of all their positions?
If one person wakes up and starts to go to the center of mass, his movement will change the location of the center of mass. If another person wakes up afterwards and uses the radar, he’ll see the center of mass at a different location and this will break the coordination.
Everyone uses the radar once they wake up. The two closest soldiers go towards each other on a straight line. Once they meet up and possibly wait for the other one to wake up they are free to visit all other soldiers in any order, when they are all together they can detonate. The important property is that the initial shortest distance is unique almost surely.
This doesn’t work (among other reasons) because the only way you have of finding out the position of the other paratroopers is to use the radar.
Suppose one of the two closest soldiers wakes up, uses his radar and heads towards the other paratrooper in the pair in a straight line. In the midst of this motion, suppose the other member of this pair also wakes up, uses his radar and executes the same strategy. Then they will fail to meet because the first paratrooper will be heading to the original position of the second, while the second will be heading towards some random point on the straight line joining them.
They won’t be able to tell if they’ve “met up” along the line because as I said the only way of getting any information about the position of the other paratroopers is by using the radar. Without it, you can’t even tell if you’re coincident (on the same point) with another paratrooper or not.
I see I should have read the instructions more carefully. I don’t quite understand all of your complaints though, if they can notice if they are on the same spot at the same time (they can’t I missed that) the strategy would work: the two soldiers would meet as they will not leave the line connecting them (walking towards some random point on it sure but still in the right direction)?
There are n paratroopers that simultaneously land on the plane R2 at independently and identically distributed positions, drawn from a distribution with density p. After landing, each paratrooper sleeps for independent and identically distributed times drawn from a distribution with density q on the positive real numbers. Before they wake up they are unable to take any action other than standing at the position they’ve landed on.
All paratroopers have two devices with them: an infinite precision radar and a detonation button, both of which can only be used once.
Using the radar tells them the exact positions of all other paratroopers relative to the current position of the radar user. (This is important—the paratroopers don’t have a compass to fix global directions such as north and south, and the radar only gives them information about relative positions.) This is the only way the paratroopers have of getting information about each other’s locations: aside from all of them being able to use the radar once, they have no other way of getting information about the location of other paratroopers even if they are standing on the same spot at the same time. The radar also doesn’t tell the user which paratroopers are at which locations, it only displays every location (possibly with multiplicity in the case of coincidence) at which there is a paratrooper.
The mission of the paratroopers is to press their detonation buttons all at the same location on the plane, though not necessarily at the same time. In other words, they all need to coordinate to go to the same point and press the detonation button once they are there, after which they are once again free to move as they please until the mission is either a success or a failure.
As a final technical detail, both density functions p and q are nonzero on their whole domain: this is R2 for p and R≥0 for q.
Assuming that the paratroopers can agree on a strategy before the mission begins, show that there is a strategy with which they can win almost surely (with probability equal to 1).
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.
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.)
Does the radar tell the paratroopers which other paratrooper is where, or just that there is some unknown paratrooper at each spot? In other words, are the paratroopers labeled on the radar?
They aren’t, otherwise the problem would be trivial since everyone could just agree on a person to be the target beforehand. I’ve edited the question to clear this up.
Gotcha, in that case:
Pick the paratrooper nearest to centroid of all paratroopers and go directly towards their location in a straight line.
As you move, the location of the centroid will change, but which paratrooper is nearest won’t change. This is because your contribution to the average distance to that paratrooper will decrease by at least as much as your contribution to the average distance to any other paratrooper (because you’re moving in a straight line towards them).
(For n equals two, you have to pick one of you to move and one to stay fixed ahead of time. For n is three or more, except for in measure zero cases, there will be exactly one paratrooper who is nearest to the centroid, with no ties.)
EDIT: Actually I think there’s a flaw in this, but I don’t see which part is wrong. The reason I think there’s a flaw is that 1) I think the centroid moves away from you as you move towards it, but 2) it seems like my argument about the delta in your contribution to the average distance to a point applies to the location of the centroid itself, in which case the location of the centroid shouldn’t move as you move towards it. So there’s a contradiction...
EDIT2: Oh, I see the flaw. The centroid moves away from you in your direction of travel. The magnitude of the decrease in average distance to the centroid is maximized along the line connecting you and the centroid, but it’s negative for points in between you two. So, if you move towards a point that point’s distance from the center of mass is actually increasing the most, not the least.
EDIT3: Wait, actually, I think we can rescue this. What if we ignore the centroid altogether, and just choose the paratrooper that has the lowest average distance to each of the other paratroopers. Then I think maybe my original line of reasoning works?
EDIT4: I figured out what I was missing here — when you move towards a point, it’s true that the average distance of that point to all other points is shrinking at least as much as for any other point, as I was saying above, except for yourself. You might be moving closer to multiple points, meaning that you might become the point with the least average distance to other points!
So a general bit of advice for this problem is that the solution I have in mind is not trivial at all—it involves plenty of cleverness to come up with and some careful accounting of all of the edge cases to prove that it works. My solution is most likely not the simplest possible but my suspicion is that no solution is going to be as simple as the ones people have proposed thus far.
If you think you have a simple solution, your solution is probably wrong.
Here is my solution:
For n=2 the solution is easy, as others have pointed out.
For n≥3, everyone executes the following algorithm (which works even if everyone has to move at a constant speed):
The idea is similar to DaemonicSigil’s, except I use rational angles to communicate information instead of rational distances. Since my motion trajectories are more regular (piecewise linear), I face the additional problem that someone can wake up and use their radar while the first person to wake up is moving some fixed distance ε to make some angle rational. To fix this, I have everyone coordinate on a point which with probability 1 won’t be affected by small perturbations of the configuration of points.
The rest is just working out the technical details to ensure that this solution always works. To implement it as a proper algorithm I also have to say how to calculate these infinitesimal distances depending on the configuration of points displayed by the radar, and essentially you need to pick ε small enough such that even if everyone moves by that distance, the following two are left invariant almost surely:
The rank order relation of distances to the center of mass
The pair of points with the smallest distance between them
There’s going to be such a valid choice of ε almost surely, so this solution works.
I’m not seeing what the time delays have to do with it, nor the probability distributions. Cannot they win with certainty (not just almost surely) by going to the average of all their positions?
If one person wakes up and starts to go to the center of mass, his movement will change the location of the center of mass. If another person wakes up afterwards and uses the radar, he’ll see the center of mass at a different location and this will break the coordination.
I see, that’s where the times come into it. They have no way of knowing when everyone has woken and used their radar.
Everyone uses the radar once they wake up. The two closest soldiers go towards each other on a straight line. Once they meet up and possibly wait for the other one to wake up they are free to visit all other soldiers in any order, when they are all together they can detonate. The important property is that the initial shortest distance is unique almost surely.
This doesn’t work (among other reasons) because the only way you have of finding out the position of the other paratroopers is to use the radar.
Suppose one of the two closest soldiers wakes up, uses his radar and heads towards the other paratrooper in the pair in a straight line. In the midst of this motion, suppose the other member of this pair also wakes up, uses his radar and executes the same strategy. Then they will fail to meet because the first paratrooper will be heading to the original position of the second, while the second will be heading towards some random point on the straight line joining them.
They won’t be able to tell if they’ve “met up” along the line because as I said the only way of getting any information about the position of the other paratroopers is by using the radar. Without it, you can’t even tell if you’re coincident (on the same point) with another paratrooper or not.
I see I should have read the instructions more carefully. I don’t quite understand all of your complaints though, if they can notice if they are on the same spot at the same time (they can’t I missed that) the strategy would work: the two soldiers would meet as they will not leave the line connecting them (walking towards some random point on it sure but still in the right direction)?