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

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

(→‎Solution)
m (→‎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>:
 
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)\\
 
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}-\sum_{i=1}^{n-1}2i\\
−
 
 
&=nk_{n,min}-2\sum_{i=1}^{n}i+2n\\
 
&=nk_{n,min}-2\sum_{i=1}^{n}i+2n\\
−
 
 
&=nk_{n,min}-n(n+1)+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>.
 
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>.
 
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\\
 
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{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^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})}\\
 
&=\frac{(s_n-n^2)^2}{n(s_n+n^2+2n\sqrt{s_n})}\\
−
 
 
&\geq 0
 
&\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.
 
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}}
 
{{MAA Notice}}

Revision as of 12: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. AMC logo.png

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