Kvant Math Problem 938
Let the angular speed be $\dfrac{360^\circ}{n}$ per second.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m22s
Source on kvant.digital
Problem
A radius of a circle centered at $O$ rotates uniformly, turning through an angle of $\dfrac{360^\circ}n$ in one second (where $n$ is a natural number greater than 3). Initially it occupied the position $OM_0$; after one second, the position $OM_1$; after a further 2 seconds, the position $OM_2$; after a further 3 seconds, the position $OM_3$; and so on; after a further $n-1$ seconds, the position $OM_{n-1}$.
- Prove that if $n$ is a power of 2, then the radii $OM_1$, $\ldots$, $OM_{n-1}$ divide the circle into $n$ equal sectors;
- Is this possible for other values of $n$?
V. V. Proizvolov
Tournament of Towns (Spring 1985)
Exploration
Let the angular speed be $\dfrac{360^\circ}{n}$ per second. The times at which the successive radii appear are
$$1,\quad 1+2,\quad 1+2+3,\quad \ldots,\quad 1+2+\cdots+k=\frac{k(k+1)}2.$$
Hence the radius $OM_k$ makes with the initial radius $OM_0$ the angle
$$\frac{360^\circ}{n}\cdot \frac{k(k+1)}2.$$
The problem asks when the set of residues
$$\frac{k(k+1)}2 \pmod n,\qquad k=0,1,\ldots,n-1,$$
contains every residue modulo $n$ exactly once. Indeed, equal sectors arise precisely when the $n$ radii occupy all $n$ directions
$$0,\frac{360^\circ}{n},\ldots,\frac{360^\circ(n-1)}n.$$
Testing small cases:
For $n=4$,
$$\frac{k(k+1)}2\equiv 0,1,3,2 \pmod 4,$$
all residues occur.
For $n=8$,
$$0,1,3,6,2,7,5,4,$$
again all residues occur.
For $n=5$,
$$0,1,3,1,0,$$
repetitions appear.
For $n=6$,
$$0,1,3,0,4,3,$$
repetitions again appear.
This suggests that powers of $2$ work and no other $n$ do.
The crucial point is to determine when the map
$$f(x)=\frac{x(x+1)}2 \pmod n$$
is a permutation of the residue classes modulo $n$.
Suppose
$$f(a)\equiv f(b)\pmod n.$$
Then
$$\frac{a(a+1)-b(b+1)}2 =\frac{(a-b)(a+b+1)}2.$$
For $n=2^m$, multiplication by $2$ is the only obstruction. One expects to prove injectivity by examining the exact power of $2$ dividing $a-b$.
For the converse, if $n$ has an odd divisor $d>1$, then
$$f(x+d)-f(x) =\frac{d(2x+d+1)}2.$$
Since $d$ is odd, choosing
$$2x+d+1\equiv 0\pmod{n/d}$$
should produce two distinct arguments with the same image modulo $n$. This would show that no $n$ having an odd factor can work.
Problem Understanding
We are given a rotating radius. After $1$ second it reaches $OM_1$, after a further $2$ seconds it reaches $OM_2$, and in general after a further $k$ seconds it reaches $OM_k$.
The direction of $OM_k$ is determined by the total elapsed time
$$\frac{k(k+1)}2.$$
The radii divide the circle into $n$ equal sectors exactly when the directions of
$$OM_0,OM_1,\ldots,OM_{n-1}$$
are the $n$ equally spaced directions of a regular $n$-division of the circle.
This is a Type B problem. We must prove the stated property for powers of $2$ and determine whether it can occur for any other $n$.
The core difficulty is to decide for which $n$ the residues
$$\frac{k(k+1)}2 \pmod n$$
form a complete residue system modulo $n$.
Proof Architecture
First, translate the geometric condition into an arithmetic one: the radii form $n$ equal sectors if and only if the residues $\frac{k(k+1)}2 \pmod n$ are all distinct.
Second, prove that for $n=2^m$ the map $x\mapsto \frac{x(x+1)}2$ is injective modulo $n$. The argument starts from
$
(a-b)(a+b+1)\equiv0\pmod{2^{m+1}}
$
and uses the exact power of $2$ dividing $a-b$.
Third, prove that injectivity implies the desired geometric conclusion, since there are exactly $n$ residues modulo $n$.
Fourth, prove the converse. If $n$ has an odd divisor $d>1$, write $n=dq$. Choose $x$ satisfying
$
2x+d+1\equiv0\pmod q
$.
Then
$
f(x+d)\equiv f(x)\pmod n
$,
so the map is not injective.
The hardest step is the injectivity proof for $n=2^m$, because one must control the $2$-adic divisibility of both factors carefully.
Solution
Let
$$f(k)=\frac{k(k+1)}2.$$
The total time elapsed when the radius reaches the position $OM_k$ is
$$1+2+\cdots+k=\frac{k(k+1)}2=f(k).$$
Since the radius turns through $\dfrac{360^\circ}{n}$ each second, the direction of $OM_k$ differs from that of $OM_0$ by
$$\frac{360^\circ}{n},f(k).$$
Thus two radii $OM_a$ and $OM_b$ coincide precisely when
$$f(a)\equiv f(b)\pmod n.$$
The radii
$$OM_0,OM_1,\ldots,OM_{n-1}$$
divide the circle into $n$ equal sectors if and only if their directions are all distinct. Since there are exactly $n$ residue classes modulo $n$, this is equivalent to the residues
$$f(0),f(1),\ldots,f(n-1)$$
forming a complete residue system modulo $n$.
We now determine for which $n$ this happens.
Assume first that
$$n=2^m.$$
Suppose
$$f(a)\equiv f(b)\pmod{2^m}.$$
Then
$$\frac{a(a+1)-b(b+1)}2\equiv0\pmod{2^m},$$
hence
$$(a-b)(a+b+1)\equiv0\pmod{2^{m+1}}.$$
Let
$$a-b=2^t u,$$
where $u$ is odd and $t\ge0$.
If $t<m$, then $a-b$ is divisible by $2^t$ but not by $2^{t+1}$. Since
$$(a+b+1)-(a-b)=2b+1,$$
and $2b+1$ is odd, the numbers $a+b+1$ and $a-b$ have opposite parity modulo $2^{t+1}$. Consequently $a+b+1$ is divisible by exactly $2^t$ and by no higher power of $2$.
Therefore the highest power of $2$ dividing
$$(a-b)(a+b+1)$$
is $2^{2t}$.
Because $t<m$, we have
$$2t\le 2m-2<m+1+t.$$
In particular,
$$2^{m+1}\nmid (a-b)(a+b+1),$$
contrary to the congruence above.
Hence $t\ge m$, which means
$$2^m\mid(a-b).$$
Thus
$$a\equiv b\pmod{2^m}.$$
The map $f$ is injective modulo $2^m$. Since there are exactly $2^m$ residue classes modulo $2^m$, it is a permutation of those residue classes. Therefore the directions of
$$OM_0,OM_1,\ldots,OM_{n-1}$$
are exactly the $n$ equally spaced directions, and the radii divide the circle into $n$ equal sectors.
Now suppose that $n$ is not a power of $2$. Then $n$ has an odd divisor $d>1$. Write
$$n=dq.$$
Because $d$ is odd, $2$ is invertible modulo $q$. Choose an integer $x$ satisfying
$$2x+d+1\equiv0\pmod q.$$
Then
$$f(x+d)-f(x) =\frac{(x+d)(x+d+1)-x(x+1)}2 =\frac{d(2x+d+1)}2.$$
The factor $2x+d+1$ is divisible by $q$, so
$$f(x+d)-f(x)$$
is divisible by
$$dq=n.$$
Hence
$$f(x+d)\equiv f(x)\pmod n.$$
Since $d>1$, the numbers $x$ and $x+d$ represent distinct residue classes modulo $n$. Thus $f$ is not injective modulo $n$.
Therefore the residues $f(0),\ldots,f(n-1)$ do not form a complete residue system modulo $n$, and the corresponding radii cannot divide the circle into $n$ equal sectors.
We have proved that the required division into $n$ equal sectors occurs precisely when $n$ is a power of $2$.
This completes the proof.
∎
Verification of Key Steps
The first delicate point is the passage from geometry to arithmetic. The direction of $OM_k$ is determined by the angle
$$\frac{360^\circ}{n}f(k).$$
Two directions coincide exactly when their difference is an integer multiple of $360^\circ$, which is equivalent to
$$f(a)-f(b)\equiv0\pmod n.$$
No geometric information is lost in this translation.
The second delicate point is the injectivity proof for $n=2^m$. From
$$(a-b)(a+b+1)\equiv0\pmod{2^{m+1}}$$
one cannot conclude that either factor is divisible by $2^{m+1}$. The correct argument uses the exact power of $2$ dividing $a-b$. Writing
$$a-b=2^t u,$$
with $u$ odd, the identity
$$(a+b+1)-(a-b)=2b+1$$
shows that $a+b+1$ has exactly the same $2$-adic valuation $t$. Hence the product has valuation $2t$. If $t<m$, then $2t<m+1+t$, so the product cannot be divisible by $2^{m+1}$. This forces $t\ge m$.
The third delicate point is the construction for the converse. Since $n=dq$ with $d$ odd, the congruence
$$2x+d+1\equiv0\pmod q$$
always has a solution because $2$ is invertible modulo $q$. Substituting into
$$f(x+d)-f(x)=\frac{d(2x+d+1)}2$$
gives divisibility by $dq=n$, producing two distinct residue classes with the same image.
Alternative Approaches
A different approach uses permutation polynomials modulo powers of $2$. The map
$$f(x)=\frac{x(x+1)}2$$
is the classical triangular-number polynomial. One may prove directly that it induces a permutation of the residue classes modulo $2^m$ by studying its action on even and odd residues and proceeding recursively from modulus $2^m$ to modulus $2^{m+1}$. This yields a short proof of the first part.
For the converse, one may invoke the Chinese remainder theorem. If $n$ has an odd factor, write
$$n=2^m r,$$
with $r$ odd and $r>1$. The congruence
$$f(x+r)\equiv f(x)\pmod r$$
shows that $f$ is not injective modulo $r$. A permutation modulo $n$ would induce a permutation modulo every divisor of $n$, which is impossible. The direct construction given in the main solution avoids introducing this additional machinery.