Maths Olympiad Prep

Library / /5 of 15

Algebra Difficulty 8.6 Shortlist Prove it IMO

Determine all real numbers α\alpha such that the number
α+2α++nα \lfloor\alpha\rfloor+\lfloor 2 \alpha\rfloor+\cdots+\lfloor n \alpha\rfloor
is a multiple of nn for every positive integer nn. (Here z\lfloor z\rfloor denotes the greatest integer less than or equal to zz.)

Solutions — 4

Solution 1

Answer: All even integers satisfy the condition of the problem and no other real number α\alpha does so.

Solution 1. First we will show that even integers satisfy the condition. If α=2m\alpha=2 m where mm is an integer then
α+2α++nα=2m+4m++2mn=mn(n+1) \lfloor\alpha\rfloor+\lfloor 2 \alpha\rfloor+\cdots+\lfloor n \alpha\rfloor=2 m+4 m+\cdots+2 m n=m n(n+1)
which is a multiple of nn.

Now we will show that they are the only real numbers satisfying the conditions of the problem. Let α=k+ϵ\alpha=k+\epsilon where kk is an integer and 0ϵ<10 \leqslant \epsilon<1. Then the number
α+2α++nα=k+ϵ+2k+2ϵ++nk+nϵ=kn(n+1)2+ϵ+2ϵ++nϵ \begin{aligned} \lfloor\alpha\rfloor+\lfloor 2 \alpha\rfloor+\cdots+\lfloor n \alpha\rfloor & =k+\lfloor\epsilon\rfloor+2 k+\lfloor 2 \epsilon\rfloor+\cdots+n k+\lfloor n \epsilon\rfloor \\ & =\frac{k n(n+1)}{2}+\lfloor\epsilon\rfloor+\lfloor 2 \epsilon\rfloor+\cdots+\lfloor n \epsilon\rfloor \end{aligned}
has to be a multiple of nn. We consider two cases based on the parity of kk.

Case 1: kk is even.
Then kn(n+1)2\frac{k n(n+1)}{2} is always a multiple of nn. Thus
ϵ+2ϵ++nϵ \lfloor\epsilon\rfloor+\lfloor 2 \epsilon\rfloor+\cdots+\lfloor n \epsilon\rfloor
also has to be a multiple of nn.

We will prove that nϵ=0\lfloor n \epsilon\rfloor=0 for every positive integer nn by strong induction. The base case n=1n=1 follows from the fact that 0ϵ<10 \leqslant \epsilon<1. Let us suppose that mϵ=0\lfloor m \epsilon\rfloor=0 for every 1m<n1 \leqslant m<n. Then the number
ϵ+2ϵ++nϵ=nϵ \lfloor\epsilon\rfloor+\lfloor 2 \epsilon\rfloor+\cdots+\lfloor n \epsilon\rfloor=\lfloor n \epsilon\rfloor
has to be a multiple of nn. As 0ϵ<10 \leqslant \epsilon<1 then 0nϵ<n0 \leqslant n \epsilon<n, which means that the number nϵ\lfloor n \epsilon\rfloor has to be equal to 0.

The equality nϵ=0\lfloor n \epsilon\rfloor=0 implies 0ϵ<1/n0 \leqslant \epsilon<1 / n. Since this has to happen for all nn, we conclude that ϵ=0\epsilon=0 and then α\alpha is an even integer.

Case 2: kk is odd.
We will prove that nϵ=n1\lfloor n \epsilon\rfloor=n-1 for every natural number nn by strong induction. The base case n=1n=1 again follows from the fact that 0ϵ<10 \leqslant \epsilon<1. Let us suppose that mϵ=m1\lfloor m \epsilon\rfloor=m-1 for every 1m<n1 \leqslant m<n. We need the number
1+nϵ 1+\lfloor n \epsilon\rfloor
to be a multiple of nn. As kk is odd, we need 1+nϵ1+\lfloor n \epsilon\rfloor to be a multiple of nn. Again, as 0ϵ<10 \leqslant \epsilon<1 then 0nϵ<n0 \leqslant n \epsilon<n, so nϵ=n1\lfloor n \epsilon\rfloor=n-1 as we wanted.

This implies that 11nϵ<11-\frac{1}{n} \leqslant \epsilon<1 for all nn which is absurd. So there are no other solutions in this case.

Comment. An alternative ending to the previous solution is as follows.
By definition we have Snαn(n+1)2S_{n} \leqslant \alpha \frac{n(n+1)}{2}, on the other hand (5) implies Snαn2nS_{n} \geqslant \alpha n^{2}-n for all nn large enough, so α=0\alpha=0.

Solution 2

As in Solution 1 we check that for even integers the condition is satisfied. Then, without loss of generality we can assume 0α<20 \leqslant \alpha<2. We set Sn=α+2α++nαS_{n}=\lfloor\alpha\rfloor+\lfloor 2 \alpha\rfloor+\cdots+\lfloor n \alpha\rfloor.

