Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

1986 USAMO Problems/Problem 3

Revision as of 09:21, 15 September 2014 by Glaivericochet (talk | contribs) (Created page with " Let's first obtain an algebraic expression for the root mean square of the first <math>n</math> integers, which we denote <math>I_n</math>. By repeatedly using the identity <mat...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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) = 6p^2,\] where $p$ 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$. We 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}$.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1986_USAMO_Problems/Problem_3&oldid=63402"