BMO Short List

Every child receives a prize if and only if $N=2^a{3}^b$ for some non-negative integers $a$ and $b$. For convenience, say $N$ is good if every child receives a prize.

Number the children $0,\dots ,N-1$ clockwise around the circle, child number $0$ starting with the parcel. After $n$ turns, the parcel will have been passed $1^2+2^2+\cdots +n^2=n(n+1)(2n+1)/6$ places around the circle. For convenience, write $s_n=n(n+1)(2n+1)/6$. Thus, child $m$ receives the parcel, and hence a prize, if and only if $m\equiv s_n(\mathrm{mod}N)$ for some $n$, so $N$ is good if and only if $s_n$ assumes every possible value modulo $N$.

To rule out the case where $N$ is divisible by a prime $p>3$, it is sufficient to show that $s_n$ misses some value modulo $p$. The latter follows from the fact that $6$ has a multiplicative inverse modulo $p$, and $s_n\equiv 0(\mathrm{mod}p)$ if $n\equiv 0(\mathrm{mod}p)$ or $-1(\mathrm{mod}p)$, so $s_n$ assumes at most $p-1$ values modulo $p$. Consequently, such an $N$ is certainly not good.

We now show that each $N$ of the form $2^a{3}^b$ is good. We do this by showing that, if $N$ is good, then so are both $2N$ and $3N$; since $1$ is clearly good, this is sufficient to prove goodness of $2^a{3}^b$ inductively on $a+b$.

To show that, if $N$ is good, then so is $2N$, refer to goodness of the former to infer that, for each $m$ modulo $2N$, there exists an $n$ such that $s_n\equiv m(\mathrm{mod}2N)$. Clearly, only the case $s_n\equiv m+2N(\mathrm{mod}2N)$ is to be dealt with. In this case, $$s_{n+6N}=s_n+(6n^2+6n+1)N+18(2n+1)N^2+72N^3\equiv s_n+N\equiv m(\mathrm{mod}2N).$$ Consequently, $2N$ is indeed good.

To show that, if $N$ is good, then so is $3N$, refer again to goodness of the former to infer that, for each $m$ modulo $3N$, there exists an $n$ such that $s_n\equiv m(\mathrm{mod}3N)$ or $m+2N(\mathrm{mod}3N)$. Clearly, only the last two cases are to be dealt with. In the former case, $$s_{n+12N}=s_n+2(6n^2+6n+1)N+72(2n+1)N^2+2^6{3}^2{N}^3\equiv s_n+2N\equiv m(\mathrm{mod}3N),$$ and in the latter, $$s_{n+6N}=s_n+(6n^2+6n+1)N+18(2n+1)N^2+72N^3\equiv s_n+N\equiv m(\mathrm{mod}3N).$$ Consequently, $3N$ is indeed good.