USAMO Problem 2

Number Theory Level 4

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

This problem is part of this set .

The answer is 337.

1 solution

Martin Sergio H. Faester
Apr 12, 2015

The sum of the first $n$ consecutive squares is known as the $n$ 'th pyramid number. The formula for such a number is $P_n = \frac{n(n+1)(2n+1)}{6}$

So the problem we are asked to solve corresponds to solving the equation $\sqrt{\frac{P_n}{n}} = y$ where $y$ is some positive integer.

Notice that we can rewrite the equation above as $\begin{aligned} \sqrt{\frac{P_n}{n}} & = y \Rightarrow \\ \frac{1}{6}(n+1)(2n+1) & = y^2 \Rightarrow \\ 2n^2+3n+1 & = 6y^2 \Rightarrow \\ 2\left(n+\frac{3}{4}\right)^2 - \frac{1}{8} & = 6y^2 \Rightarrow \\ (4n+3)^2 - 48y^2 & = 1 \end{aligned}$ If we let $x = 4n + 3$ then we are looking for solutions to the Pell equation for which $x \equiv 3 \pmod{4}$ . For a moment, leave aside the extra restriction on $x$ .

It is easy to see that $(x, y) = (7, 1)$ is a solution to $x^2 - 48y^2 = 1$ . Observe that if $(x_0, y_0)$ is a solution then computing $(x_0 + \sqrt{48} y_0 )^k = x_k + \sqrt{48} y_k$ yields another solution $( x_k, y_k )$ for any $k$ .

A few hand calculations generate the following solutions $(7, 1), (97, 14), (1351, 195), (18817, 2716), \ldots$ The least ''non-trivial'' $x$ -value that is congruent to 3 modulo 4 is $x = 1351$ . Thus, $n = \frac{1351 - 3}{4} = \boxed{337}$

Oh damn got till that Pell's equation(not by this method though) but just forgot that formula right now(ah darn me) for its solution so had to use programming. Thanks for the Pell's equations

Kartik Sharma - 6 years, 2 months ago

What's the proof? Had to do something with generating functions?

Kartik Sharma - 6 years, 2 months ago

Without going into details, say we have a solution $(x_0, y_0)$ , in our case the minimal solution, then let us rewrite the following $\begin{aligned} x_k^2 - 48 y_k^2 & = (x_0^2 - 48 y_0^2)^k = 1 \Rightarrow \\ (x_k + \sqrt{48} y_k)(x_k - \sqrt{48} y_k) & = (x_0 + \sqrt{48} y_0)^k (x_0 - \sqrt{48} y_0)^k \end{aligned}$ So $\begin{aligned} x_k + \sqrt{48} y_k & = (x_0 + \sqrt{48} y_0)^k \\ x_k - \sqrt{48} y_k & = (x_0 - 4\sqrt{48} y_0)^k \Rightarrow \\ x_k + \sqrt{48} y_k + (x_k - \sqrt{48} y_k) & = (x_0 + 4\sqrt{3} y_0)^k + (x_0 - 4\sqrt{3} y_0)^k \\ \Rightarrow x_k & = \frac{(x_0 + 4\sqrt{3} y_0)^k + (x_0 - 4\sqrt{3} y_0)^k}{2} \end{aligned}$ We can do similarly for $y_k$ .

The formula above is not the most convenient way of generating solutions by hand. I have revised my solution a bit such that it applies a slightly easier technique to generate solutions.

Martin Sergio H. Faester - 6 years, 1 month ago

Nice! Took me a while to notice the Pell equation.

Jake Lai - 6 years, 2 months ago

USAMO Problem 2

This problem is part of this set .

The answer is 337.

1 solution

0 pending reports