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

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?

$\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) = 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}$ .

@@ Line 2: / Line 2: @@
 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>
+==Solution==
 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
 <math>(x+1)^3 = x^3 + 3x^2 + 3x + 1</math>, we can write

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

Page

Toolbox

Search

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

Revision as of 14:49, 18 July 2016

Problem

Solution

See Also