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 "2007 USAMO Problems/Problem 3"

(→‎Solution)
m (wikify, i guess set theory -> combinatorics category?)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
  
−
Let <math>S</math> be a set containing <math>n^2+n-1</math> elements, for some positive integer <math>n</math>.  Suppose that the <math>n</math>-element subsets of <math>S</math> are partitioned into two classes.  Prove that there are at least <math>n</math> pairwise disjoint sets in the same class.
+
Let <math>S</math> be a [[set]] containing <math>\displaystyle n^2+n-1</math> [[element]]s, for some [[positive]] [[integer]] <math>n</math>.  Suppose that the <math>n</math>-element [[subset]]s of <math>S</math> are partitioned into two classes.  Prove that there are at least <math>n</math> [[pairwise disjoint]] sets in the same class.
  
 
== Solution ==
 
== Solution ==
  
−
Call an <math>n+1</math>-element subset of <math>S</math> seperable if it has a subset in each class of the partition. We recursively build a set <math>Q</math> of disjoint seperable subsets of <math>S</math>: begin with <math>Q</math> empty and at each step if there is a seperable subset which is disjoint from all sets in <math>Q</math> add that set to <math>Q</math>. The process terminates when every seperable subset intersects a set in <math>Q</math>. Let <math>T</math> be the set of elements in <math>S</math> which are not in any set in <math>Q</math>. We claim that one class contains every <math>n</math>-element subset of <math>T</math>.
+
Call an <math>\displaystyle n+1</math>-element subset of <math>S</math> separable if it has a subset in each class of the partition. We [[recursion|recursively]] build a set <math>Q</math> of disjoint separable subsets of <math>S</math>: begin with <math>Q</math> empty and at each step if there is a separable subset which is disjoint from all sets in <math>Q</math> add that set to <math>Q</math>. The process terminates when every separable subset intersects a set in <math>Q</math>. Let <math>T</math> be the set of elements in <math>S</math> which are not in any set in <math>Q</math>. We claim that one class contains every <math>n</math>-element subset of <math>T</math>.
  
−
Suppose that <math>a_1, a_2, \ldots a_k</math> are elements of <math>T</math>. Denote by <math>A_i</math> the set <math>\left\{a_i, a_{i+1}, \ldots a_{i+n-1}\right\}</math>. Note that for each <math>i</math>, <math>A_i \cup A_{i+1}</math> is not seperable, so that <math>A_i</math> and <math>A_{i+1}</math> are in the same class. But then <math>A_i</math> is in the same class for each <math>1 \leq i \leq k - n + 1</math>--in particular, <math>A_1</math> and <math>A_{k-n+1}</math> are in the same class. But for any two sets we may construct such a sequence with <math>A_1</math> equal to one and <math>A_{k-n+1}</math> equal to the other.   
+
Suppose that <math>\displaystyle a_1, a_2, \ldots a_k</math> are elements of <math>T</math>. Denote by <math>A_i</math> the set <math>\left\{a_i, a_{i+1}, \ldots a_{i+n-1}\right\}</math>. Note that for each <math>i</math>, <math>A_i \cup A_{i+1}</math> is not separable, so that <math>A_i</math> and <math>A_{i+1}</math> are in the same class. But then <math>A_i</math> is in the same class for each <math>1 \leq i \leq k - n + 1</math> &mdash; in particular, <math>A_1</math> and <math>A_{k-n+1}</math> are in the same class. But for any two sets we may construct such a sequence with <math>A_1</math> equal to one and <math>A_{k-n+1}</math> equal to the other.   
  
−
We are now ready to construct our <math>n</math> disjoint sets. Suppose that <math>|Q| = q</math>. Then <math>|T| = (n+1)(n-q) - 1 \geq n(n-q)</math>, so we may select <math>n - q</math> disjoint <math>n</math>-element subsets of <math>T</math>. Then for each of the <math>q</math> sets in <math>Q</math>, we may select a subset which is in the same class as all the subsets of <math>T</math>, for a total of <math>n</math> disjoint sets.
+
We are now ready to construct our <math>n</math> disjoint sets. Suppose that <math>\displaystyle |Q| = q</math>. Then <math>|T| = (n+1)(n-q) - 1 \geq n(n-q)</math>, so we may select <math>n - q</math> disjoint <math>n</math>-element subsets of <math>T</math>. Then for each of the <math>q</math> sets in <math>Q</math>, we may select a subset which is in the same class as all the subsets of <math>T</math>, for a total of <math>n</math> disjoint sets.
  
−
Idea from K81o7, write-up by 101101101.
+
== See also ==
 +
{{USAMO newbox|year=2007|num-b=2|num-a=4}}
  
−
 
+
[[Category:Olympiad Combinatorics Problems]]
−
{{USAMO newbox|year=2007|num-b=2|num-a=4}}
 

Revision as of 14:49, 26 April 2007

Problem

Let $S$ be a set containing $\displaystyle n^2+n-1$ elements, for some positive integer $n$. Suppose that the $n$-element subsets of $S$ are partitioned into two classes. Prove that there are at least $n$ pairwise disjoint sets in the same class.

Solution

Call an $\displaystyle n+1$-element subset of $S$ separable if it has a subset in each class of the partition. We recursively build a set $Q$ of disjoint separable subsets of $S$: begin with $Q$ empty and at each step if there is a separable subset which is disjoint from all sets in $Q$ add that set to $Q$. The process terminates when every separable subset intersects a set in $Q$. Let $T$ be the set of elements in $S$ which are not in any set in $Q$. We claim that one class contains every $n$-element subset of $T$.

Suppose that $\displaystyle a_1, a_2, \ldots a_k$ are elements of $T$. Denote by $A_i$ the set $\left\{a_i, a_{i+1}, \ldots a_{i+n-1}\right\}$. Note that for each $i$, $A_i \cup A_{i+1}$ is not separable, so that $A_i$ and $A_{i+1}$ are in the same class. But then $A_i$ is in the same class for each $1 \leq i \leq k - n + 1$ — in particular, $A_1$ and $A_{k-n+1}$ are in the same class. But for any two sets we may construct such a sequence with $A_1$ equal to one and $A_{k-n+1}$ equal to the other.

We are now ready to construct our $n$ disjoint sets. Suppose that $\displaystyle |Q| = q$. Then $|T| = (n+1)(n-q) - 1 \geq n(n-q)$, so we may select $n - q$ disjoint $n$-element subsets of $T$. Then for each of the $q$ sets in $Q$, we may select a subset which is in the same class as all the subsets of $T$, for a total of $n$ disjoint sets.

See also

2007 USAMO (Problems • Resources)
Preceded by
Problem 2 		Followed by
Problem 4
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2007_USAMO_Problems/Problem_3&oldid=14739"