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…') |
(No difference)
|
Revision as of 05:25, 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
$2a > a^2 + q + 1
a^2 - 2a + (q + 1) < 0
No real roots (Discriminant < 0)
=><=
Now assume that this property should be true for$ (Error compiling LaTeX. Unknown error_msg)\, [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.