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 1)
(→‎Solution 1)
Line 16: Line 16:
 
Look at any 2 n-element subsets <math>a_1</math> and <math>a_p</math>. Then we can create a path <math>a_1,a_2,...,a_p</math> s.t. any 2 consecutive terms belong to the same n+1-element subset.(i.e. we change 1 element each time.) Thus, <math>a_1</math> and <math>a_p</math> are in the same class and we see that all subsets are in one class. Obviously we can find <math>k</math> disjoint subsets of size n.
 
Look at any 2 n-element subsets <math>a_1</math> and <math>a_p</math>. Then we can create a path <math>a_1,a_2,...,a_p</math> s.t. any 2 consecutive terms belong to the same n+1-element subset.(i.e. we change 1 element each time.) Thus, <math>a_1</math> and <math>a_p</math> are in the same class and we see that all subsets are in one class. Obviously we can find <math>k</math> disjoint subsets of size n.
  
−
(Correct me if I'm wrong) Note: Because k<math>(n+1)</math>-1>k<math>(n+1)</math>, we can group the first n+1 elements, then the next <math>n+1</math> elements, and we have <math>k</math> of these groupings. Then each class is going to have one <math>n</math>-element group from each of these <math>k</math> groupings. Because their elements don't repeat, the sets are disjoint) 
+
(Correct me if I'm wrong) Note: Because <math>k</math><math>(n+1)</math>-1><math>k</math><math>(n+1)</math>, we can group the first n+1 elements, then the next <math>n+1</math> elements, and we have <math>k</math> of these groupings. Then, we assign each of the 2 classes to have one <math>n</math>-element group from each of these <math>k</math> groupings, so that their elements don't repeat. This means that they're disjoint!
  
−
The question is asking for the case when <math>k=n</math> which we have proved.
+
The question is asking for the case when we substitute <math>k=n</math> which we have proved.
 +
 
 +
~Brackie1331
  
 
=== Solution 2 ===
 
=== Solution 2 ===

Revision as of 23:21, 27 September 2024

Problem

(András Gyárfás) Let $S$ be a set containing $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

Solution 1

Claim: If we have instead $k(n+1)-1$ elements, then we must have k disjoint subsets in a class. We proceed by Induction

Base Case: $k=1$ is trivial.

Case 1: If there exists an $n+1$ element subset $X$ s.t. $X$ has 2 n-element subsets in different classes. Consider the $(k-1)(n+1)-1$ elements that are not in $X$, from the Induction hypothesis, we have $k-1$ disjoint subsets in one of the classes. Those $k-1$ subsets paired with a subset of $X$ in the same class forms $k$ disjoint subsets of size n.

Case 2: All $n+1$ element subsets have all of their n-element subsets in one class. Look at any 2 n-element subsets $a_1$ and $a_p$. Then we can create a path $a_1,a_2,...,a_p$ s.t. any 2 consecutive terms belong to the same n+1-element subset.(i.e. we change 1 element each time.) Thus, $a_1$ and $a_p$ are in the same class and we see that all subsets are in one class. Obviously we can find $k$ disjoint subsets of size n.

(Correct me if I'm wrong) Note: Because $k$$(n+1)$-1>$k$$(n+1)$, we can group the first n+1 elements, then the next $n+1$ elements, and we have $k$ of these groupings. Then, we assign each of the 2 classes to have one $n$-element group from each of these $k$ groupings, so that their elements don't repeat. This means that they're disjoint!

The question is asking for the case when we substitute $k=n$ which we have proved.

~Brackie1331

Solution 2

Call an $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 $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 $|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.

Solution 3

In order to apply induction, we generalize the result to be proved so that it reads as follows:

Proposition. If the $n$-element subsets of a set $S$ with $(n + 1)m - 1$ elements are partitioned into two classes, then there are at least $m$ pairwise disjoint sets in the same class.

Proof. Fix $n$ and proceed by induction on $m$. The case of $m = 1$ is trivial. Assume $m > 1$ and that the proposition is true for $m - 1$. Let $\mathcal{P}$ be the partition of the $n$-element subsets into two classes. If all the $n$-element subsets belong to the same class, the result is obvious. Otherwise select two $n$-element subsets $A$ and $B$ from different classes so that their intersection has maximal size. It is easy to see that $|A\cap B| = n - 1$. (If $|A\cap B| = k < n - 1$, then build $C$ from $B$ by replacing some element not in $A\cap B$ with an element of $A$ not already in $B$. Then $|A\cap C| = k + 1$ and $|B\cap C| = n - 1$ and either $A$ and $C$ or $B$ and $C$ are in different classes.) Removing $A\cup B$ from $S$, there are $(n + 1)(m - 1) - 1$ elements left. On this set the partition induced by $\mathcal{P}$ has, by the inductive hypothesis, $m - 1$ pairwise disjoint sets in the same class. Adding either $A$ or $B$ as appropriate gives $m$ pairwise disjoint sets in the same class. $\blacksquare$

Remark: The value $n^2 + n - 1$ is sharp. A set $S$ with $n^2 + n - 2$ elements can be split into a set $A$ with $n^2 - 1$ elements and a set $B$ of $n - 1$ elements. Let one class consist of all $n$-element subsets of $A$ and the other consist of all $n$-element subsets that intersect $B$. Then neither class contains $n$ pairwise disjoint sets.


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

See also

  • <url>viewtopic.php?t=145845 Discussion on AoPS/MathLinks</url>
2007 USAMO (Problems • Resources)
Preceded by
Problem 2 		Followed by
Problem 4
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=2007_USAMO_Problems/Problem_3&oldid=228370"