Difference between revisions of "2009 USAMO Problems/Problem 2"
JoetheFixer (talk | contribs) m (→Solution) |
|||
Line 10: | Line 10: | ||
− | '''Lemma 2''': <math>s_{2k} = s_{2k-1}</math>. Suppose, for sake of contradiction, that <math>M_{2k} \in Z_{n+1}</math> and <math> | + | '''Lemma 2''': <math>s_{2k} = s_{2k-1}</math>. Suppose, for sake of contradiction, that <math>M_{2k} \in Z_{n+1}</math> and <math>s_{2k} > s_{2k-1}</math>. Remove <math>2k,-2k</math> from <math>M_{2k}</math>, and partition the rest of the elements into two sets <math>P_{2k-1}, Q_{2k-1}</math>, where <math>P</math> and <math>Q</math> contain all of the positive and negative elements of <math>M_{2k}</math>, respectively. (obviously <math>0 \not \in M_{2k}</math>, because <math>0+0+0 = 0</math>). WLOG, suppose <math>|P_{2k-1}| \ge |Q_{2k-1}|</math>. Then <math>|P_{2k-1}| + |Q_{2k-1}| \ge s_{2k-1} - 1 \ge 2k - 1</math>. We now show the following two sub-results: |
Revision as of 11:05, 23 December 2014
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 |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.