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.
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 |
slightly different solution
