Maths Olympiad Prep

Library / /46 of 84

, 2002

Number theory Difficulty 5.3 AIME, harder Prove it United States

Problem:
Let TL=n=1Ln3/9T_{L} = \sum_{n=1}^{L} \left\lfloor n^{3} / 9 \right\rfloor for positive integers LL. Determine all LL for which TLT_{L} is a square number.

Solution

Solution:
Since TLT_{L} is square if and only if 9TL9 T_{L} is square, we may consider 9TL9 T_{L} instead of TLT_{L}.
It is well known that n3n^{3} is congruent to 0,10, 1, or 88 modulo 99 according as nn is congruent to 0,10, 1, or 22 modulo 33. (Proof: (3m+k)3=27m3+3(9m2)k+3(3m)k2+k3k3(mod9)(3m + k)^{3} = 27m^{3} + 3(9m^{2})k + 3(3m)k^{2} + k^{3} \equiv k^{3} \pmod{9}.) Therefore
n39n3/9n^{3} - 9\left\lfloor n^{3} / 9 \right\rfloor is 0,10, 1, or 88 according as nn is congruent to 0,10, 1, or 22 modulo 33. We find therefore that
9TL=1nL9n39=1nLn3#{1nL:n1(mod3)}8#{1nL:n2(mod3)}=(12L(L+1))2L+238L+13. \begin{aligned} 9 T_{L} &= \sum_{1 \leq n \leq L} 9\left\lfloor \frac{n^{3}}{9} \right\rfloor \\ &= \sum_{1 \leq n \leq L} n^{3} - \#\{1 \leq n \leq L : n \equiv 1 \pmod{3}\} - 8\#\{1 \leq n \leq L : n \equiv 2 \pmod{3}\} \\ &= \left( \frac{1}{2} L(L+1) \right)^{2} - \left\lfloor \frac{L+2}{3} \right\rfloor - 8\left\lfloor \frac{L+1}{3} \right\rfloor . \end{aligned}
Clearly 9TL<(L(L+1)/2)29 T_{L} < (L(L+1)/2)^{2} for L1L \geq 1. We shall prove that 9TL>(L(L+1)/21)29 T_{L} > (L(L+1)/2 - 1)^{2} for L4L \geq 4, whence 9TL9 T_{L} is not square for L4L \geq 4. Because
(L(L+1)/21)2=(L(L+1)/2)2L(L+1)+1, (L(L+1)/2 - 1)^{2} = (L(L+1)/2)^{2} - L(L+1) + 1,
we need only show that
L+23+8L+13L2+L2. \left\lfloor \frac{L+2}{3} \right\rfloor + 8\left\lfloor \frac{L+1}{3} \right\rfloor \leq L^{2} + L - 2 .
But the left-hand side of this is bounded above by 3L+10/33L + 10/3, and the inequality 3L+10/3L2+L23L + 10/3 \leq L^{2} + L - 2 means exactly L22L16/30L^{2} - 2L - 16/3 \geq 0 or (L1)219/3(L-1)^{2} \geq 19/3, which is true for L4L \geq 4, as desired.
Hence TLT_{L} is not square for L4L \geq 4. By direct computation we find T1=T2=0T_{1} = T_{2} = 0 and T3=3T_{3} = 3, so TLT_{L} is square only for L{1,2}L \in \{\mathbf{1}, \mathbf{2}\}.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.