Difference between revisions of "1994 USAMO Problems/Problem 1"

Revision as of 13:46, 1 June 2015

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.

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.

Page

Toolbox

Search

Difference between revisions of "1994 USAMO Problems/Problem 1"

Revision as of 13:46, 1 June 2015

Solution

@@ Line 6: / Line 6: @@
 Given <math>s_n=\sum_{i=1}^{n}k_i</math>, where no <math>k_i</math> are consecutive, we can put a lower bound on <math>k_n</math>. This occurs when all <math>k_{i+1}=k_i+2</math>:
-<cmath>\begin{align*}
+<cmath>
+\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\\
-&=nk_{n,min}-n^2+n
+\end{align*}
-\end{align*}</cmath>
+</cmath>
 Rearranging, <math>k_{n,min}=\frac{s_n}{n}+n-1</math>. So, <math>k_n\geq\frac{s_n}{n}+n-1</math>, and the distance between <math>s_n</math> and <math>s_{n+1}</math> is <math>k_{n+1}\geq k_n+2\geq\frac{s_n}{n}+n+1</math>.
@@ Line 32: / Line 30: @@
 Now, it suffices to show that <math>k_{n+1}\geq d(s_n)</math> for all <math>n</math>.
-<cmath>\begin{align*}
+<cmath>
+\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*}</cmath>
+\end{align*}
+</cmath>
 So, <math>k_{n+1}\geq d(s_n)</math> and all intervals between <math>s_n</math> and <math>s_{n+1}</math> will contain at least one perfect square.
 {{MAA Notice}}