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 "2002 USAMO Problems/Problem 1"

 
m
 
(8 intermediate revisions by 6 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
  
−
Let <math> \displaystyle S </math> be a set with 2002 elements, and let <math> \displaystyle N </math> be an integer with <math> 0 \le N \le 2^{2002} </math>.  Prove that it is possible to color every subset of <math> \displaystyle S </math> either blue or red so that the following conditions hold:
+
Let <math>S </math> be a set with 2002 elements, and let <math>N </math> be an integer with <math> 0 \le N \le 2^{2002} </math>.  Prove that it is possible to color every subset of <math>S </math> either blue or red so that the following conditions hold:
  
 
(a) the union of any two red subsets is red;
 
(a) the union of any two red subsets is red;
Line 7: Line 7:
 
(b) the union of any two blue subsets is blue;
 
(b) the union of any two blue subsets is blue;
  
−
(c) there are exactly <math> \displaystyle N </math> subsets.
+
(c) there are exactly <math>N </math> red subsets.
  
 
== Solutions ==
 
== Solutions ==
Line 13: Line 13:
 
=== Solution 1 ===
 
=== Solution 1 ===
  
−
Let a set colored in such a manner be ''properly colored''.  We prove that any set with <math> \displaystyle n </math> elements can be properly colored for any <math> 0 \le N \le 2^n </math>.  We proceed by induction.
+
Let a set colored in such a manner be ''properly colored''.  We prove that any set with <math>n </math> elements can be properly colored for any <math> 0 \le N \le 2^n </math>.  We proceed by induction.
  
−
The base case, <math> \displaystyle n = 0 </math>, is trivial.
+
The base case, <math>n = 0 </math>, is trivial.
  
−
Suppose that our claim holds for <math> \displaystyle n = k </math>.  Let <math> \displaystyle s \in S </math>, <math> \displaystyle |S| = k + 1 </math>, and let <math> \displaystyle S' </math> denote the set of all elements of <math> \displaystyle S </math> other than <math> \displaystyle s </math>.
+
Suppose that our claim holds for <math>n = k </math>.  Let <math>s \in S </math>, <math>|S| = k + 1 </math>, and let <math>S' </math> denote the set of all elements of <math>S </math> other than <math>s </math>.
  
−
If <math> N \le 2^k </math>, then we may collor all subsets of <math> \displaystyle S </math> which contain <math> \displaystyle S </math> blue, and we may properly color <math> \displaystyle S' </math>.  This is a proper coloring because the union of any two red sets must be a subset of <math> \displaystyle S' </math>, which is properly colored, and any the union of any two blue sets either must be in <math> \displaystyle S' </math>, which is properly colored, or must contain <math> \displaystyle s </math> and therefore be blue.
+
If <math> N \le 2^k </math>, then we may color all subsets of <math>S </math> which contain <math>s </math> blue, and we may properly color <math>S' </math>.  This is a proper coloring because the union of any two red sets must be a subset of <math>S' </math>, which is properly colored, and any the union of any two blue sets either must be in <math>S' </math>, which is properly colored, or must contain <math>s </math> and therefore be blue.
  
−
If <math> \displaystyle N > 2^k </math>, then we color all subsets containing <math> \displaystyle s </math> red, and we color <math> \displaystyle N - 2^k </math> elements of <math> \displaystyle S' </math> red in such a way that <math> \displaystyle S' </math> is colored properly.  Then <math> \displaystyle S </math> is properly colored, using similar reasoning as before.  Thus the induction is complete.
+
If <math>N > 2^k </math>, then we color all subsets containing <math>s </math> red, and we color <math>N - 2^k </math> elements of <math>S' </math> red in such a way that <math>S' </math> is colored properly.  Then <math>S </math> is properly colored, using similar reasoning as before.  Thus the induction is complete.
  
 
=== Solution 2 ===
 
=== Solution 2 ===
  
−
If <math> \displaystyle N = 0 </math>, color every subset blue.  If <math> \displaystyle N = 2002 </math>, color every subset red.  Otherwise, let <math> \displaystyle S </math> be <math> \{ 0, 1, \ldots , 2001 \} </math>.  Write <math> \displaystyle N </math> in binary, i.e., let
+
If <math>N = 0 </math>, color every subset blue.  If <math>N = 2^{2002} </math>, color every subset red.  Otherwise, let <math>S </math> be <math> \{ 0, 1, \ldots , 2001 \} </math>.  Write <math>N </math> in binary, i.e., let
 
<center>
 
<center>
 
<math>
 
<math>
Line 31: Line 31:
 
</math>,
 
</math>,
 
</center>
 
</center>
−
where each of the <math> \displaystyle a_i </math> is an element of <math> \displaystyle S </math>.  We color each of the <math> \displaystyle a_i </math> red and all the other elements of <math> S </math> blue.  We color the empty set blue, and we color any other set the color of its largest element.  This satisfies the problem's first two conditions, as the largest element of the union of two red (or blue) sets will have a red (or blue) number as its largest element.  In addition, for each integer <math>n \in S</math>, there are <math> \displaystyle 2^{n} </math> subsets of <math> \displaystyle S </math> with <math> \displaystyle n </math> as a maximal element, so <math> \sum_{i=1}^{k} 2^{a_i} = N </math> subsets of <math> \displaystyle S </math> are colored red, as desired.
+
where each of the <math>a_i </math> is an element of <math>S </math>.  We color each of the <math>a_i </math> red and all the other elements of <math> S </math> blue.  We color the empty set blue, and we color any other set the color of its largest element.  This satisfies the problem's first two conditions, as the largest element of the union of two red (or blue) sets will have a red (or blue) number as its largest element.  In addition, for each integer <math>n \in S</math>, there are <math>2^{n} </math> subsets of <math>S </math> with <math>n </math> as a maximal element, so <math> \sum_{i=1}^{k} 2^{a_i} = N </math> subsets of <math>S </math> are colored red, as desired.
  
  
 
{{alternate solutions}}
 
{{alternate solutions}}
  
−
== Resources ==
+
== See also ==
−
 
+
{{USAMO newbox|year=2002|before=First question|num-a=2}}
−
* [[2002 USAMO Problems]]
 
−
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=337845#p337845 Discussion on AoPS/MathLinks]
 
−
 
 
  
 
[[Category:Olympiad Combinatorics Problems]]
 
[[Category:Olympiad Combinatorics Problems]]
 +
{{MAA Notice}}

Latest revision as of 13:57, 16 June 2020

Problem

Let $S$ be a set with 2002 elements, and let $N$ be an integer with $0 \le N \le 2^{2002}$. Prove that it is possible to color every subset of $S$ either blue or red so that the following conditions hold:

(a) the union of any two red subsets is red;

(b) the union of any two blue subsets is blue;

(c) there are exactly $N$ red subsets.

Solutions

Solution 1

Let a set colored in such a manner be properly colored. We prove that any set with $n$ elements can be properly colored for any $0 \le N \le 2^n$. We proceed by induction.

The base case, $n = 0$, is trivial.

Suppose that our claim holds for $n = k$. Let $s \in S$, $|S| = k + 1$, and let $S'$ denote the set of all elements of $S$ other than $s$.

If $N \le 2^k$, then we may color all subsets of $S$ which contain $s$ blue, and we may properly color $S'$. This is a proper coloring because the union of any two red sets must be a subset of $S'$, which is properly colored, and any the union of any two blue sets either must be in $S'$, which is properly colored, or must contain $s$ and therefore be blue.

If $N > 2^k$, then we color all subsets containing $s$ red, and we color $N - 2^k$ elements of $S'$ red in such a way that $S'$ is colored properly. Then $S$ is properly colored, using similar reasoning as before. Thus the induction is complete.

Solution 2

If $N = 0$, color every subset blue. If $N = 2^{2002}$, color every subset red. Otherwise, let $S$ be $\{ 0, 1, \ldots , 2001 \}$. Write $N$ in binary, i.e., let

$N = \sum_{i=1}^{k} 2^{a_i}$,

where each of the $a_i$ is an element of $S$. We color each of the $a_i$ red and all the other elements of $S$ blue. We color the empty set blue, and we color any other set the color of its largest element. This satisfies the problem's first two conditions, as the largest element of the union of two red (or blue) sets will have a red (or blue) number as its largest element. In addition, for each integer $n \in S$, there are $2^{n}$ subsets of $S$ with $n$ as a maximal element, so $\sum_{i=1}^{k} 2^{a_i} = N$ subsets of $S$ are colored red, as desired.


Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

See also

2002 USAMO (Problems • Resources)
Preceded by
First question 		Followed by
Problem 2
1 • 2 • 3 • 4 • 5 • 6
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

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