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

God of Math (talk | contribs) (Created page with '==Solution== 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 i…') |
God of Math (talk | contribs) (→Solution) |
||

Line 3: | Line 3: | ||

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. | 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. | ||

− | + | <math>2a + 1 \le k_0 + 2</math> | |

<math>2a \le k_0 + 1</math> | <math>2a \le k_0 + 1</math> | ||

<math>2a \le k_0 + (q + 1), where q is a member of </math>\{1, 2, \ldots, 2\a}<math> | <math>2a \le k_0 + (q + 1), where q is a member of </math>\{1, 2, \ldots, 2\a}<math> | ||

Line 12: | Line 12: | ||

a^2 - 2a + (q + 1) < 0 | a^2 - 2a + (q + 1) < 0 | ||

No real roots (Discriminant < 0) | No real roots (Discriminant < 0) | ||

− | =><= | + | =><= </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>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. | + | Therefore etc.</math> |

## Revision as of 06:26, 11 July 2009

## Solution

Induct on . When , we are to show that the interval contains at least one perfect square. This interval is equivalent to when . Now for some .Then it suffices to show that the minimal "distance spanned" by the interval is greater than or equal to the maximum distance from to the nearest perfect square. Since the smallest element that can follow is , we have to show the below. Note that we ignore the trivial case where , which should be mentioned.

```
\{1, 2, \ldots, 2\a}$$ (Error compiling LaTeX. Unknown error_msg)We now prove by contradiction. Assume that
```

\, [s_{n - 1}, s_{n}) \,\, [s_n, s_{n + 1}) \,$, 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.$ (Error compiling LaTeX. Unknown error_msg)