2009 USAMO Problems/Problem 2
Problem
Let be a positive integer. Determine the size of the largest subset of which does not contain three elements (not necessarily distinct) satisfying .
Solution
Let be the set of subsets satisfying the condition for , and let be the largest size of a set in . Let if is even, and if is odd. We note that due to the following constuction: or all of the odd numbers in the set. Then the sum of any three will be odd and thus nonzero.
Lemma 1: . If , then we note that , so .
Lemma 2: . Suppose, for sake of contradiction, that and . Remove from , and partition the rest of the elements into two sets , where and contain all of the positive and negative elements of , respectively. (obviously , because ). WLOG, suppose . Then . We now show the following two sub-results:
- Sub-lemma (A): if , [and similar for ]; and
- Sub-lemma (B): we cannot have both and simultaneously hold.
This is sufficient, because the only two elements that may be in that are not in are and ; for , we must either have and both [but by pigeonhole , see sub-lemma (A)], or , and , in which case by (A) we must have , violating (B).
(A): Partition into the sets . Because , then if any of those sets are within , . But by Pigeonhole at most elements may be in , contradiction.
(B): We prove this statement with another induction. We see that the statement easily holds true for or , so suppose it is true for , but [for sake of contradiction] false for . Let , and similarly for . Again WLOG . Then we have .
- If , then by inductive hypothesis, we must have . But (A) implies that we cannot add or . So to satisfy we must have added, but then contradiction.
- If , then at least three of added. But , and by (A) we have that cannot be added. If , then another grouping similar to (A) shows that canno be added, contradiction. So , , and adding the three remaining elements gives contradiction.
- If , then all four of must be added, and furthermore . Then , and by previous paragraph we cannot add .
So we have and by induction, that , which we showed is achievable above.
See also
2009 USAMO (Problems • Resources) | ||
Preceded by Problem 1 |
Followed by Problem 3 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |