Jump to content
BrainDen.com - Brain Teasers
  • 0

Soldiers in a field


BMAD
 Share

Question

6 answers to this question

Recommended Posts

  • 1

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.

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

  • 1
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).

 

Link to comment
Share on other sites

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

 

Link to comment
Share on other sites

  • 1

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.

Link to comment
Share on other sites

  • 0
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)

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...