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

Difference between revisions of "1986 USAMO Problems/Problem 3"

(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...")
 
Line 1: Line 1:
 +
==Problem==
 +
What is the smallest integer <math>n</math>, greater than one, for which the root-mean-square of the first <math>n</math> positive integers is an integer?
 +
 +
==Solution==
 +
<math>\mathbf{Note.}</math> The root-mean-square of <math>n</math> numbers <math>a_1, a_2, \cdots, a_n</math> is defined to be
 +
<cmath>\left[\frac{a_1^2 + a_2^2 + \cdots + a_n^2}n\right]^{1/2}</cmath>
  
 
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
 
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
Line 41: Line 47:
  
 
In summary, the smallest value of <math>n</math> greater than 1 for which <math>I_n</math> is an integer is <math>\boxed{337}</math>.
 
In summary, the smallest value of <math>n</math> greater than 1 for which <math>I_n</math> is an integer is <math>\boxed{337}</math>.
 +
 +
==See Also==
 +
{{USAMO box|year=1986|num-b=2|num-a=4}}
 +
{{MAA Notice}}
 +
[[Category:Olympiad Number Theory Problems]]

Revision as of 14:49, 18 July 2016

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?

Solution

$\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}\]

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}$.

See Also

1986 USAMO (Problems • Resources)
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

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