BMAD 64 Report post Posted January 2, 2018 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. Quote Share this post Link to post Share on other sites
1 CaptainEd 26 Report post Posted January 5, 2018 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. Quote Share this post Link to post Share on other sites
1 CaptainEd 26 Report post Posted January 2, 2018 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. Quote Share this post Link to post Share on other sites
1 plainglazed 67 Report post Posted January 4, 2018 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). Quote Share this post Link to post Share on other sites
0 Donald Cartmill 2 Report post Posted January 3, 2018 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. Quote Share this post Link to post Share on other sites
0 Donald Cartmill 2 Report post Posted January 4, 2018 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. Quote Share this post Link to post Share on other sites
0 harey 8 Report post Posted January 14, 2018 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) Quote Share this post Link to post Share on other sites
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.
Share this post
Link to post
Share on other sites