IMO 2024 Problem 1
For each real number $\alpha$, define
Proposed by: -
Verified: yes
Verdicts: PASS + PASS
Solve time: 5m00s
Problem
Determine all real numbers $\alpha$ such that, for every positive integer $n$, the integer
$$ \lfloor \alpha \rfloor + \lfloor 2\alpha \rfloor + \dots +\lfloor n\alpha \rfloor $$
is a multiple of $n$. (Note that $\lfloor z \rfloor$ denotes the greatest integer less than or equal to $z$. For example, $\lfloor -\pi \rfloor = -4$ and $\lfloor 2 \rfloor = \lfloor 2.9 \rfloor = 2$.)
Problem Understanding
For each real number $\alpha$, define
$$S_n(\alpha)=\sum_{k=1}^n \lfloor k\alpha\rfloor .$$
The problem asks for all real numbers $\alpha$ such that
$$n\mid S_n(\alpha)$$
for every positive integer $n$.
The condition must hold simultaneously for all $n$, so even a small structural restriction on $\alpha$ can become decisive. The floor function suggests separating $\alpha$ into its integer and fractional parts.
Write
$$\alpha=m+\beta, \qquad m\in\mathbb Z, \qquad 0\le \beta<1.$$
Then
$$\lfloor k\alpha\rfloor = \lfloor km+k\beta\rfloor = km+\lfloor k\beta\rfloor,$$
because $km$ is an integer. Hence
$$S_n(\alpha) = m\sum_{k=1}^n k+\sum_{k=1}^n \lfloor k\beta\rfloor = m\frac{n(n+1)}2+\sum_{k=1}^n \lfloor k\beta\rfloor.$$
The problem becomes: determine all pairs $(m,\beta)$ for which
$$n\mid m\frac{n(n+1)}2+\sum_{k=1}^n \lfloor k\beta\rfloor \qquad\text{for every }n\ge1.$$
The integer part contributes a simple quadratic expression. The difficulty lies entirely in the fractional part.
Key Observations
If $\beta=0$, then $\alpha$ is an integer and
$$S_n(\alpha)=m\frac{n(n+1)}2.$$
The divisibility condition becomes
$$n\mid m\frac{n(n+1)}2.$$
After dividing by $n$,
$$\frac{S_n(\alpha)}n=m\frac{n+1}2.$$
Taking $n=2$ gives
$$\frac32 m\in\mathbb Z,$$
so $m$ must be even. Every even integer works, because if $m=2t$, then
$$S_n(\alpha)=tn(n+1),$$
which is divisible by $n$.
Thus the main task is to prove that $\beta$ cannot be positive.
The previous flawed proof attempted to choose
$$N=\left\lfloor \frac1\beta\right\rfloor,$$
and incorrectly claimed that $N\beta<1$ always holds. This fails when $1/\beta$ is an integer. For example, if $\beta=\tfrac13$, then $N=3$ and $N\beta=1$.
A correct argument must avoid this pitfall entirely.
The cleanest way is to choose the unique positive integer $N$ satisfying
$$N\beta<1\le (N+1)\beta.$$
Such an $N$ always exists when $0<\beta<1$. Indeed, let
$$N=\left\lceil \frac1\beta\right\rceil-1.$$
Then
$$N<\frac1\beta\le N+1,$$
and multiplying by $\beta>0$ gives
$$N\beta<1\le (N+1)\beta.$$
This formulation handles both cases, whether $1/\beta$ is integral or not.
Solution
Assume that $\alpha$ satisfies the required divisibility condition for every positive integer $n$.
Write
$$\alpha=m+\beta, \qquad m\in\mathbb Z, \qquad 0\le\beta<1.$$
As established earlier,
$$S_n(\alpha) = m\frac{n(n+1)}2+\sum_{k=1}^n \lfloor k\beta\rfloor.$$
We first prove that $\beta=0$.
Suppose instead that
$$0<\beta<1.$$
Choose
$$N=\left\lceil \frac1\beta\right\rceil-1.$$
Then
$$N\beta<1\le (N+1)\beta.$$
Since $\beta<1$, we also have
$$(N+1)\beta<2.$$
Indeed,
$$N+1=\left\lceil \frac1\beta\right\rceil\le \frac1\beta+1,$$
hence
$$(N+1)\beta\le 1+\beta<2.$$
Therefore
$$1\le (N+1)\beta<2.$$
For every integer $k$ with $1\le k\le N$,
$$0\le k\beta\le N\beta<1,$$
so
$$\lfloor k\beta\rfloor=0.$$
Also,
$$1\le (N+1)\beta<2,$$
so
$$\lfloor (N+1)\beta\rfloor=1.$$
Consequently,
$$\sum_{k=1}^N \lfloor k\beta\rfloor=0,$$
and
$$\sum_{k=1}^{N+1} \lfloor k\beta\rfloor=1.$$
Now apply the divisibility condition for $n=N$.
We obtain
$$S_N(\alpha)=m\frac{N(N+1)}2.$$
Since $N\mid S_N(\alpha)$,
$$N\mid m\frac{N(N+1)}2.$$
Dividing by the common factor $N$ gives
$$2\mid m(N+1).$$
Thus
$$m(N+1)$$
is even.
Next apply the divisibility condition for $n=N+1$.
Using
$$\sum_{k=1}^{N+1}\lfloor k\beta\rfloor=1,$$
we get
$$S_{N+1}(\alpha) = m\frac{(N+1)(N+2)}2+1.$$
Because $N+1\mid S_{N+1}(\alpha)$,
$$N+1 \mid m\frac{(N+1)(N+2)}2+1.$$
We now reduce the first term modulo $N+1$ carefully.
From the earlier conclusion that $m(N+1)$ is even, the integer
$$\frac{m(N+1)}2$$
is well defined. Hence
$$m\frac{(N+1)(N+2)}2 = (N+2)\cdot \frac{m(N+1)}2$$
is a multiple of $N+1$.
Therefore
$$S_{N+1}(\alpha)\equiv 1 \pmod{N+1}.$$
But the hypothesis says that $N+1\mid S_{N+1}(\alpha)$, so
$$1\equiv0\pmod{N+1}.$$
This implies
$$N+1=1,$$
which is impossible because $N\ge1$.
The contradiction shows that our assumption $0<\beta<1$ was false. Hence
$$\beta=0.$$
Thus $\alpha=m$ is an integer.
We now determine which integers work.
If $\alpha=m$, then
$$S_n(\alpha) = m\frac{n(n+1)}2.$$
The condition
$$n\mid S_n(\alpha)$$
becomes
$$n\mid m\frac{n(n+1)}2.$$
After dividing by $n$,
$$m\frac{n+1}2\in\mathbb Z \qquad\text{for every }n\ge1.$$
Taking $n=2$ gives
$$\frac32 m\in\mathbb Z,$$
so $m$ is even.
Conversely, if $m=2t$ for some integer $t$, then
$$S_n(\alpha) = 2t\cdot \frac{n(n+1)}2 = tn(n+1),$$
which is divisible by $n$ for every positive integer $n$.
Hence the required real numbers are exactly the even integers:
$$\boxed{\alpha\in 2\mathbb Z}.$$
Verification of Key Steps
The crucial construction is the choice
$$N=\left\lceil \frac1\beta\right\rceil-1.$$
This avoids the defect in the earlier argument. Consider the problematic example
$$\beta=\frac13.$$
Then
$$\left\lceil \frac1\beta\right\rceil = \lceil 3\rceil = 3,$$
so
$$N=2.$$
Indeed,
$$N\beta=\frac23<1, \qquad (N+1)\beta=1.$$
Hence
$$\lfloor \beta\rfloor=\lfloor 2\beta\rfloor=0, \qquad \lfloor 3\beta\rfloor=1,$$
exactly as required.
The divisibility reduction for $n=N+1$ also requires care. The expression
$$m\frac{(N+1)(N+2)}2$$
is not automatically divisible by $N+1$. For example, if $m=1$ and $N=1$, then it equals $3$, which is not divisible by $2$.
The proof first derives
$$2\mid m(N+1),$$
from the case $n=N$. Only after establishing this parity condition do we write
$$m\frac{(N+1)(N+2)}2 = (N+2)\cdot \frac{m(N+1)}2,$$
where
$$\frac{m(N+1)}2$$
is now known to be an integer. This justifies the reduction modulo $N+1$ rigorously.
The contradiction step should also be checked numerically in a sample case. Take
$$\beta=\frac13.$$
Then $N=2$. The argument gives
$$\sum_{k=1}^2 \lfloor k\beta\rfloor=0, \qquad \sum_{k=1}^3 \lfloor k\beta\rfloor=1.$$
From $n=2$,
$$2\mid m\cdot\frac{2\cdot3}2=3m,$$
so $m$ is even.
From $n=3$,
$$3\mid m\cdot\frac{3\cdot4}2+1=6m+1.$$
Since $6m$ is divisible by $3$, this would force $3\mid1$, impossible.
The mechanism of the proof functions exactly as intended.
Alternative Approaches
Another approach begins with the congruences
$$S_n(\alpha)\equiv0\pmod n, \qquad S_{n+1}(\alpha)\equiv0\pmod{n+1}.$$
Since
$$S_{n+1}(\alpha)-S_n(\alpha)=\lfloor (n+1)\alpha\rfloor,$$
one can compare consecutive congruences and derive strong restrictions on the sequence $\lfloor n\alpha\rfloor$. After sufficient manipulation, the sequence is forced to behave like
$$2cn$$
for some integer $c$, leading again to the conclusion that $\alpha$ must be an even integer.
A different route separates rational and irrational values of $\alpha$. Writing
$$\lfloor k\alpha\rfloor=k\alpha-{k\alpha},$$
gives
$$S_n(\alpha) = \alpha\frac{n(n+1)}2-\sum_{k=1}^n {k\alpha}.$$
If $\alpha$ is irrational, the fractional parts ${k\alpha}$ are distributed through $[0,1)$, and the resulting fluctuations prevent the required divisibility pattern from holding for every $n$. If $\alpha$ is rational but not an integer, periodicity of the fractional parts produces contradictions for suitable choices of $n$. This approach is more conceptual but requires substantially more machinery than the direct elementary argument above.