Induction

This is a problem that I tried a while ago and got nowhere with. Looking at it again, it seems rather tame and easy. Maybe this is because it was a problem set from the induction lecture, giving a rather large hint as to what to do. Nonetheless, I enjoy whenever this happens because it shows that I'm actually making progress.



Proceed by INDUCTION. LECKE.

Start with n=3. Since the distances to each person are different, we can conclude that they form a scalene triangle. Take the shortest of its lengths - these two people shoot eachother, leaving the third man unsprayed.

Assume its true for n=k, k-2, ..., 3, show its true for n=k+2:

Again, consider the shortest attainable distance. Depending on the positioning of the people, this shortest distance could occur between a number of people. Assume for now that it only occurs once (we'll address this soon enough). These two people shoot each other. Now consider the remaining k people. If any one of them shoots one of these two people, then at least one person will be left dry, as we have k-1 shots left but k people who haven't been sprayed. Thus, we can assume that they form their own little "spraying group", if you will, of k people. Since we already showed that at least one of these people will be left dry, we're done.

Note that if we have more than one of those "shortest distances" then all that happens is that instead of having a group of k people, we would now have a group of k-2, k-4, or something else depending on how many of those there are.

What if, as a result of these shortest distance cases, we are left with a group of only 1 person? Although we didn't prove the base case of n=1, we can just point out that if this occurs, we're left with one dry person, which is enough to prove our claim.