Difference between revisions of "2009 USAMO Problems/Problem 2"
JoetheFixer (talk | contribs) 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> | + | '''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
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.