Maths Olympiad Prep

Library / /12 of 115

Algebra Difficulty 6.5 National olympiad Find the answer

What is the smallest integer nn , greater than one, for which the root-mean-square of the first nn positive integers is an integer?
Note.\mathbf{Note.} The root-mean-square of nn numbers a1,a2,,ana_1, a_2, \cdots, a_n is defined to be [a12+a22++an2n]1/2\left[\frac{a_1^2 + a_2^2 + \cdots + a_n^2}n\right]^{1/2}

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let's first obtain an algebraic expression for the root mean square of the first nn integers, which we denote InI_n . By repeatedly using the identity (x+1)3=x3+3x2+3x+1(x+1)^3 = x^3 + 3x^2 + 3x + 1 , we can write 13+312+31+1=23,1^3 + 3\cdot 1^2 + 3 \cdot 1 + 1 = 2^3, 13+3(12+22)+3(1+2)+1+1=33,1^3 + 3 \cdot(1^2 + 2^2) + 3 \cdot (1 + 2) + 1 + 1 = 3^3, and 13+3(12+22+32)+3(1+2+3)+1+1+1=43.1^3 + 3\cdot(1^2 + 2^2 + 3^2) + 3 \cdot (1 + 2 + 3) + 1 + 1 + 1 = 4^3. We can continue this pattern indefinitely, and thus for any
positive integer nn , 1+3j=1nj2+3j=1nj1+j=1nj0=(n+1)3.1 + 3\sum_{j=1}^n j^2 + 3 \sum_{j=1}^n j^1 + \sum_{j=1}^n j^0 = (n+1)^3. Since j=1nj=n(n+1)/2\sum_{j=1}^n j = n(n+1)/2 , we obtain j=1nj2=2n3+3n2+n6.\sum_{j=1}^n j^2 = \frac{2n^3 + 3n^2 + n}{6}. Therefore, In=(1nj=1nj2)1/2=(2n2+3n+16)1/2.I_n = \left(\frac{1}{n} \sum_{j=1}^n j^2\right)^{1/2} = \left(\frac{2n^2 + 3n + 1}{6}\right)^{1/2}. Requiring that InI_n be an integer, we find that (2n+1)(n+1)=6k2,(2n+1 ) (n+1) = 6k^2, where kk is an integer. Using the Euclidean algorithm, we see that gcd(2n+1,n+1)=gcd(n+1,n)=1\gcd(2n+1, n+1) = \gcd(n+1,n) = 1 , and so 2n+12n+1 and n+1n+1 share no
factors greater than 1. The equation above thus implies that 2n+12n+1 and n+1n+1 is each proportional to a perfect square. Since 2n+12n+1 is
odd, there are only two possible cases:
Case 1: 2n+1=3a22n+1 = 3 a^2 and n+1=2b2n+1 = 2b^2 , where aa and bb are integers.
Case 2: 2n+1=a22n+1 = a^2 and n+1=6b2n+1 = 6b^2 .
In Case 1, 2n+1=4b21=3a22n+1 = 4b^2 -1 = 3a^2 . This means that (4b21)/3=a2(4b^2 -1)/3 = a^2 for some integers aa and bb . We proceed by checking whether (4b21)/3(4b^2-1)/3 is a perfect square for b=2,3,4,b=2, 3, 4, \dots . (The solution b=1b=1 leads to n=1n=1 , and we are asked to find a value of nn greater than 1.) The smallest positive integer bb greater than 1 for
which (4b21)/3(4b^2-1)/3 is a perfect square is b=13b=13 , which results in n=337n=337 .
In Case 2, 2n+1=12b21=a22n+1 = 12b^2 - 1 = a^2 . Note that a2=2n+1a^2 = 2n+1 is an odd square, and hence is congruent to 1(mod4)1 \pmod 4 . But 12b213(mod4)12b^2 -1 \equiv 3 \pmod 4 for any bb , so Case 2 has no solutions.
Alternatively, one can proceed by checking whether 12b2112b^2 -1 is a perfect square for b=1,2,3,b=1, 2 ,3 ,\dots . We find that 12b2112b^2 -1 is not a perfect square for b=1,2,3,...,7,8b = 1,2, 3, ..., 7, 8 , and n=383n= 383 when b=8b=8 . Thus the smallest positive integers aa and bb for which 12b21=a212b^2- 1 = a^2 result in a value of nn exceeding the value found in Case 1, which was 337.
In summary, the smallest value of nn greater than 1 for which InI_n is an integer is 337\boxed{337} .

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.