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)
(Added a 3rd Solution)
 
(9 intermediate revisions by 7 users not shown)
Line 1: Line 1:
 +
==Problem==
 +
Let <math> \, k_1 < k_2 < k_3 <\cdots\, </math>, be positive integers, no two consecutive, and let <math> \, s_m = k_1+k_2+\cdots+k_m\, </math>, for <math> \, m = 1,2,3,\ldots\;\; </math>. Prove that, for each positive integer <math>n</math>, the interval <math> \, [s_n, s_{n+1})\, </math>, contains at least one perfect square.
 +
 
==Solution==
 
==Solution==
 +
We want to show that the distance between <math>s_n</math> and <math>s_{n+1}</math> is greater than the distance between <math>s_n</math> and the next perfect square following <math>s_n</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*}
 +
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*}
 +
</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>.
 +
 +
Also, let <math>d(s_n)</math> be the distance between <math>s_n</math> and the next perfect square following <math>s_n</math>. Let's look at the function <math>d(x)</math> for all positive integers <math>x</math>.
 +
 +
When <math>x</math> is a perfect square, it is easy to see that <math>d(x)=2\sqrt{x}+1</math>.
 +
Proof: Choose <math>x=m^2</math>. <math>d(m^2)=(m+1)^2-m^2=2m+1=2\sqrt{m^2}+1</math>.
 +
 +
When <math>x</math> is not a perfect square, <math>d(x)<2\sqrt{x}+1</math>.
 +
Proof: Choose <math>x=m^2+p</math> with <math>0<p<2m+1</math>. <math>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</math>.
 +
 +
So, <math>d(x)\leq 2\sqrt{x}+1</math> for all <math>x</math> and <math>d(s_n)\leq 2\sqrt{s_n}+1</math> for all <math>s_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*}
 +
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>
 +
 +
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.
 +
 +
==Solution 2==
 +
 +
We see that by increasing <math>n</math> by some amount, we simply shift our interval by a finite amount. It suffices to consider the case <math>n=1</math> (since this can be inducted across all positive integers). Let <math>k_1=x</math>. We want the smallest interval, so we have <math>[x, 2x+2]</math>. Simple induction reveals that the ration of consecutive squares grows slower than our linear bound. We now consider sufficiently small <math>x</math> (where <math>\frac{(n+1)^2}{n^2}<2</math>). This first happens at <math>n=3</math>. By simple casework, our answer is as desired <math>\blacksquare</math>.
 +
 +
 +
==Solution 3==
 +
We will first prove by Induction on <math>n\in\mathbb{N}</math> that <math>(k_{n}+1)^2\geq4(k_1+k_2+\cdots +k_{n}).</math> Denote this statement by <math>P(n).</math>
 +
 +
For the Base Case let <math>n=1,</math> we know that;
 +
<cmath>(k_1-1)^2\geq 0</cmath>
 +
<cmath>\Rightarrow k_1^2-2k_1+1\geq 0</cmath>
 +
<cmath>\Rightarrow k_1^2+2k_1+1\geq 4k_1</cmath>
 +
<cmath>\Rightarrow (k_1+1)^2\geq 4k_1.</cmath>
 +
 +
Hence, the Base Case holds.
 +
 +
For the Inductive Step, suppose that <math>P(m)</math> holds for some <math>k\in\mathbb{N},</math> we will prove that <math>P(m+1)</math> holds as well.
 +
 +
Assume for contradiction that <math>P(m+1)</math> doesn't hold, then we know that;
 +
<cmath>(k_m+1)^2<4(k_1+k_2+\cdots +k_m)</cmath>
 +
<cmath>\Rightarrow k_m^2+2k_m+1<4(k_1+k_2+\cdots +k_{m-1})+4k_m</cmath>
 +
<cmath>\Rightarrow k_m^2-2k_m+1<4(k_1+k_2+\cdots +k_{m-1})</cmath>
 +
<cmath>\Rightarrow (k_m-1)^2<4(k_1+k_2+\cdots +k_{m-1}).</cmath>
 +
 +
We know that since <math>k_m</math> and <math>k_{m-1}</math> are not consecutive, we have;
 +
<cmath>k_{m-1}\geq k_m-2</cmath>
 +
<cmath>\Rightarrow k_{m-1}+1\leq k_m-1</cmath>
 +
<cmath>\Rightarrow (k_{m-1}+1)^2\leq (k_m-1)^2</cmath>
 +
<cmath>\Rightarrow (k_{m-1}+1)^2\leq (k_m-1)^2<4(k_1+k_2+\cdots +k_{m-1}).</cmath>
 +
 +
