Problem 9

9. Suppose $n$ children holding loaded water pistols are standing in an open field, no three of them in line, such that all the distances between pairs of them are distinct. At a given signal, each child shoots the child closest to him or her with water. Show that if $n$ is an even number, then it is possible (but not necessarily the case) that every child gets wet. Show that if $n$ is odd, then necessarily at least one child stays dry.

Commentary: My method of finite-point intersections in constructing the even case was taken from a resourceful proof I'd read of the problem, "Can the real plane be covered by countably many lines?" This was important as it was otherwise difficult to "prove the obvious" that certain area subtractions didn't annihilate the whole area. For the odd case, the key was in finding an "odd man out" in pairing (guaranteeing a sequence of length greater than two) and the aside about sequence length (disproving any sequence of length greater than two).

Proof: We shall prove the odd statement first, and then the even.

Say $a→b$ if child $a$ shoots child $b$. Assume the configuration between the $n$ children is such that there exists distinct $a,b,c$ such that $a→b→c$. Then we show necessarily at least one child stays dry. This is generally the case for odd $n$ (as otherwise the children could be paired up exactly with who they shoot, as the shot would have no one else to shoot but the shooter; formally, say $a \text{~} b$ if $a=b$ or if $a→b$. Then $\text{~}$ is checked to be naturally reflexive, and transitive and symmetric by assuming such $a,b,c$ don't exist. Hence $\text{~}$ is an equivalence relation, and we cannot have less than or more than $2$ elements in any element of the afforded partition set, hence the order of the union of the partition is even), yet it can still occur from even $n$, and together with the even statement's proof it will classify the case in which it does occur when $n$ is even.

Before continuing with the odd case, we prove that there does not exist a sequence of distinct children $p_1→...→p_m→p_1$ when $m > 2$. To wit, let $r_i$ denote the distance between child $p_i$ and $p_{i+1}$ for $1 ≤ i < m$ and let $r_m$ be the distance between $p_m$ and $p_1$. When $m > 2$ we must have $r_1 > r_2$ for $p_2$ to shoot $p_3$ rather than $p_1$, and generally we continue $r_1 > ... > r_m$ implying $r_1 > r_m$, but now $p_1$ would've shot $p_m$, a contradiction.

Return back to the distinct sequence $a→b→c$. Let $D$ be the set of all children in a sequence that eventually shoots $a$. Starting from $a$, choose another child shooting $a$ (if no child is to remain dry), choose another child shooting this child, and continue until a child $d$ reappears in the sequence (necessarily since there are a finite amount of children), hence $d→e→...→d$. But this whole sequence is contained in $D$ by induction, and also by the aside above the sequence for $d$ must simply be $d→e→d→e→...$, never in fact reaching $a$, a contradiction.

The even statement is simple enough to take on faith; simply scatter the children very far apart so that they shoot each other in pairs, and wiggle them if necessary to eliminate collinearity. More formally, construct the $2m$ case for all natural $m$ by induction. $m=0$ is vacuously true without children. Construct the $2(m+1)$ case from $2m$ as follows: Let $r$ be the maximum distance between any two children. Then select a line $l$ such that $l$ does not intersect any circles of radius $r$ drawn around the children (possible since the circles' maximum height in the plane is bounded), so in particular doesn't intersect any children. Place an extra child $x_1$ on this line such that he isn't collinear with any other children and doesn't have equal distance between any two other children (possible since the other children's collinearity lines as do the lines denoting equal distance between two other children intersect $l$ in only finitely many places, and the line has infinite points). Letting $r' > r$ be the minimum distance between $x_1$ and any other child and $s$ be the smallest distance between any two children, draw an open ball $b$ of radius $\text{min}\{r'-r,r,s\}$ around $x_1$. Let $m$ be the maximum of the slopes collected when drawing lines between $x_1$ and the children and lines denoting the points equal distance between any two children (excluding vertical lines if needed), and draw a line $l'$ of slope $m'$ intersecting $x_1$. Then those lines intersect the infinite $l'∩b$ in only finitely many places, so place $x_2$ in $l'∩b$ not on any of these lines. We have completed the task of placing $x_1$ and $x_2$ such that (1) $x_1$ shoots $x_2$, (2) $x_2$ shoots $x_1$, (3) $|x_1-c|≠|d-e|$ for all children $c,d,e$ with $d,e≠x_1$, (4) $|x_1-c|≠|x_1-d|$ for all children $d,e$, also (3) and (4) with $x_1$ replaced by $x_2$, and (7) there are no lines containing $x_1$ and two previous children, and (8) no lines containing $x_1$, $x_2$, and a previous child.