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"

(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…')
 
(→‎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 + 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}) \,$, 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.  
+
<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 05:26, 11 July 2009

Solution

Induct on $n$. When $n = 1$, we are to show that the interval $\, [s_n, s_{n + 1}) \,$ contains at least one perfect square. This interval is equivalent to $\, [k_0, k_0 + k_1) \,$ when $n = 1$. Now for some $a , a^2 \le k_0^2 < (a+1)^2$.Then it suffices to show that the minimal "distance spanned" by the interval $\, [k_0, k_0 + k_1) \,$ is greater than or equal to the maximum distance from $k_0$ to the nearest perfect square. Since the smallest element that can follow $k_0$ is $k_0 + 2$, we have to show the below. Note that we ignore the trivial case where $k_0 = a^2$, which should be mentioned. 

 $2a + 1 \le k_0 + 2$
  $2a \le k_0 + 1$
  $2a \le k_0 + (q + 1), where q is a member of$\{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$\, [s_{n - 1}, s_{n}) \,$. Now to show for$\, [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)

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1994_USAMO_Problems/Problem_1&oldid=32288"