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

(→Solution) |
Mathgeek2006 (talk | contribs) 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 13:46, 1 June 2015

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.

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