But this contradicts the Inductive Hypothesis that <cmath>\Rightarrow (k_{m-1}+1)^2\geq 4(k_1+k_2+\cdots +k_{m-1}),</cmath> thus our assumption was false and the Inductive Step is complete.
 +
 +
Hence, we have proved that <math>P(n)</math> holds, and we will use <math>P(n)</math> to solve the original problem.
 +
 +
 +
Now suppose that for some positive integer <math>n</math>, the interval <math>\, [s_n, s_{n+1})\,</math> 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 <math>s_n</math> and the larger one greater than or equal to <math>s_{n+1}.</math>
 +
 +
We thus know that there exists some <math>x\in\mathbb{N}</math> such that;
 +
<cmath>
 +
\begin{eqnarray}
 +
x^2<s_n \\
 +
\text{and }(x+1)^2\geq s_{n+1}
 +
\end{eqnarray}
 +
</cmath>
 +
 +
By Inequality 1;
 +
<cmath>
 +
\begin{align*}
 +
x
 +
&<\sqrt{s_n}\\
 +
&=\sqrt{k_1+k_2+\cdots+k_n}.\\
 +
\end{align*}
 +
</cmath>
 +
  
−
Induct on <math>n</math>. When <math>n = 1</math>, we are to show that the interval <math>\, [s_n, s_{n + 1}) \,</math> contains at least one perfect square. This interval is equivalent to <math>\, [k_0, k_0 + k_1) \,</math> when <math>n = 1</math>. Now for some <math>a , a^2 \le k_0^2 < (a+1)^2</math>.Then it suffices to show that the minimal "distance spanned" by the interval <math>\, [k_0, k_0 + k_1) \,</math> is greater than or equal to the maximum distance from <math>k_0</math> to the nearest perfect square. Since the smallest element that can follow <math>k_0</math> is <math>k_0 + 2</math>, we have to show the below. Note that we ignore the trivial case where <math>k_0 = a^2</math>, which should be mentioned.
+
Hence, we know that;
 +
<cmath>
 +
\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*}
 +
</cmath>
  
−
  <math>2a + 1 \le k_0 + 2</math>
+
Combining this with Inequality 2 gives;
−
  <math>2a \le k_0 + 1</math>
+
<cmath>s_{n+1}\leq (x+1)^2<k_1+k_2+\cdots+k_n+2\sqrt{k_1+k_2+\cdots+k_n}+1</cmath>
−
  <math>2a \le k_0 + (q + 1), where q is a member of </math>\{1, 2, \ldots, 2\a}<math>
+
<cmath>\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</cmath>
−
  </math>We now prove by contradiction. Assume that
+
<cmath>\Rightarrow k_{n+1}<2\sqrt{k_1+k_2+\cdots+k_n}+1</cmath>
 +
<cmath>\Rightarrow k_{n+1}-1<2\sqrt{k_1+k_2+\cdots+k_n}.</cmath>
  
  
−
  <math>2a > a^2 + q + 1
+
We know that since <math>k_{n+1}</math> are not consecutive, <math>k_n+1\leq k_{n+1}-1,</math> hence, we have;
−
  a^2 - 2a + (q + 1) < 0
+
<cmath>k_{n+1}\leq k_{n+1}-1<2\sqrt{k_1+k_2+\cdots+k_n}</cmath>
−
  No real roots (Discriminant < 0)
+
<cmath>k_{n+1}<2\sqrt{k_1+k_2+\cdots+k_n}</cmath>
−
  =><= </math>
+
<cmath>(k_{n+1}^2<4(k_1+k_2+\cdots+k_n).</cmath>
  
−
<math>Now assume that this property should be true for </math>\, [s_{n - 1}, s_{n}) \,<math>. Now to show for </math>\, [s_n, s_{n + 1}) \,<math>, we note that an interval is defined solely by the sum of the elements in the respective sets and '''not''' on the length of the set. Thus any s_{n + 1} can be turned into an s_n by removing k_{n + 1} and adding it to k_n. The new set is now in a form to which we can apply our assumption. The same goes for s_n and s_{n - 1}. Thus we have finished the inductive argument.
 
  
−
Therefore etc.</math>
+
But this contradicts the statement <math>P(n)</math> which was proved earlier.
 +
<math>\square</math>
 +
==See Also==
 +
{{USAMO box|year=1994|before=First Problem|num-a=2}}
 +
{{MAA Notice}}
 +
[[Category:Olympiad Number Theory Problems]]

Latest revision as of 05:09, 8 December 2020

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

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=139226"