Difference between revisions of "1994 USAMO Problems/Problem 1"
(Added a 3rd Solution) |
|||
(7 intermediate revisions by 5 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> | ||
+ | |||
+ | |||
+ | 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> | ||
+ | |||
+ | Combining this with Inequality 2 gives; | ||
+ | <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> | ||
+ | <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> | ||
+ | <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> | ||
+ | |||
+ | |||
+ | 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; | ||
+ | <cmath>k_{n+1}\leq k_{n+1}-1<2\sqrt{k_1+k_2+\cdots+k_n}</cmath> | ||
+ | <cmath>k_{n+1}<2\sqrt{k_1+k_2+\cdots+k_n}</cmath> | ||
+ | <cmath>(k_{n+1}^2<4(k_1+k_2+\cdots+k_n).</cmath> | ||
+ | |||
+ | |||
+ | 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}} | {{MAA Notice}} | ||
+ | [[Category:Olympiad Number Theory Problems]] |
Latest revision as of 05:09, 8 December 2020
Problem
Let , be positive integers, no two consecutive, and let , for . Prove that, for each positive integer , the interval , contains at least one perfect square.
Solution
We want to show that the distance between and is greater than the distance between and the next perfect square following .
Given , where no are consecutive, we can put a lower bound on . This occurs when all :
Rearranging, . So, , and the distance between and is .
Also, let be the distance between and the next perfect square following . Let's look at the function for all positive integers .
When is a perfect square, it is easy to see that . Proof: Choose . .
When is not a perfect square, . Proof: Choose with . .
So, for all and for all .
Now, it suffices to show that for all .
So, and all intervals between and will contain at least one perfect square.
Solution 2
We see that by increasing by some amount, we simply shift our interval by a finite amount. It suffices to consider the case (since this can be inducted across all positive integers). Let . We want the smallest interval, so we have . Simple induction reveals that the ration of consecutive squares grows slower than our linear bound. We now consider sufficiently small (where ). This first happens at . By simple casework, our answer is as desired .
Solution 3
We will first prove by Induction on that Denote this statement by
For the Base Case let we know that;
Hence, the Base Case holds.
For the Inductive Step, suppose that holds for some we will prove that holds as well.
Assume for contradiction that doesn't hold, then we know that;
We know that since and are not consecutive, we have;
But this contradicts the Inductive Hypothesis that thus our assumption was false and the Inductive Step is complete.
Hence, we have proved that holds, and we will use to solve the original problem.
Now suppose that for some positive integer , the interval 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 and the larger one greater than or equal to
We thus know that there exists some such that;
By Inequality 1;
Hence, we know that;
Combining this with Inequality 2 gives;
We know that since are not consecutive, hence, we have;
But this contradicts the statement which was proved earlier.
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.