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

 Keep an eye Onto the other (Posted on 2019-07-19)
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.)
 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

 Search: Search body:
Forums (0)