An odd number of people armed with water guns are standing in a field so that all the pairwise distances are distinct. At a signal, each shoots at his nearest neighbor and hits him. Prove that one person doesn’t get wet.
Consider the two people separated by the shortest distance. At the signal, these two will shoot one another. Now:
If another player has also shot at one of these two, then we’ve established that one player was shot twice, and hence that some other player (in the whole group) lacked an antagonist and stayed dry.
If no other player shot at these two, then we can remove them from consideration and apply the same reasoning to the remaining group: The two closest neighbors fired on one another; if another player fired on them then we have our proof; if not then remove the pair and continue.
Because we’re removing players in pairs, the group under consideration always contains an odd number of players. But it can’t drop all the way to a single player, as he would be firing on no one, and we’ve said that every player fires on someone. Hence at some point we must discover a player who is fired on twice, and thus prove that some other player was not fired on at all.
From the 1987 Canadian Mathematical Olympiad, based on a problem from the 6th All Soviet Union Mathematical Competition in Voronezh, 1966.
