AI proved a math conjecture I made when I was an undergraduate

2026-09-13

The problem

Given positive integers $n$ and $k$ with $k<n$, consider $n-1$ balls labelled $1,2,\ldots,n-1$. Color them subject to the following rules:

1. Balls $i$ and $n-i$ have the same color.
2. Balls $i$ and $|i-k|$ have the same color whenever $i\ne k$.

What is the maximum possible number of colors?

I recently rediscovered this problem in my undergraduate notes. I proposed this problem “inspired by a homework problem in my discrete mathematics class.” At the time, I experimentally found what appeared to be the answer, but I never managed to prove it rigorously. Years later, I gave the problem to an AI, which revealed the simple algebraic structure behind the conjecture.

My original observation

Let $f(n,k)$ denote the answer. From small examples, I observed the recurrence

$$f(n,k)=f\bigl(\max(n-k,k),\min(n-k,k)\bigr).$$

This resembles the Euclidean algorithm, so I conjectured that the answer depends only on $\gcd(n,k)$. More precisely, if $d=\gcd(n,k)$, then

$$\boxed{f(n,k)=\left\lfloor\frac d2\right\rfloor+1.}$$

The conjecture is correct and proved by AI. Following are AI-generated contents.

Proof

Think of each ball as a vertex. Join two vertices whenever the rules require the corresponding balls to have the same color. Every connected component must be monochromatic, while different components may receive different colors. Thus, $f(n,k)$ is exactly the number of connected components.

It is convenient to regard the labels as the nonzero elements of $\mathbb Z/n\mathbb Z$. The first rule says

$$i\sim-i\pmod n.$$

The second rule, together with the first, gives an edge between $i$ and $i-k\pmod n$. If $i>k$, this follows directly from $i\sim i-k$. If $i<k$, then

$$i\sim k-i\sim -(k-i)=i-k\pmod n.$$

The relation $\sim$ is symmetric: if we can move from $i$ to $i-k$, we can traverse the same edge backward and move from $i-k$ to $i$. Thus we may both subtract and add $k$. Repeating these moves, and applying negation when desired, produces labels congruent to

$$\pm i+qk\pmod n,\qquad q\in\mathbb Z.$$

Equivalently, one could take only nonnegative $q$: because the sequence is periodic modulo $n$, a negative value of $q$ can always be replaced by a nonnegative one. The only caveat is that $0$ is not an actual label; we handle that case below.

Now let $d=\gcd(n,k)$. The subgroup of $\mathbb Z/n\mathbb Z$ generated by $k$ is precisely the set of multiples of $d$. Therefore, repeated addition of $k$ can change a label by any multiple of $d$, and negation can change its residue modulo $d$ from $r$ to $-r$. It follows that two labels $i$ and $j$ are connected exactly when

$$j\equiv i\pmod d \qquad\text{or}\qquad j\equiv-i\pmod d.$$

There is one small boundary issue: the label $0$ is not a ball. This does not split the component consisting of multiples of $d$. In the cycle formed by repeatedly adding $k$, removing $0$ leaves a path whose endpoints are $k$ and $n-k$; the first coloring rule connects those two endpoints. Hence all nonzero multiples of $d$ remain in one component.

We are therefore left to count the residue classes modulo $d$ after identifying each residue $r$ with $-r$. They are

$$\{0\},\{1,d-1\},\{2,d-2\},\ldots.$$

If $d$ is odd, there are $1+(d-1)/2$ such classes. If $d$ is even, there are $1+(d-2)/2+1$ because both $0$ and $d/2$ are fixed by negation. In either case, the total is

$$\left\lfloor\frac d2\right\rfloor+1.$$

Thus

$$\boxed{f(n,k)=\left\lfloor\frac{\gcd(n,k)}2\right\rfloor+1.}$$

The hidden structure

There are two complementary ways to describe the structure behind the problem. The first is concrete and gives the shortest proof; the second places the same argument in a broader group-theoretic setting.

The cyclic-group interpretation

Regard the labels as elements of the cyclic group $\mathbb Z/n\mathbb Z$. The coloring rules allow the operations

$$i\longmapsto i+k \qquad\text{and}\qquad i\longmapsto-i.$$

The subgroup generated by $k$ consists precisely of the multiples of $d=\gcd(n,k)$. Translation by $k$ therefore moves within a residue class modulo $d$, while negation identifies the class $r$ with $-r$. Consequently, the connected components are indexed by

$$(\mathbb Z/d\mathbb Z)/\{r\sim-r\}.$$

Counting these classes immediately gives $\lfloor d/2\rfloor+1$. This is the most direct interpretation of why the gcd appears in the answer.

The dihedral-group interpretation

Alternatively, write the two original operations as reflections:

$$s_0(i)=-i, \qquad s_1(i)=k-i \pmod n.$$

Their composition is the translation

$$s_1s_0(i)=i+k.$$

Abstractly, two reflections of this form generate the infinite dihedral group $D_\infty$, equivalently the affine Weyl group of type $\widetilde A_1$. The orbit of $i$ under its action on $\mathbb Z/n\mathbb Z$ is

$$\{\,\pm i+qk\pmod n:q\in\mathbb Z\,\}.$$

The coloring graph is essentially the Schreier graph of this action: applying either generator draws an edge, so its connected components are exactly the orbits. Although $D_\infty$ is infinite, this particular action is finite. The translation $i\mapsto i+k$ has order $n/d$, so the action factors through a finite dihedral group.

Thus the two descriptions say the same thing at different levels. The cyclic-group view computes the orbits directly; the dihedral-group view explains why translation and reflection occur together. The gcd formula is the concrete shadow of this underlying dihedral symmetry.

mathematics, number theory