19
$\begingroup$

A troop of N immortal point mass soldiers (with N >= 3) are attempting to infiltrate Fogland (an infinite 2-dimensional plane covered in fog).
They will jump out of an airplane and, after being buffeted by the winds, will each land in an independent random location in Fogland.
Unfortunately, being point mass soldiers in a foggy country, they will not be able to see each other, and will not even know if they are in the precise same location as each other.
The landing will knock them unconscious for a random amount of time. Each soldier carries two devices, both of which are only good enough for a single use.
The first device is a GPS device, which will tell them the instantaneous distances and directions of the other point mass soldiers at the time of its use.
The second device is a detonator.
The only way that the infiltration can succeed is if all N soldiers activate their detonators at the same location (but not necessarily at the same time).

For each value of N, come up with a strategy that the soldiers can use for the infiltration to succeed with probability 1. (You can specify probability 0 conditions which will cause the infiltration to fail)

Inviolable Statements:
* The soldiers have a finite speed limit beyond which they cannot travel.
* Given any region on the plane with non-zero area, the probability that any given soldier lands in that region is non-zero.
* Given any non-zero period of time after the landing, the probability that any gien soldier awakes during that period is non-zero.
* The only means of communication the point mass soldiers have with each other is seeing each others locations on the GPS device.

NB: infinite 2d planes don't have magnetic poles. Therefore there is no such concept as "North"

Comment I got this puzzle from a colleague who used to send the team a brain teaser every week. This was one of them and came with the following note: "WARNING: this week's brainteaser is ridiculously difficult. I know few people who have independently worked out a solution for any N, and nobody who has independently worked out a solution for all N."
I found an answer for N=3 and he accepted it (different from the answer that was provided here), but I never knew if it was what he expected and if it can be generalized. Therefore, I am posting my answer and will give a bounty if someone manages to do it. Good luck!

$\endgroup$
8
  • $\begingroup$ Are we to assume that each soldier can get to any location of their choosing? Or at least any location relative to the position where they start? $\endgroup$
    – Gareth McCaughan
    Sep 28, 2017 at 21:17
  • 1
    $\begingroup$ Does a soldier who detonates their device remain or do they vanish? It's not clear whether detonation has any effect (other than to solve the problem)? Also can the soldiers (i) tell themselves apart (eg can you have a rule that soldier 1 does something...) (ii) tell each other apart on the GPS? $\endgroup$ Sep 28, 2017 at 21:44
  • 5
    $\begingroup$ Can we acknowledge how mind-boggling it must have been for one-dimensional beings to invade a two-dimensional plane by jumping out of an airplane? $\endgroup$ Sep 28, 2017 at 22:06
  • 3
    $\begingroup$ @EngineerToast: they're zero-dimensional beings :) $\endgroup$ Sep 29, 2017 at 22:46
  • 1
    $\begingroup$ The GPS (Global Posioning System) won't work on an infinite 2d surface, you need a Planar Position System, or a PPS instead. :-) $\endgroup$
    – Bass
    Oct 3, 2017 at 11:12

9 Answers 9

16
$\begingroup$

Answer for three soldiers

Since the relative distances to all soldiers is known, the soldiers might as well all go directly (i.e in a straight line)

to the Fermat point of the set of all soldiers (of course, this is assuming that they are sufficiently capable at mathematics, but they are immortal so they have forever to do the sums). This point is special in that it subtends equal angles to all three soldiers, except in a special case - I'll not go into that, but this point still exists (and is in fact a vertex) and this still works.

Outline of proof that this works