Notice that
Sn0(modn)SnSnSn1=nα(modn1)(2) \begin{array}{ll} S_{n} \equiv 0 & (\bmod n) \\ S_{n} \equiv S_{n}-S_{n-1}=\lfloor n \alpha\rfloor & (\bmod n-1) \tag{2} \end{array}
Since gcd(n,n1)=1\operatorname{gcd}(n, n-1)=1, (1) and (2) imply that
Snnnα(modn(n1)). \begin{equation*} S_{n} \equiv n\lfloor n \alpha\rfloor \quad(\bmod n(n-1)) . \tag{3} \end{equation*}
In addition,
0nnαSn=k=1n(nαkα)<k=1n(nαkα+1)=n(n1)2α+n. \begin{equation*} 0 \leqslant n\lfloor n \alpha\rfloor-S_{n}=\sum_{k=1}^{n}(\lfloor n \alpha\rfloor-\lfloor k \alpha\rfloor)<\sum_{k=1}^{n}(n \alpha-k \alpha+1)=\frac{n(n-1)}{2} \alpha+n . \tag{4} \end{equation*}
For nn large enough, the RHS of (4) is less than n(n1)n(n-1). Then (3) forces
0=Snnnα=k=1n(nαkα) \begin{equation*} 0=S_{n}-n\lfloor n \alpha\rfloor=\sum_{k=1}^{n}(\lfloor n \alpha\rfloor-\lfloor k \alpha\rfloor) \tag{5} \end{equation*}
for nn large enough.

Since nαkα0\lfloor n \alpha\rfloor-\lfloor k \alpha\rfloor \geqslant 0 for 1kn1 \leqslant k \leqslant n, we get from (5) that, for all nn large enough, all these inequalities are equalities. In particular α=nα\lfloor\alpha\rfloor=\lfloor n \alpha\rfloor for all nn large enough, which is absurd unless α=0\alpha=0.

Solution 3

As in other solutions, without loss of generality we may assume that 0α<20 \leqslant \alpha<2. Even integers satisfy the condition, so we assume 0<α<20<\alpha<2 and we will derive a contradiction.

By induction on nn, we will simultaneously show that
α+2α++nα=n2 and 2n1nα<2. \begin{gather*} \lfloor\alpha\rfloor+\lfloor 2 \alpha\rfloor+\cdots+\lfloor n \alpha\rfloor=n^{2} \tag{6}\\ \text{ and } \quad \frac{2 n-1}{n} \leqslant \alpha<2 . \tag{7} \end{gather*}
The base case is n=1n=1 : If α<1\alpha<1, consider m=1α>1m=\left\lceil\frac{1}{\alpha}\right\rceil>1, then
α+2α++mα=1 \lfloor\alpha\rfloor+\lfloor 2 \alpha\rfloor+\cdots+\lfloor m \alpha\rfloor=1
is not a multiple of mm, so we deduce (7). Hence, α=1\lfloor\alpha\rfloor=1 and (6) follows.

For the induction step: assume the induction hypothesis to be true for nn, then by (7)
2n+11n(n+1)α<2n+2 2 n+1-\frac{1}{n} \leqslant(n+1) \alpha<2 n+2
Hence,
n2+2nα+2α++nα+(n+1)α=n2+(n+1)α<n2+2n+2. n^{2}+2 n \leqslant\lfloor\alpha\rfloor+\lfloor 2 \alpha\rfloor+\cdots+\lfloor n \alpha\rfloor+\lfloor(n+1) \alpha\rfloor=n^{2}+\lfloor(n+1) \alpha\rfloor<n^{2}+2 n+2 .
So, necessarily (n+1)α=2n+1\lfloor(n+1) \alpha\rfloor=2 n+1 and
α+2α++nα+(n+1)α=(n+1)2 \lfloor\alpha\rfloor+\lfloor 2 \alpha\rfloor+\cdots+\lfloor n \alpha\rfloor+\lfloor(n+1) \alpha\rfloor=(n+1)^{2}
in order to obtain a multiple of n+1n+1. These two equalities give (6) and (7) respectively.

Finally, we notice that condition (7) being true for all nn gives a contradiction.

Solution 4

As in other solutions without loss of generality we will assume that 0<α<20<\alpha<2 and derive a contradiction. For each nn, we define
bn=α+2α++nαn, b_{n}=\frac{\lfloor\alpha\rfloor+\lfloor 2 \alpha\rfloor+\cdots+\lfloor n \alpha\rfloor}{n},
which is a nonnegative integer by the problem condition and our assumption. Note that
(n+1)αα,2α,,nα and (n+1)α>α \lfloor(n+1) \alpha\rfloor \geqslant\lfloor\alpha\rfloor,\lfloor 2 \alpha\rfloor, \ldots,\lfloor n \alpha\rfloor \quad \text{ and } \quad\lfloor(n+1) \alpha\rfloor>\lfloor\alpha\rfloor
for all n>1αn>\frac{1}{\alpha}. It follows that bn+1>bnbn+1bn+1b_{n+1}>b_{n} \Longrightarrow b_{n+1} \geqslant b_{n}+1 for n>1αn>\frac{1}{\alpha}. Thus, for all such nn,
bnn+C b_{n} \geqslant n+C
where CC is a fixed integer. On the other hand, the definition of bnb_{n} gives
bn=α+2α++nαnα+2α++nαn=α2(n+1), b_{n}=\frac{\lfloor\alpha\rfloor+\lfloor 2 \alpha\rfloor+\cdots+\lfloor n \alpha\rfloor}{n} \leqslant \frac{\alpha+2 \alpha+\cdots+n \alpha}{n}=\frac{\alpha}{2}(n+1),
which is a contradiction for sufficiently large nn.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.