Difference between revisions of "2009 USAMO Problems/Problem 2"
JoetheFixer (talk | contribs) m (→Solution) |
|||
Line 2: | Line 2: | ||
Let <math>n</math> be a positive integer. Determine the size of the largest subset of <math>\{ - n, - n + 1, \ldots , n - 1, n\}</math> which does not contain three elements <math>a, b, c</math> (not necessarily distinct) satisfying <math>a + b + c = 0</math>. | Let <math>n</math> be a positive integer. Determine the size of the largest subset of <math>\{ - n, - n + 1, \ldots , n - 1, n\}</math> which does not contain three elements <math>a, b, c</math> (not necessarily distinct) satisfying <math>a + b + c = 0</math>. | ||
− | == Solution == | + | == Solution 1 == |
+ | |||
+ | Let <math>S</math> be a subset of <math>\{-n,-n+1,\dots,n-1,n\}</math> of largest size satisfying <math>a+b+c\neq 0</math> for all <math>a,b,c\in S</math>. First, observe that <math>0\notin S</math>. Next note that <math>|S|\geq \lceil n/2\rceil</math>, by observing that the set of all the odd numbers in <math>\{-n,-n+1,\dots,n-1,n\}</math> works. To prove that <math>|S|\leq \lceil n/2\rceil</math>, it suffices to only consider even <math>n</math>, because the statement for <math>2k</math> implies the statement for <math>2k-1</math> as well. So from here forth, assume <math>n</math> is even. | ||
+ | |||
+ | For any two sets <math>A</math> and <math>B</math>, denote by <math>A+B</math> the set <math>\{a+b\mid a\in A,b\in B\}</math>, and by <math>-A</math> the set <math>\{-a\mid a\in A\}</math>. Also, let <math>A_+</math> denote <math>A\cap\{1,2,\dots\}</math> and <math>A_-</math> denote <math>A\cap\{-1,-2,\dots\}</math>. First, we present a lemma: | ||
+ | |||
+ | '''Lemma 1''': Let <math>A</math> and <math>B</math> be two sets of integers. Then <math>|A+B|\geq|A|+|B|-1</math>. | ||
+ | |||
+ | ''Proof'': Write <math>A=\{a_1,\dots,a_n\}</math> and <math>B=\{b_1,\dots,b_m\}</math> where <math>a_1<\dots<a_n</math> and <math>b_1<\dots<b_m</math>. Then <math>a_1+b_1,a_1+b_2,\dots,a_1+b_m,a_2+b_m,\dots,a_n+b_m</math> is a strictly increasing sequence of <math>n+m-1</math> integers in <math>A+B</math>. | ||
+ | |||
+ | Now, we consider two cases: | ||
+ | |||
+ | '''Case 1''': One of <math>n,-n</math> is not in <math>S</math>. Without loss of generality, suppose <math>-n\notin S</math>. Let <math>U=\{-n+1,-n+2,\dots,n-2,n-1,n\}</math> (a set with <math>2n</math> elements), so that <math>S\subseteq U</math> by our assumption. Now, the condition that <math>a+b+c\neq 0</math> for all <math>a,b,c\in S</math> implies that <math>-S\cap(S_++S_-)=\emptyset</math>. Since any element of <math>S_++S_-</math> has absolute value at most <math>n-1</math>, we have <math>S_++S_-\subseteq \{-n+1,-n+2,\dots,n-2,n-1\}\subseteq U</math>. It follows that <math>S_++S_-\subseteq U\setminus -S</math>, so <math>|S_++S_-|\leq 2n-|S|</math>. However, by Lemma 1, we also have <math>|S_++S_-|\geq |S_+|+|S_-|-1=|S|-1</math>. Therefore, we must have <math>|S|-1\leq 2n-|S|</math>, or <math>2|S|\leq 2n+1</math>, or <math>|S|\leq n</math>. | ||
+ | |||
+ | '''Case 2''': Both <math>n</math> and <math>-n</math> are in <math>S</math>. Then <math>n/2</math> and <math>-n/2</math> are not in <math>S</math>, and at most one of each of the pairs <math>\{1,n-1\},\{2,n-2\},\ldots,\{\frac n2-1,\frac n2+1\}</math> and their negatives are in <math>S</math>. This means <math>S</math> contains at most <math>2+(n-2)=n</math> elements. | ||
+ | |||
+ | Thus we have proved that <math>|S|\leq n=\lceil n/2\rceil</math> for even <math>n</math>, and we are done. | ||
+ | |||
+ | == Solution 2 == | ||
Let <math>Z_n</math> be the set of subsets satisfying the <math>a+b+c \neq 0</math> condition for <math>n</math>, and let <math>s_n</math> be the largest size of a set in <math>Z_n</math>. Let <math>n = 2k</math> if <math>n</math> is even, and <math>n = 2k-1</math> if <math>n</math> is odd. We note that <math>s_n \ge 2k</math> due to the following constuction: <cmath>\{-2k+1, -2k + 3, \ldots, 2k-3, 2k-1\}</cmath> or all of the odd numbers in the set. Then the sum of any three will be odd and thus nonzero. | Let <math>Z_n</math> be the set of subsets satisfying the <math>a+b+c \neq 0</math> condition for <math>n</math>, and let <math>s_n</math> be the largest size of a set in <math>Z_n</math>. Let <math>n = 2k</math> if <math>n</math> is even, and <math>n = 2k-1</math> if <math>n</math> is odd. We note that <math>s_n \ge 2k</math> due to the following constuction: <cmath>\{-2k+1, -2k + 3, \ldots, 2k-3, 2k-1\}</cmath> or all of the odd numbers in the set. Then the sum of any three will be odd and thus nonzero. |
Latest revision as of 02:44, 2 October 2015
Contents
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 1
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.
Solution 2
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.