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 "2009 USAMO Problems/Problem 2"

m (→‎Solution)
 
(One intermediate revision by one other user not shown)
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.  
Line 10: Line 28:
  
  
−
'''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:
+
'''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>M_{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:
  
  

Latest revision as of 03:44, 2 October 2015

Problem

Let $n$ be a positive integer. Determine the size of the largest subset of $\{ - n, - n + 1, \ldots , n - 1, n\}$ which does not contain three elements $a, b, c$ (not necessarily distinct) satisfying $a + b + c = 0$.

Solution 1

Let $S$ be a subset of $\{-n,-n+1,\dots,n-1,n\}$ of largest size satisfying $a+b+c\neq 0$ for all $a,b,c\in S$. First, observe that $0\notin S$. Next note that $|S|\geq \lceil n/2\rceil$, by observing that the set of all the odd numbers in $\{-n,-n+1,\dots,n-1,n\}$ works. To prove that $|S|\leq \lceil n/2\rceil$, it suffices to only consider even $n$, because the statement for $2k$ implies the statement for $2k-1$ as well. So from here forth, assume $n$ is even.

For any two sets $A$ and $B$, denote by $A+B$ the set $\{a+b\mid a\in A,b\in B\}$, and by $-A$ the set $\{-a\mid a\in A\}$. Also, let $A_+$ denote $A\cap\{1,2,\dots\}$ and $A_-$ denote $A\cap\{-1,-2,\dots\}$. First, we present a lemma:

Lemma 1: Let $A$ and $B$ be two sets of integers. Then $|A+B|\geq|A|+|B|-1$.

Proof: Write $A=\{a_1,\dots,a_n\}$ and $B=\{b_1,\dots,b_m\}$ where $a_1<\dots<a_n$ and $b_1<\dots<b_m$. Then $a_1+b_1,a_1+b_2,\dots,a_1+b_m,a_2+b_m,\dots,a_n+b_m$ is a strictly increasing sequence of $n+m-1$ integers in $A+B$.

Now, we consider two cases:

Case 1: One of $n,-n$ is not in $S$. Without loss of generality, suppose $-n\notin S$. Let $U=\{-n+1,-n+2,\dots,n-2,n-1,n\}$ (a set with $2n$ elements), so that $S\subseteq U$ by our assumption. Now, the condition that $a+b+c\neq 0$ for all $a,b,c\in S$ implies that $-S\cap(S_++S_-)=\emptyset$. Since any element of $S_++S_-$ has absolute value at most $n-1$, we have $S_++S_-\subseteq \{-n+1,-n+2,\dots,n-2,n-1\}\subseteq U$. It follows that $S_++S_-\subseteq U\setminus -S$, so $|S_++S_-|\leq 2n-|S|$. However, by Lemma 1, we also have $|S_++S_-|\geq |S_+|+|S_-|-1=|S|-1$. Therefore, we must have $|S|-1\leq 2n-|S|$, or $2|S|\leq 2n+1$, or $|S|\leq n$.

Case 2: Both $n$ and $-n$ are in $S$. Then $n/2$ and $-n/2$ are not in $S$, and at most one of each of the pairs $\{1,n-1\},\{2,n-2\},\ldots,\{\frac n2-1,\frac n2+1\}$ and their negatives are in $S$. This means $S$ contains at most $2+(n-2)=n$ elements.

Thus we have proved that $|S|\leq n=\lceil n/2\rceil$ for even $n$, and we are done.

Solution 2

Let $Z_n$ be the set of subsets satisfying the $a+b+c \neq 0$ condition for $n$, and let $s_n$ be the largest size of a set in $Z_n$. Let $n = 2k$ if $n$ is even, and $n = 2k-1$ if $n$ is odd. We note that $s_n \ge 2k$ due to the following constuction: \[\{-2k+1, -2k + 3, \ldots, 2k-3, 2k-1\}\] or all of the odd numbers in the set. Then the sum of any three will be odd and thus nonzero.


Lemma 1: $s_{n+1} \le s_{n} + 2$. If $M_{n+1} \in Z_{n+1}, |M_{n+1}| = s_{n+1}$, then we note that $M_{n+1} \setminus \{-2n+1, 2n-1\} \in Z_n$, so $|M_{n+1}| - 2 \le s_n$. $\square$


Lemma 2: $s_{2k} = s_{2k-1}$. Suppose, for sake of contradiction, that $M_{2k} \in Z_{n+1}$ and $M_{2k} > s_{2k-1}$. Remove $2k,-2k$ from $M_{2k}$, and partition the rest of the elements into two sets $P_{2k-1}, Q_{2k-1}$, where $P$ and $Q$ contain all of the positive and negative elements of $M_{2k}$, respectively. (obviously $0 \not \in M_{2k}$, because $0+0+0 = 0$). WLOG, suppose $|P_{2k-1}| \ge |Q_{2k-1}|$. Then $|P_{2k-1}| + |Q_{2k-1}| \ge s_{2k-1} - 1 \ge 2k - 1$. We now show the following two sub-results:


Sub-lemma (A): if $|P_{2k-1}| \ge k$, $-2k \not \in M_{2k}$ [and similar for $Q$]; and


Sub-lemma (B): we cannot have both $|P_{2k-1}| + |Q_{2k-1}| \ge 2k$ and $|Q_{2k-1}| < k$ simultaneously hold.


This is sufficient, because the only two elements that may be in $M_{2k}$ that are not in $P_{2k-1}, Q_{2k-1}$ are $2k$ and $-2k$; for $M_{2k} > s_{2k-1}$, we must either have $|P_{2k-1}| + |Q_{2k-1}| = s_{2k-1} - 1 \ge 2k-1$ and both $2k,-2k \in M_{2k}$ [but by pigeonhole $|P_{2k-1}| \ge k$, see sub-lemma (A)], or $|P_{2k-1}| + |Q_{2k-1}| = s_{2k-1} \ge 2k$, and $2k \in M_{2k}$, in which case by (A) we must have $|Q_{2k-1}| < k$, violating (B).


(A): Partition $\{1,2,\ldots,2k-1\}$ into the $k$ sets $\{k\}, \{1,2k-1\}, \{2, 2k-2\}, \cdots, \{k-1, k+1\}$. Because $(k+\delta) + (k-\delta) - 2k = 0$, then if any of those sets are within $P_{2k-1}$, $-2k \not \in M_{2k}$. But by Pigeonhole at most $k-1$ elements may be in $P_{2k-1}$, contradiction.


(B): We prove this statement with another induction. We see that the statement easily holds true for $k=1$ or $2$, so suppose it is true for $k-1$, but [for sake of contradiction] false for $k$. Let $P_{2k-3} = P_{2k-1} \setminus \{2k-2, 2k-1\}$, and similarly for $Q_{2k-3}$. Again WLOG $|P_{2k-3}| \ge |Q_{2k-3}|$. Then we have $|P_{2k-1}| + |Q_{2k-1}| \le |P_{2k-3}| + |Q_{2k-3}| + 4$.

  • If $|P_{2k-3}| + |Q_{2k-3}| \ge 2k-2$, then by inductive hypothesis, we must have $|P_{2k-3}| = |Q_{2k-3}| = k-1$. But (A) implies that we cannot add $2k-2$ or $-2k+2$. So to satisfy $|P_{2k-1}| = |Q_{2k-1}| \ge 2k$ we must have $2k-1, -2k+1$ added, but then $|P_{2k-1}| = |Q_{2k-1}| = k$ contradiction.
  • If $|P_{2k-3}| + |Q_{2k-3}| = 2k-3$, then at least three of $\{2k-2, 2k-1, -2k+2, -2k + 1\}$ added. But $|P_{2k-3}| \ge k-1$, and by (A) we have that $-2k+2$ cannot be added. If $|P_{2k-3}| \ge k$, then another grouping similar to (A) shows that $-2k+1$ canno be added, contradiction. So $|P_{2k-3}| = k-1$, $|Q_{2k-3}| = k-2$, and adding the three remaining elements gives $|P_{2k-1}| = |Q_{2k-1}| = k$ contradiction.
  • If $|P_{2k-3}| + |Q_{2k-3}| = 2k-4$, then all four of $\{2k-2, 2k-1, -2k+2, -2k + 1\}$ must be added, and furthermore $|P_{2k-3}| > |Q_{2k-3}|$. Then $|P_{2k-3}| \ge k-1$, and by previous paragraph we cannot add $-2k+2$. $\square$


So we have $\begin{cases} s_1 &= 2 \\ s_{2k} &= s_{2k-1} \\ s_{2k-1} &\le s_{2k-2} + 2 \\ \end{cases}$ and by induction, that $s_n \le \boxed{2\left\lceil \frac n2 \right \rceil} = 2k$, 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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2009_USAMO_Problems/Problem_2&oldid=72314"