1986 USAMO Problems/Problem 3

Revision as of 12:19, 19 July 2023 by Iaeuy (talk | contribs) (Added that Case 2 has no solutions by analyzing mod 4. Also changed variable name "p" to "k", as p commonly denotes a prime.)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Problem

What is the smallest integer $n$, greater than one, for which the root-mean-square of the first $n$ positive integers is an integer?

$\mathbf{Note.}$ The root-mean-square of $n$ numbers $a_1, a_2, \cdots, a_n$ is defined to be \[\left[\frac{a_1^2 + a_2^2 + \cdots + a_n^2}n\right]^{1/2}\]

Solution

Let's first obtain an algebraic expression for the root mean square of the first $n$ integers, which we denote $I_n$. By repeatedly using the identity $(x+1)^3 = x^3 + 3x^2 + 3x + 1$, we can write \[1^3 + 3\cdot 1^2 + 3 \cdot 1 + 1 = 2^3,\] \[1^3 + 3 \cdot(1^2 + 2^2) + 3 \cdot (1 + 2) + 1 + 1  = 3^3,\] and \[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 $n$, \[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 $\sum_{j=1}^n j  = n(n+1)/2$, we obtain \[\sum_{j=1}^n j^2 = \frac{2n^3 + 3n^2 + n}{6}.\] Therefore, \[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 $I_n$ be an integer, we find that \[(2n+1 ) (n+1) = 6k^2,\] where $k$ is an integer. Using the Euclidean algorithm, we see that $\gcd(2n+1, n+1) = \gcd(n+1,n) = 1$, and so $2n+1$ and $n+1$ share no factors greater than 1. The equation above thus implies that $2n+1$ and $n+1$ is each proportional to a perfect square. Since $2n+1$ is odd, there are only two possible cases:

Case 1: $2n+1 = 3 a^2$ and $n+1 = 2b^2$, where $a$ and $b$ are integers.

Case 2: $2n+1 = a^2$ and $n+1 = 6b^2$.

In Case 1, $2n+1 = 4b^2 -1 = 3a^2$. This means that $(4b^2 -1)/3 = a^2$ for some integers $a$ and $b$. We proceed by checking whether $(4b^2-1)/3$ is a perfect square for $b=2, 3, 4, \dots$. (The solution $b=1$ leads to $n=1$, and we are asked to find a value of $n$ greater than 1.) The smallest positive integer $b$ greater than 1 for which $(4b^2-1)/3$ is a perfect square is $b=13$, which results in $n=337$.

In Case 2, $2n+1 = 12b^2 - 1 = a^2$. Note that $a^2 = 2n+1$ is an odd square, and hence is congruent to $1 \pmod 4$. But $12b^2 -1 \equiv 3 \pmod 4$ for any $b$, so Case 2 has no solutions.

Alternatively, one can proceed by checking whether $12b^2 -1$ is a perfect square for $b=1, 2 ,3 ,\dots$. We find that $12b^2 -1$ is not a perfect square for $b = 1,2, 3, ..., 7, 8$, and $n= 383$ when $b=8$. Thus the smallest positive integers $a$ and $b$ for which $12b^2- 1 = a^2$ result in a value of $n$ exceeding the value found in Case 1, which was 337.

In summary, the smallest value of $n$ greater than 1 for which $I_n$ is an integer is $\boxed{337}$.

See Also

1986 USAMO (ProblemsResources)
Preceded by
Problem 2
Followed by
Problem 4
1 2 3 4 5
All USAMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png