Firstly, prove existence and uniqueness of this point - this is not too bad (especially because of some useful stuff you can do such as angle stuff or Ptolemy's. A useful construction would be constructing external equilateral triangles on sides of the triangle). Next, show that the in the non-overobtuse (overobtuse = an angle is at least 120 degrees) (yes, I made that up) case, the angles subtended by a side to this point are all 120 degrees. Lastly, notice that this still holds even as the people walk towards the point. If the triangle is overobtuse, then this point (the Fermat one) lies at the side with the largest angle. Notice that as other people walk towards this point, it remains the same since the sum of distances from this point to all soldiers decreases at least as rapidly as the sum of the distance from any other point to the soldiers.

Answer for 4 soldiers

We can see that if the

convex hull of the set of soldiers make is a convex quadrilateral, the intersection of the diagonals is valid as a meeting point (not too hard to see)

On the other hand, if the

convex hull is a triangle, then the soldier inside the triangle is a valid meeting point - all soldiers go to that point, activate their detonator and immediately head back any distance (optional)

Both may fail if three soldiers end up in a line, with 0 probability.

Actually, generalisation...?!

Perhaps

Heading to the point P such that the sum of the distances from P to the locations of the soldiers is minimal

This point exists (that isn't too hard to prove), I think, but I'm not sure if P varies. I'm not sure if P is necessarily unique. I believe the cases where it isn't (if any) have 0 probability though, as perturbation of any point will result in a successful configuration.

As @ffao pointed out (thanks!),

P does not vary as moving any soldier towards P decreases the sum of their distances to P more than the sum of their distances to any other point.

Again, as @ffao pointed out (thanks again!) and Gareth (thanks as well!) clarified,

The geometric median (as it's called, apparently) is unique as long as the points are not collinear; the points are collinear with 0 probability.

Some curiosities:

- The geometric median for four points is the intersection of diagonals for convex hull is a quadrilateral, and also is the center point if the convex hull is a triangle
- It is also the Fermat point for three points (hence this generalises all the previous solutions)
- "No such formula is known for the geometric median, and it has been shown that no explicit formula, nor an exact algorithm involving only arithmetic operations and kth roots can exist in general" (good luck immortal soldiers, I think you'll need it)

$\endgroup$
15
  • $\begingroup$ I don't think P varies; if you're moving straight for P, surely the point whose distance is decreasing the most after the move is P, so there's no way some other point will overtake it as the optimal sum of distances. $\endgroup$
    – ffao
    Sep 29, 2017 at 3:47
  • $\begingroup$ Oh, right. I just realised, uniqueness of P is also an issue here. $\endgroup$
    – Wen1now
    Sep 29, 2017 at 4:13
  • 1
    $\begingroup$ According to wikipedia, "when the points are not collinear, the sum of distances is positive and strictly convex and hence the minimum is achieved at a unique point". I don't know what this means but you might :P $\endgroup$
    – ffao
    Sep 29, 2017 at 4:41
  • 2
    $\begingroup$ So far as I am aware, there is no procedure that computes this point exactly in finite time. So I'm not sure how the soldiers can do this. (I suspect it is the intended answer, though.) $\endgroup$
    – Gareth McCaughan
    Sep 29, 2017 at 9:09
  • $\begingroup$ @Wen1now do you think the fermat point could be an edge of the triangle?! $\endgroup$
    – sousben
    Sep 30, 2017 at 19:21
6
$\begingroup$

Every soldier should use the GPS as soon as they wake up, and head straight for

the northernmost soldier.

The movement of the soldiers does not affect this location, since

the northernmost soldier will not move, and no other soldier will ever move further north.

In the case that

two or more soldiers 'tie' for northernmost

which happens with probability zero, then

choose the most easterly of those soldiers.

The reasoning is the same as before.

$\endgroup$
3
  • 1
    $\begingroup$ Assuming, of course, that they know where "north" is. Another assumption that OP should probably clarify... $\endgroup$
    – ffao
    Sep 29, 2017 at 3:20
  • $\begingroup$ OP has qualified the challenge: "there is no such concept as "North". Otherwise, would be a good answer. $\endgroup$ Oct 1, 2017 at 11:10
  • $\begingroup$ See my answer. "GPS" implicitly creates a north. So it should be removed form the question for clarity. $\endgroup$
    – BmyGuest
    Oct 6, 2017 at 12:15
3
$\begingroup$

Possible answer: traveling in circles

All tentative as well as the accepted answer here are based on the soldiers traveling in a straight line.
Circles offers new perspectives, and if a general case exists it could be stronger than using the geometric median which we don't know to compute with precision!

Working N=3 solution

The 3 points of a triangle also delimit 3 arcs on their circumscribed circle: ⌒AB, ⌒AC and ⌒BC
Except some 0 probability events (3 points forming an isosceles triangle), one of the 3 arcs will be longer than the other 2. The 3 soldiers can therefore convene in advance of a meeting point (the initial position of one of them) that will work with a probability 1 if they travel only opposite to the longest arc.

Example:
The soldiers agree to meet on the starting point of the soldier who is not in contact with the longest arc. If ⌒AB is the longest arc, the meeting point will be C. With A traveling only on ⌒AC and B traveling only on ⌒BC, they can wake up at any random time and will know where to go. They could also have chosen to meet on the first extremity of ⌒AB clockwise (B) or counterclockwise (A).

enter image description here

The demonstration is I think trivial, because anytime A or B gets closer to C, the long arc AB gets longer.

4 soldiers, convex setup

If they form a convex quadrilateral, I think they can successfully infiltrate with a probability of 1 using the following strategy:
Upon waking up a soldier looks at all the possible triangles and their circumscribed circles. The meeting point will be the clockwise extremity of the longest arc of the circle that has the greatest diameter.
Soldiers who wake up on that circle will travel on it counterclockwise. The soldier who doesn't, can travel clockwise (I think) on any of the 2 circles that go through him and the meeting point. Traveling in a straight line for him wouldn't work because it could create a situation close to alignment, and possibly changing what will be the meeting point for another soldier waking up.

In the example below, CAD has the largest circumscribed circle, C is the meeting point, and B can travel on ⌒BC clockwise on any of the blue or the red circle without compromising the success probability of the infiltration.

enter image description here

4 soldiers, concave setup

When the quadrilateral is concave, traveling to the same point as before can be dangerous because 3 soldiers may get close to alignment and mess up the meeting point for other soldiers when they wake up. On the other hand, traveling towards the concave point seems to work, both on a straight line or on one of the circle paths, provided that the soldiers choose the path that doesn't invert convexity.

On the example below, A, C and D can easily travel to B without breaking the concavity of the quadrilateral.

enter image description here

General case

I will award a bounty if someone finds a generalized solution where the meeting point is always a soldier.

$\endgroup$
2
  • $\begingroup$ Woah, that is an awesome solution for n=3! I was doing a writeup of why it was impossible to always meet at a soldier, but got stuck and scrolled down to see other's progress (in case I was wrong). Last note, I didn't actually assume that the soldiers had to move in straight lines, but I found a solution where they did which worked. $\endgroup$
    – Wen1now
    Oct 3, 2017 at 7:13
  • $\begingroup$ Thank you, to be honest I am not 100% sure the person who initially sent this puzzle was thinking about your solution because: 1. it is not always possible to compute 2. he said "no one independently worked out a solution for any N" which is surprising given that there is no real increase in complexity between n=3,4 and up with the geometric median! 3. he confirmed my answer was correct for 3 and didn't suggest another way to solve it $\endgroup$
    – sousben
    Oct 3, 2017 at 7:35
1
$\begingroup$

This is not a valid answer since it is stated that noone can see each other even they are exactly at the same location.

Here is my methodology including they can wake up any time and without using compass etc:

First of all, I will try to explain my methodology with an example and make it general:

enter image description here

This is our initial condition, where you can see anyone in their map. let say E wakes up and the rest is still sleeping, or does not matter if anyone has already started to move according to the method, but for simplicity I will make E moves only for now.

E will calculate the center of their position with putting a simple coordinate system on the locations with the formula below:

$Avg_{CoorX}=\frac{C_1x+C_2x+....}{Num_{soldiers}}$

which is simple average of X and Y axes values. As example, I put a random coordinate system on their locations, but whatever X and Y axes you use, it will be the same result:

enter image description here

I took the reference point as $A$ for $E$ and find the mid point using their coordinates and draw a circle where it covers everything as below:

enter image description here

So our furthest point to the center is $A$, and it could be any point anyway but that's the point where they are going to meet but how?

This is a tricky part because if "let say" $E$ wakes up and starts to move to $A$, the new furthest point to the middle point may change to $B$ or $C$ as you suspected. So $E$ cannot move to $A$ for sure. So where can he move?

Here is the tricky part!

$E$ will move straight to furthest point from $A$ which is point $C$ in this condition. As a result $A$ will be always furthest point from the center point soldiers calculate after they check their GPSs. And everybody knows (including $C$) $C$ is the furthest point from $A$ always! So if $C$ or $D$ or anyone wakes up while $E$ moving, $A$ being the furthest point from middle point and $C$ is the furthest point from $A$ will not change.

enter image description here

So:

  • $A$ will not move at all.
  • C will not move until the rest arrives to his location
  • The rest ($B$,$E$,$D$) will move to $C$ directly without making more distance from $A$ than $C$.
    • After they all made to point $C$ (They will wait the rest arriving to $C$), they will move together to $A$.

enter image description here

I believe this methodology will always work whenever they wake up. In more general:

  • Wake up and find the center point on the GPS, find the furthest soldier ($F_1$) to the center, find the further soldier ($F_2$) to this one.
  • $F_1$ will not move at all.
  • The rest (except $F_1$ and $F_2$) will move to $F_2$ directly without making more distance from $F_1$ than $F_2$.
  • After they all made to point $F_2$, they will move together to $F_1$.

Though there are some possibilities where there are more than one $F_2$ and more than one $F_1$. But there is tweak for these conditions:

What if there are more than one $F_2$ but unique $F_1$,

The rest (except $F_1$ and $F_2$s) will move to nearest $F_2$s, then move to the other $F_2$ in a straight line, so there is no way they will miss other soldiers after a while and they know how many soldiers are not $F_1$. moreover a single movement to another $F_2$ will favor the destination $F_2$ since the distance will be shorter because they move straight.

What if there are more than one $F_1$,

There is also no problem using the same methodology where "$F_1$s don't move until someone reaches them.". Because even a single movement from anyone will change the center, and $F_1$ will be unique. Here is an example:

enter image description here

Let say this is initial condition and a soldier wakes up and see this condition. There are 3 $F_1$s and one $F_2$s for each $F_1$. Probably one of the worst condition possible but if any soldier moves even like a inch, there will be a unique $F_1$ and unique $F_2$ because the center will automatically change. For example, let say a point in the circle wakes up and see this condition, he is furthest from one of the $F_1$, but if he even moves a inch to any other furthest point, the middle point will not favor his $F_1$ anymore and there will be a unique $F_1$. The rest becomes the same methodology above.

Please ask me any question regarding to this methodology, I will edit this answer accordingly. But l believe this will work with any conditions.

$\endgroup$
3
  • 2
    $\begingroup$ "After they all made to point F2, they will move together to F1." How do they know they all reached F2? They can't see each other, even on the same spot. $\endgroup$
    – ffao
    Sep 29, 2017 at 23:02
  • $\begingroup$ In the case $N=3$ and the points are at the vertices of an equilateral triangle, who moves? (Or can this and similar cases be dismissed as probability 0 events?) $\endgroup$
    – Lawrence
    Sep 29, 2017 at 23:11
  • $\begingroup$ @ffao i did not notice they cant see esch other even they are at exactly at the same point :/ too unrealistic... $\endgroup$
    – Oray
    Sep 30, 2017 at 5:12
1
$\begingroup$

Just for fun, let's try skirting the rules with physics, and establish a sort of communication channel by abusing the facts that immortal point mass soldiers are, indeed, dimensionless, and that they do, indeed, have mass. So..

Let the point mass soldiers be nearly frictionless, and very heavy.

Once on the infinite plane, each point mass soldier, conscious or not, will experience a net gravitational pull toward the common center of gravity, and will enter a decaying orbit around it. (Orbit, because not all the soldiers landed at the same time, and decaying, because they are only nearly frictionless).

Once John, the leader of the immortal point mass forces, and heaviest of them all by several orders of magnitude, wakes up, he sticks his point mass feet in the 2-d mud, and stops himself. This will anchor the center of mass of the whole system, which will start to orbit John, and will eventually converge to John's location due to the tiny friction.

Since the soldiers' gravities will interact with each other, some soldiers might get flung right out of the system, but even the tiny friction will eventually stop them, and they'll fall right back in.

Once a point mass soldier comes to a complete stop and feels no net acceleration for some time (could take mighty long, but, hey, still immortal), he knows that the common center of mass has stopped, and that he is at the center of mass.

He can then say "Hi, John", press the detonator, and buy half a kilogram of point mass beer with the point mass money he got from selling that crappy single-use GPS.

(No, I'm not really serious, but it seemed like an fun idea :-)

$\endgroup$
2
  • 1
    $\begingroup$ this is a realy fun way of reading the instructions, i was just wondering at the "nearly frictionless" part, isn't there a distance where that tiny little friction could just prevent the soldier to move toward the others ? $\endgroup$
    – Neil
    Oct 3, 2017 at 12:41
  • $\begingroup$ Oh, yeah, that could be a problem.. but only if we assume that static friction is a thing that exists. :-) Purely kinetic friction won't cause problems, it only slows things down, but won't prevent a stopped soldier from returning. Yeah, this is definitely how I planned it in the first place, and didn't completely overlook it at all. $\endgroup$
    – Bass
    Oct 3, 2017 at 15:52
1
$\begingroup$

Not a solution but an observation which might require the original question to be re-phrased:

The soldiers can not have a GPS device!

( No solder can have a device which tell him where he himself is. )

Instead:

They can only have a device which tells them the relative distance to other soldiers and which direction (when the device rotates) the soldier is. Like a "scanner".

Why?

Any "mapping" device which locates itself requires some sort of origin or reference point, otherwise it can not put itself "on the map". Similarly, if it would have any sense of "direction" - i.e. when the device is rotated - it would require a physical property or axis to determine its relative orientation.

So, for the question as currently written, one "trick" answer would be:

The soldiers have a GPS. So their device has some sort of reference point. They all agree on moving to this reference point.

or also

If the "GPS" only has some directional sense, but no fixed origin: Calling the direction "North" for simplicity: The soldiers agree that the one soldier which is the most to the "north" stays put. All others move to him - first only moving perpendicular to the North-South axis.. (This is of course the same answer as proposed by 2012rcampion above.)

$\endgroup$
0
$\begingroup$

The soldiers meet up at the point that minimizes the total distance to their starting points. Each solder immediately uses their GPS on waking up, walks straight to the distance-minimizing point, and activates their detonator at it.

The key property is that the current distance-minimizing point remains the same as soldiers walk towards it, so soldiers waking up later will choose the same point. Imagine to the contrary that some soldiers have walked partway to the distance-minimizing point P, but from the current position another point Q has smaller total distance than P, so they divert to Q instead. This means the combined crooked walk is shorter in total than the originally planned walk to P. A straight-line walk from the initial positions to Q would be even shorter in total than this jagged one, and so shorter than the original walk to P. This contradicts that P was distance-minimizing.

This assumes a unique distance-minimizing point, which I'm pretty sure happens with probability 1.

$\endgroup$
3
  • $\begingroup$ How is this different from Wen's answer? $\endgroup$
    – ffao
    Sep 30, 2017 at 9:53
  • $\begingroup$ @ffao I prove the claim. $\endgroup$
    – xnor
    Sep 30, 2017 at 9:55
  • $\begingroup$ Two things. Firstly, I prove this claim as well, albeit informally. Secondly, the existence of a unique distance-minimizing point is also noted in my solution $\endgroup$
    – Wen1now
    Sep 30, 2017 at 11:11
-1
$\begingroup$

A slow, iterative, approximate solution:

  • At every iteration of a given timestep (say 1 minute), check the direction of every other Soldier.

  • If they fall within 180 degrees, move in the direction that bisects the range of angles seen. If not within 180, stay still.

  • The speed of travel is either the max possible speed for the soldiers or 1/2 (distance to furthest soldier)/(timestep), whichever is smaller.

  • Now they iterate into a shrinking circle. Wait until every other soldier is within some arbitrarily small distance each other, which can be defined for any given set of starting conditions and a distance epsilon.

If this heathen Fogland plane doesn't accept arbitrarily-near explosions on an arbitrarily-long (but provably finite!) timescale, then maybe we were never meant to succeed.

$\endgroup$
2
  • $\begingroup$ Each soldier carries two devices, both of which are only good enough for a single use. $\endgroup$
    – ffao
    Sep 29, 2017 at 17:36
  • $\begingroup$ Hah, I read the brief several times looking for that conceit and didn't spot it. Ah well. $\endgroup$ Oct 4, 2017 at 9:56
-1
$\begingroup$

I think the way i solved is there is a p=1 chance it will work(although it can fail with p=0 chance), with any number of n>=3.

The point mass soldiers are given the instructions beforehand:

1.- Whenever you wake up, use the gps device.
2.- Calculate where to go(specific, about to be described).
3.- Travel to it.
4.- Use the detonator. 

So, the location a point mass soldier should go is the following:

Calculate every point mass soldier's distance sum from everyone else. For example at n=3, any point mass soldier will have a location sum of two number for all three point mass soldier(including himself).

Identify the one which is the minimum, if there are more than one minimum, chose randomly between them(let's call him bomberman). If it is you, you can use the detonator right now.

Why it works?

The location where the detonation will happen is the same, unless there will be a time where there will be at least 2 minimum(the sum) who are not in the exact same location.

This is because no distance sum can decrease by more than the bombermen's, when everyone is travelling there in a straight line(so the bomberman will stay the same). (the same amount can be subtracted from other's sum, who are in the same line of the travelling, at at least that distance where the bomberman is).

Because of it it doesn't even matter if someone is waking up during the time someone is travelling, the one called bomberman can not change.

Of course after the first guy uses the detonator, he will be also at the bomberman's location, but it won't matter for the ones who wake up after.

After the last point mass soldier wakes up, and get to the point to use the detonator, they win.

When can it fail?

Because of they are at random locations at the start, there is a p=0 chance that there will be more point mass soldier with the exact same sum min distance.

For example if they woke up in the corner's of a square, they can still fail(which means there will be two different location where someone will detonate).

If there wasn't at least two minimum sum, there won't be during their mission.

$\endgroup$
1
  • 1
    $\begingroup$ The bomberman can change. For example, suppose there's an almost right-angled triangle ABC with almost-right angle at A and AC>AB. Specifically, the angle at A is less than 90. Now C wakes up first. As C walks towards A, when C is just near the foot of the perpendicular from B to AC, B wakes up. The bomberman, from B's POV, is C. Thus B moves towards Cs new location, and the detonators explode in different places. $\endgroup$
    – Wen1now
    Sep 30, 2017 at 11:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.