Soldiers in a field

[BMAD]

An odd number of soldiers are stationed in a field such that all the pairwise distances are distinct. Each soldier is told to keep an eye on the nearest other soldier.  Prove that at least one soldier is not being watched.

[CaptainEd]

Consider the person whose shortest distance to someone is the longest. Can that person be in a cycle? 

Suppose A is that soldier, and B is the closest soldier to A.

Distance AB is less than Ax for all x other than B. More compactly,

AB < Ax

BC < Bx including BA

CD < Cx including CB < AB

...

VW < Vx including VU < ... < AB

WA < Wx including WV <...< AB

But AB < Ax including WA

This contradiction resulted from the assumption that there is a cycle that includes the soldier with maximin distance.

Since there can be no cycles, can all the soldiers be part of mutual pairs? Only an even number of soldiers can do that, but we have an odd number.

So there is at least one soldier who is not in a cycle, and is not part of a mutual pair.

[Donald Cartmill]

Not exactly a proof ,but if all soldiers watch the soldier to their left, then the soldier to the extreme right is NOT being watched. and the reverse is true.   Taking the smallest odd number 3, if the middle man looks left then the man on the right is not watched .  The only way all ARE watched is if they are in a circle.

[plainglazed]

Spoiler

Given the constraint of the OP that all pairwise distances are distinct, one such distance must be the greatest.  And since there are an odd number of soldiers, that soldier (n) with the greatest distinct pairwise distance is watching another soldier (m) but that soldier(m) is watching another leaving no one watching soldier (n).

 

[Donald Cartmill]

21 hours ago, Donald Cartmill said:

Not exactly a proof ,but if all soldiers watch the soldier to their left, then the soldier to the extreme right is NOT being watched. and the reverse is true.   Taking the smallest odd number 3, if the middle man looks left then the man on the right is not watched .  The only way all ARE watched is if they are in a circle.

 

[CaptainEd]

Maybe this is clearer and more accurate than my previous try.

Point one: 

The shortest distance is between one pair, A and B. They are a mutual pair, as the shortest distance from each goes to the other.

Point two:

Consider the node whose smallest distance is greater than anyone else’s. Call that soldier A. A’s smallest distance is to a node, call it B.

Which soldier is pointing at A? Call it Z. Because AB is A’s least distance, AB < Ax for all x in S - {A,B}

Because ZA is Z’s least distance, ZA < Zx for all x in S - {A,Z}

Because  A’s smallest distance is greater than anyone else’s, ZA < AB. But that contradicts the fact that AB < AZ. 

However, it is possible that Z = B, as AB <= AZ and ZA <= AB. 

Result: the node with the highest lowest distance is in a mutual pair OR A is not watched.

What about the next highest least distance? Call it node C, its successor D and predecessor Y.

CD < Cx for all x in S - {C,D}

YC < Yx for all x in S - {C,Y}

Because C’s smallest distance is greater than anyone other than A or B, YC < CD, but that contradicts that CD < YC.

This can only happen if Y = D. So CD are a mutual pair OR C is not watched.

The same argument proceeds one pair at a time, until an unwatched soldier is found, OR one soldier remains. That soldier is not watched.

[harey]

On 1/5/2018 at 11:50 PM, CaptainEd said:

Maybe this is clearer and more accurate than my previous try.

Point one: 

 

  Hide contents

 

The shortest distance is between one pair, A and B. They are a mutual pair, as the shortest distance from each goes to the other.

 

Point two:

 

  Hide contents

 

Consider the node whose smallest distance is greater than anyone else’s. Call that soldier A. A’s smallest distance is to a node, call it B.

Which soldier is pointing at A? Call it Z. Because AB is A’s least distance, AB < Ax for all x in S - {A,B}

Because ZA is Z’s least distance, ZA < Zx for all x in S - {A,Z}

Because  A’s smallest distance is greater than anyone else’s, ZA < AB. But that contradicts the fact that AB < AZ. 

However, it is possible that Z = B, as AB <= AZ and ZA <= AB. 

Result: the node with the highest lowest distance is in a mutual pair OR A is not watched.

What about the next highest least distance? Call it node C, its successor D and predecessor Y.

CD < Cx for all x in S - {C,D}

YC < Yx for all x in S - {C,Y}

Because C’s smallest distance is greater than anyone other than A or B, YC < CD, but that contradicts that CD < YC.

This can only happen if Y = D. So CD are a mutual pair OR C is not watched.

The same argument proceeds one pair at a time, until an unwatched soldier is found, OR one soldier remains. That soldier is not watched.

 

 

 

Cannot you shorten it?

- if no one else watches A nor B, remove A and B and start over (this happens if A and B are very near and all other are far away enough)
- if someone else watches A and/or B, at least one is not being watched (evident; if proof needed, start with 3 and continue with recursion)