1994 USAMO Problems/Problem 1

Problem

Let $\, k_1 < k_2 < k_3 <\cdots\,$ , be positive integers, no two consecutive, and let $\, s_m = k_1+k_2+\cdots+k_m\,$ , for $\, m = 1,2,3,\ldots\;\;$ . Prove that, for each positive integer $n$ , the interval $\, [s_n, s_{n+1})\,$ , contains at least one perfect square.

Solution

We want to show that the distance between $s_n$ and $s_{n+1}$ is greater than the distance between $s_n$ and the next perfect square following $s_n$ .

Given $s_n=\sum_{i=1}^{n}k_i$ , where no $k_i$ are consecutive, we can put a lower bound on $k_n$ . This occurs when all $k_{i+1}=k_i+2$ :

$\begin{align*} s_n&=(k_{n,min})+(k_{n,min}-2)+(k_{n,min}-4)+\dots+(k_{n,min}-2n+2)\\ &=nk_{n,min}-\sum_{i=1}^{n-1}2i\\ &=nk_{n,min}-2\sum_{i=1}^{n}i+2n\\ &=nk_{n,min}-n(n+1)+2n\\ &=nk_{n,min}-n^2+n\\ \end{align*}$

Rearranging, $k_{n,min}=\frac{s_n}{n}+n-1$ . So, $k_n\geq\frac{s_n}{n}+n-1$ , and the distance between $s_n$ and $s_{n+1}$ is $k_{n+1}\geq k_n+2\geq\frac{s_n}{n}+n+1$ .

Also, let $d(s_n)$ be the distance between $s_n$ and the next perfect square following $s_n$ . Let's look at the function $d(x)$ for all positive integers $x$ .

When $x$ is a perfect square, it is easy to see that $d(x)=2\sqrt{x}+1$ . Proof: Choose $x=m^2$ . $d(m^2)=(m+1)^2-m^2=2m+1=2\sqrt{m^2}+1$ .

When $x$ is not a perfect square, $d(x)<2\sqrt{x}+1$ . Proof: Choose $x=m^2+p$ with $0<p<2m+1$ . $d(m^2+p)=(m+1)^2-m^2-p=2m+1-p<2m+1=2\sqrt{m^2}+1<2\sqrt{m^2+p}+1$ .

So, $d(x)\leq 2\sqrt{x}+1$ for all $x$ and $d(s_n)\leq 2\sqrt{s_n}+1$ for all $s_n$ .

Now, it suffices to show that $k_{n+1}\geq d(s_n)$ for all $n$ .

$\begin{align*} k_{n+1}-d(s_n)&\geq \frac{s_n}{n}+n+1-2\sqrt{s_n}-1\\ &=\frac{1}{n}(s_n+n^2-2n\sqrt{s_n})\\ &=\frac{s_n^2+n^4+2n^2s_n-4n^2s_n}{n(s_n+n^2+2n\sqrt{s_n})}\\ &=\frac{(s_n-n^2)^2}{n(s_n+n^2+2n\sqrt{s_n})}\\ &\geq 0 \end{align*}$

So, $k_{n+1}\geq d(s_n)$ and all intervals between $s_n$ and $s_{n+1}$ will contain at least one perfect square.

Solution 2

We see that by increasing $n$ by some amount, we simply shift our interval by a finite amount. It suffices to consider the case $n=1$ (since this can be inducted across all positive integers). Let $k_1=x$ . We want the smallest interval, so we have $[x, 2x+2]$ . Simple induction reveals that the ration of consecutive squares grows slower than our linear bound. We now consider sufficiently small $x$ (where $\frac{(n+1)^2}{n^2}<2$ ). This first happens at $n=3$ . By simple casework, our answer is as desired $\blacksquare$ .

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

Page

Toolbox

Search

1994 USAMO Problems/Problem 1

Contents

Problem

Solution

Solution 2

See Also