We will let \(\{b_i\}\) be a sequence of numbers modulo \(p\) that after \(n\) steps becomes the sequence \(\{b_i + ni\}\) modulo \(p\). For three balls to be in the same box at move \(n\) means that the evolved \(b_i' \equiv b_i + ni\), \(b_j' \equiv b_j + nj\) and \(b_k' \equiv b_k + nk\) must be congruent modulo \(p\). \[b_i + ni \equiv b_j + nj \pmod{p} \implies \frac{b_i - b_j}{i - j} \equiv -n \pmod{p}\] Combining this with what we get from \((j, k)\), we obtain \[\frac{b_i - b_j}{i - j} \equiv \frac{b_j - b_k}{j - k} \pmod{p}\] Indeed, this means that if \(\{i, b_i\}\) from \(i = 0\) to \(p\) is a set of points in \(\mathbf{Z}_p^2\) (effectively a \(p \times p\) grid with cyclic coordinates), we want to show that three points are collinear. Rephrased, there are two points in the first column (\(i = 0\) and \(i = p\)) and one point in the rest of the columns, and we wish to show that three points must be collinear. We will now declare a chain of reformulations of this problem - in what follows, \(p\) is simply an odd number - we do not require \(p\) prime at all!

First, note that this problem is equivalent to showing that given \(p\) points, all in distinct columns, there is no point that is not covered by the collection of lines joining the \(p\) points. If there was such a point, then we have \(p + 1\) points such that no three are collinear - one of the columns has two points, and we can just translate this column to \(i = 0\).

We now introduce the projective plane of order \(p\): a structure that effectively 'adds' points at infinity on every slope in our \(p \times p\) grid and ensures a structure with \(p^2 + p + 1\) total points, \(p + 1\) points through every line and \(p + 1\) lines through every point. Define an \(m\)-arc in the projective plane to be a set of \(m\) points such that no three are collinear, and define an oval as a \(p+1\)-arc. We claim the following statement: in the projective plane of order \(p\), a \(p\)-arc either uniquely extends to an oval, or does not extend to an oval at all. This is enough to finish, since we know a point in the projective plane that extends the \(p\)-arc with points in pairwise distinct columns to an oval; namely, the point at infinity along the \(y\)-axis!

We first show a magical algebraic/combinatorial proof of this claim. Define a tangent to a set of points as a line that passes through exactly \(1\) of the points. Since there are \(p + 1\) lines through any point, looking at a point on the \(p\)-arc, we note that there are \(p - 1\) lines through it that are not tangents. Thus, there are exactly \(2\) tangents through every point on the \(p\)-arc. Let \(t_i\) be the number of points outside the \(p\)-arc such that \(i\) distinct tangents from the \(p\)-arc pass through it. The problem is equivalent to showing that \(t_p \le 1\).

Since \(p\) is an odd number and any line through the \(p\)-arc contains either \(1\) or \(2\) of its points, there can be no point outside the \(p\)-arc that passes through an even number of tangents, so \(t_{2j} = 0\) for all \(j\). We only define \(t_i\) for \(i \le p\), since there can be no point that lies on \(p + x\) tangents - that would mean by the pigeonhole principle that it lies on two of the tangents through the same point, which is absurd. Now, notice that \[\sum_{i = 1}^p t_i = p^2 + 1 \;\;\;\; (1)\] which is true since there are \(p^2 + p + 1\) points total, and \(p\) points on the \(p\)-arc. Next, \[\sum_{i=1}^p i t_i = (2p)(p) = 2p^2 \;\;\;\; (2)\] which counts the number of (point \(\in\) tangent) pairs. Finally, \[\sum_{i=1}^p \binom{i}{2} t_i = 4 \binom{p}{2} \;\;\;\; (3)\] which counts the nummber of (tangent \(\cap\) tangent \(=\) point) triples. Now, we consider the following expression, which is motivated by noticing that \(t_1 = \binom{p+1}{2}\), \(t_3 = \binom{p}{2}\), \(t_p = 1\) is a solution to the above equations: \[S = \sum_{i=1}^p (i - 1)(i - 3)(i - p)t_i\] Note that this expression can clearly never be positive. Calculating \(\sum i^2 t_i = 6p^2 - 4p\) from the equation sum \((2) + 2 \times (3)\), we get \[\begin{align*} S &= \sum_{i=1}^p i^3 t_i - (p + 4)(6p^2 - 4p) + (4p + 3)(2p^2) - 3p(p^2+1) \\ &= \sum_{i=1}^p i^3 t_i - p^3 - 14p^2 + 13p \end{align*}\] Assume for the sake of contradiction that \(t_p \ge 2\). Then \(\sum i^3 t_i > 2p^3\), which means \[S \ge p^3 - 14p^2 + 13p > p(p - 13)(p + 1)\] This expression is \( > 0\), and thus a contradiction, for all \(p \ge 13\). It remains to check \(p = 5\), \(7\), \(9\), \(11\), which are all very short bashes by hand. Hence, we have a contradiction to the fact that \(t_p \ge 2\), so \(t_p \le 1\) must hold - we are done.

The \(p = 11\) case is demonstrated in order to show that the bash is doable: note that we have the system of equations \[t_1 + t_3 + t_5 + t_7 + t_9 + t_{11} = 122\] \[t_1 + 3 t_3 + 5 t_5 + 7 t_7 + 9 t_9 + 11 t_{11} = 242\] \[3 t_3 + 10 t_5 + 21 t_7 + 36 t_9 + 55 t_{11} = 220\] Clearly \(t_{11} < 4\), and \(t_{11} = 3\) is not possible by comparing equation \((\text{ii}) - (\text{i})\) vs. equation \((\text{iii})\). Thus the only possibility left to check is \(t_{11} = 2\), which yields the system \[t_1 + t_3 + t_5 + t_7 + t_9 = 120\] \[t_1 + 3 t_3 + 5 t_5 + 7 t_7 + 9 t_9 = 220\] \[3 t_3 + 10 t_5 + 21 t_7 + 36 t_9 = 110\] Consider the equation obtained through \((\text{iii}) - (\text{ii}) + (\text{i})\), that is, \(t_3 + 6 t_5 + 15 t_7 + 28 t_9 = 10\). This instantly yields \(t_7 = t_9 = 0\), so \(t_3 + 6t_5 = 10\). This simply cannot work with equation \((\text{iii})\), and we are done.

Here we provide another proof to the main claim: in the projective plane of order \(p\) (where \(p\) is odd), a \(p\)-arc either uniquely extends to an oval, or does not extend to an oval at all. Suppose our \(p\)-arc does extend to an oval, but not uniquely. Then, note that due to Segre's theorem on projective planes of odd order, conics and ovals are equivalent, so we obtain two conics that pass through \(p + 1\) points, and share \(p\) points. Since \(p \ge 5\), they must be the same conic, and we are done.

Note that it is not as though our proof has not used the fact that \(p\) is prime at all - we have used this when we converted the problem to a collinearity problem on a grid, in the 'collinearity formula'.

A similar result to the main claim holds for even \(n\). If we define a hyperoval to be a set of \(n + 2\) points in a projective plane of even order \(n\) such that no \(3\) are collinear, then an oval can always (!) be uniquely extended to a hyperoval. The proof of this fact follows along similar lines to the first proof we have mentioned: Note that there is exactly \(1\) tangent (rather than the messy \(2\) tangents in our case) through each point on the oval, letting \(t_i\) denote the number of points that have \(i\) tangents passing through them, we look at the quantity \[S = \sum_{i=1}^{n+1} (i - 1)(i - (n+1)) t_i\] which is directly equal to \(0\) since there is no cubic expression at all.