Art of Problem Solving
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

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


Solution 3

We will first prove by Induction on $n\in\mathbb{N}$ that $(k_{n}+1)^2\geq4(k_1+k_2+\cdots +k_{n}).$ Denote this statement by $P(n).$

For the Base Case let $n=1,$ we know that; \[(k_1-1)^2\geq 0\] \[\Rightarrow k_1^2-2k_1+1\geq 0\] \[\Rightarrow k_1^2+2k_1+1\geq 4k_1\] \[\Rightarrow (k_1+1)^2\geq 4k_1.\]

Hence, the Base Case holds.

For the Inductive Step, suppose that $P(m)$ holds for some $k\in\mathbb{N},$ we will prove that $P(m+1)$ holds as well.

Assume for contradiction that $P(m+1)$ doesn't hold, then we know that; \[(k_m+1)^2<4(k_1+k_2+\cdots +k_m)\] \[\Rightarrow k_m^2+2k_m+1<4(k_1+k_2+\cdots +k_{m-1})+4k_m\] \[\Rightarrow k_m^2-2k_m+1<4(k_1+k_2+\cdots +k_{m-1})\] \[\Rightarrow (k_m-1)^2<4(k_1+k_2+\cdots +k_{m-1}).\]

We know that since $k_m$ and $k_{m-1}$ are not consecutive, we have; \[k_{m-1}\geq k_m-2\] \[\Rightarrow k_{m-1}+1\leq k_m-1\] \[\Rightarrow (k_{m-1}+1)^2\leq (k_m-1)^2\] \[\Rightarrow (k_{m-1}+1)^2\leq (k_m-1)^2<4(k_1+k_2+\cdots +k_{m-1}).\]

But this contradicts the Inductive Hypothesis that \[\Rightarrow (k_{m-1}+1)^2\geq 4(k_1+k_2+\cdots +k_{m-1}),\] thus our assumption was false and the Inductive Step is complete.

Hence, we have proved that $P(n)$ holds, and we will use $P(n)$ to solve the original problem.


Now suppose that for some positive integer $n$, the interval $\, [s_n, s_{n+1})\,$ does not contain any perfect square, then we know that there must exist two perfect squares of consecutive integers, such that the smaller one is lesser than $s_n$ and the larger one greater than or equal to $s_{n+1}.$

We thus know that there exists some $x\in\mathbb{N}$ such that; \begin{eqnarray} x^2<s_n \\ \text{and }(x+1)^2\geq s_{n+1} \end{eqnarray}

By Inequality 1; \begin{align*} x &<\sqrt{s_n}\\ &=\sqrt{k_1+k_2+\cdots+k_n}.\\ \end{align*}


Hence, we know that; \begin{align*} (x+1)^2 &<(\sqrt{k_1+k_2+\cdots+k_n}+1)^2\\ &=k_1+k_2+\cdots+k_n+2\sqrt{k_1+k_2+\cdots+k_n}+1. \end{align*}

Combining this with Inequality 2 gives; \[s_{n+1}\leq (x+1)^2<k_1+k_2+\cdots+k_n+2\sqrt{k_1+k_2+\cdots+k_n}+1\] \[\Rightarrow k_1+k_2+\cdots+k_n+k_{n+1}<k_1+k_2+\cdots+k_n+2\sqrt{k_1+k_2+\cdots+k_n}+1\] \[\Rightarrow k_{n+1}<2\sqrt{k_1+k_2+\cdots+k_n}+1\] \[\Rightarrow k_{n+1}-1<2\sqrt{k_1+k_2+\cdots+k_n}.\]


We know that since $k_{n+1}$ are not consecutive, $k_n+1\leq k_{n+1}-1,$ hence, we have; \[k_{n+1}\leq k_{n+1}-1<2\sqrt{k_1+k_2+\cdots+k_n}\] \[k_{n+1}<2\sqrt{k_1+k_2+\cdots+k_n}\] \[(k_{n+1}^2<4(k_1+k_2+\cdots+k_n).\]


But this contradicts the statement $P(n)$ which was proved earlier. $\square$

See Also

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

These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions. Error creating thumbnail: File missing

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1994_USAMO_Problems/Problem_1&oldid=139226"