All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
Keep an eye Onto the other (Posted on 2019-07-19) Difficulty: 3 of 5
An odd number of soldiers are stationed in a field in such a way that all the pairwise distances are distinct. Each soldier is told to keep an eye on the nearest other soldier. Show that at least one soldier is not being watched.

No Solution Yet Submitted by Danish Ahmed Khan    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution slightly different solution | Comment 3 of 4 |
Consider the case of 3 soldiers. The two soldiers closest together will watch each other, leaving the last soldier unwatched.

Consider the case of N (odd) soldiers. Again, the two soldiers closest together will watch each other. Now there are two possibilities:

Case 1: some other soldier(s) also watch one of these two. Since there are N watchers and N watchees, if multiple watchers watch the same watchee then there won't be enough watchers left over by the pigeonhole principle. In this case, there is no solution.

Case 2: no other soldiers watch these first two. In this case, there are still enough watchers to go around, but the scenario is identical to one with N-2 soldiers in which we remove the two closest soldiers. This case has a solution only if the corresponding N-2 case has a solution. BUT by induction, the N-2 has a solution only if the N-4 case does, and so on until we reach N=3, which we have already shown has no solution.

So in the end, there's always an unwatched soldier, regardless of which case applies.

  Posted by Paul on 2019-07-19 12:43:06
Please log in:
Remember me:
Sign up! | Forgot password

Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (4)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Copyright © 2002 - 2021 by Animus Pactum Consulting. All rights reserved. Privacy Information