Difference between revisions of "1994 USAMO Problems"

(Added Problem 5)
 
(6 intermediate revisions by 4 users not shown)
Line 6: Line 6:
  
 
[[1994 USAMO Problems/Problem 1|Solution]]
 
[[1994 USAMO Problems/Problem 1|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 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 + (q + 1)</math>, where <math>q</math> is a member of <math>\{1, 2, \ldots, 2\a}</math>
 
  We now prove by contradiction. Assume that
 
  
 
==Problem 2==
 
==Problem 2==
 
+
The sides of a 99-gon are initially colored so that consecutive sides are red, blue, red, blue, ... red, blue, yellow. We make a sequence of modifications in the coloring, changing the color of one side at a time to one of the three given colors (red, blue, yellow), under the constraint that no two adjacent sides may be the same color. By making a sequence of such modifications, is it possible to arrive at the coloring in which consecutive sides  
The sides of a 99-gon are initially colored so that consecutive sides are red, blue, red, blue,  red, blue, yellow. We make a sequence of modifications in the coloring, changing the color of one side at a time to one of the three given colors (red, blue, yellow), under the constraint that no two adjacent sides may be the same color. By making a sequence of such modifications, is it possible to arrive at the coloring in which consecutive sides  
+
are red, blue, red, blue, red, blue, ... red, yellow, blue?
are red, blue, red, blue, red, blue,  red, yellow, blue?
 
  
 
[[1994 USAMO Problems/Problem 2|Solution]]
 
[[1994 USAMO Problems/Problem 2|Solution]]
Line 37: Line 28:
  
 
==Problem 5==
 
==Problem 5==
 
+
Let <math>\, |U|, \, \sigma(U) \,</math> and <math>\, \pi(U) \,</math> denote the number of elements, the sum, and the product, respectively, of a finite set <math>\, U \,</math> of positive integers.  (If <math>\, U \,</math> is the empty set, <math>\, |U| = 0, \, \sigma(U) = 0, \, \pi(U) = 1</math>.) Let <math>\, S \,</math> be a finite set of positive integers. As usual, let <math>\, \binom{n}{k} \,</math> denote <math>\, n! \over k! \, (n-k)!</math>. Prove that <cmath> \sum_{U \subseteq S} (-1)^{|U|} \binom{m - \sigma(U)}{|S|} = \pi(S) </cmath> for all integers <math>\, m \geq \sigma(S)</math>.
Let <math>\, |U|, \, \sigma(U) \,</math> and <math>\, \pi(U) \,</math> denote the number of elements, the sum, and the product, respectively, of a finite set <math>\, U \,</math> of positive integers.  (If <math>\, U \,</math> is the empty set, <math>\, |U| = 0, \, \sigma(U) = 0, \, \pi(U) = 1</math>.) Let <math>\, S \,</math> be a finite set of positive integers. As usual, let <math>\, \binom{n}{k} \,</math> denote <math>\, n! \over k! \, (n - k)!</math>. Prove that
 
 
 
<cmath>\sum_{U \subseteq S} ( - 1)^{|U|} \binom{m - \sigma(U)}{|S|} = \pi(S)</cmath>
 
 
 
for all integers <math>\, m \geq \sigma(S)</math>.
 
  
 
[[1994 USAMO Problems/Problem 5|Solution]]
 
[[1994 USAMO Problems/Problem 5|Solution]]
  
== Resources ==
+
== See Also ==
 
 
 
{{USAMO box|year=1994|before=[[1993 USAMO]]|after=[[1995 USAMO]]}}
 
{{USAMO box|year=1994|before=[[1993 USAMO]]|after=[[1995 USAMO]]}}
 
+
{{MAA Notice}}
* [http://www.artofproblemsolving.com/Forum/resources.php?c=182&cid=27&year=1994 1994 USAMO Problems on the resources page]
 

Latest revision as of 07:58, 19 July 2016

Problems of the 1994 USAMO.

Problem 1

Let $\, k_1 < k_2 < k_3 < \cdots \,$ be positive integers, no two consecutive, and let $\, s_m = k_1 + k_2 + \cdots + k_m \,$ for $\, m = 1,2,3, \ldots \; \;$. Prove that, for each positive integer $\, n, \,$ the interval $\, [s_n, s_{n + 1}) \,$ contains at least one perfect square.

Solution

Problem 2

The sides of a 99-gon are initially colored so that consecutive sides are red, blue, red, blue, ... red, blue, yellow. We make a sequence of modifications in the coloring, changing the color of one side at a time to one of the three given colors (red, blue, yellow), under the constraint that no two adjacent sides may be the same color. By making a sequence of such modifications, is it possible to arrive at the coloring in which consecutive sides are red, blue, red, blue, red, blue, ... red, yellow, blue?

Solution

Problem 3

A convex hexagon $ABCDEF$ is inscribed in a circle such that $AB = CD = EF$ and diagonals $AD$, $BE$, and $CF$ are concurrent. Let $P$ be the intersection of $AD$ and $CE$. Prove that $CP/PE = (AC/CE)^2$.

Solution

Problem 4

Let $\, a_1, a_2, a_3, \ldots \,$ be a sequence of positive real numbers satisfying $\, \sum_{j = 1}^n a_j \geq \sqrt {n} \,$ for all $\, n \geq 1$. Prove that, for all $\, n \geq 1, \,$

\[\sum_{j = 1}^n a_j^2 > \frac {1}{4} \left( 1 + \frac {1}{2} + \cdots + \frac {1}{n} \right).\]

Solution

Problem 5

Let $\, |U|, \, \sigma(U) \,$ and $\, \pi(U) \,$ denote the number of elements, the sum, and the product, respectively, of a finite set $\, U \,$ of positive integers. (If $\, U \,$ is the empty set, $\, |U| = 0, \, \sigma(U) = 0, \, \pi(U) = 1$.) Let $\, S \,$ be a finite set of positive integers. As usual, let $\, \binom{n}{k} \,$ denote $\, n! \over k! \, (n-k)!$. Prove that \[\sum_{U \subseteq S} (-1)^{|U|} \binom{m - \sigma(U)}{|S|} = \pi(S)\] for all integers $\, m \geq \sigma(S)$.

Solution

See Also

1994 USAMO (ProblemsResources)
Preceded by
1993 USAMO
Followed by
1995 USAMO
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. AMC logo.png

Invalid username
Login to AoPS