Given $n$ students in the plane such that the $\frac{n(n-1)}{2}$ distances are pairwise distinct. Each student gives a candy each to the $k$ students closest to him. Given that each student receives the same amount of candies, determine all possible values of $n$ in terms of $k$. Proposed by Wong Jer Ren
Problem
Source: Malaysian SST 2024 P3
Tags: combinatorics
13.09.2024 08:50
This problem is not real. Needed a hint from @above to finish. Note that $n > k$. Call such a candy giving distribution good. Claim: Call a configuration of $n$ students, potentially with two distances being the same, for some $k$, uniquely distinguishable if for any student, there is an unambiguous way to refer to the $k$ students closest to it. Then if any such configuration is good, then we can get a configuration with all distinct distances that work. Proof. Let the minimal difference between two different of the $\frac{n(n-1)}{2}$ distances be $\varepsilon$. Then we can perturb each student in within a $\frac{\varepsilon}{1434}$-neighborhood such that all distances are distinct. This preserves the fact that if a distance $d_1$ between two students is initially less than $d_2$, then it remains so afterward. This means that this new configuration remains good. $\blacksquare$ For even $k$, we can take a regular $n$-gon, where each student gives candies to the $\frac{k}{2}$ neighbors on each side of them in the $n$-gon. This is uniquely distinguishable and good which suffices. Now consider odd $k$. Claim: For odd $k$, if student $A$ gives a candy to $B$, then $B$ gives a candy to $A$. Proof. We take any candy configuration and repeatedly remove the up to two edges in the smallest distance in the directed graph $G$ where $A \mapsto B$ if $A$ gives $B$ a candy. This operation preserves the fact that each student always gives their candies to the students with closest unremoved distances, and that each student has the same indegree and outdegree. As such, when we remove the edge $A \mapsto B$, then $B$ must have nonzero outdegree, and the distance $A$ to $B$ is minimal, so $B \mapsto A$ must also be present. $\blacksquare$ This implies that there are an even number of candies given, so $nk$ must be even and thus $n$ is even. For even $n$, consider taking a regular $\frac{n}{2}$-gon $A_1A_2 \dots A_n$ of students inscribed in a circle, and another regular $\frac{n}{2}$-gon $B_1 \dots B_n$ such that $A_iB_i = \frac{1}{1434n}$ is small and $B_i$ is counterclockwise of $A_i$ as a minor arc. Then the $k$ neighbors of $A_i$ are $B_i$, the $\frac{k-1}{2}$ neighbors clockwise of $A_i$, and the $\frac{k-1}{2}$ neighbors counterclockwise of $B_i$. The $k$ neighbors of $B_i$ are the same with $A_i$ instead. This means that this operation is fixed when $i$ is shifted, so by symmetry each $A_i$ gets the same number of candy. By flipping, we get that each $A_i$ and $B_i$ gets the same amount of candy. This configuration is also uniquely distinguishable and good which finishes.