2009 USAMO Problems/Problem 2
Let be a positive integer. Determine the size of the largest subset of which does not contain three elements (not necessarily distinct) satisfying .
Let be a subset of of largest size satisfying for all . First, observe that . Next note that , by observing that the set of all the odd numbers in works. To prove that , it suffices to only consider even , because the statement for implies the statement for as well. So from here forth, assume is even.
For any two sets and , denote by the set , and by the set . Also, let denote and denote . First, we present a lemma:
Lemma 1: Let and be two sets of integers. Then .
Proof: Write and where and . Then is a strictly increasing sequence of integers in .
Now, we consider two cases:
Case 1: One of is not in . Without loss of generality, suppose . Let (a set with elements), so that by our assumption. Now, the condition that for all implies that . Since any element of has absolute value at most , we have . It follows that , so . However, by Lemma 1, we also have . Therefore, we must have , or , or .
Case 2: Both and are in . Then and are not in , and at most one of each of the pairs and their negatives are in . This means contains at most elements.
Thus we have proved that for even , and we are done.
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.
|2009 USAMO (Problems • Resources)|
|1 • 2 • 3 • 4 • 5 • 6|
|All USAMO Problems and Solutions|