Difference between revisions of "2009 USAMO Problems/Problem 2"
JoetheFixer (talk | contribs) m (→Solution) |
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>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: |
Revision as of 12:07, 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.