Difference between revisions of "2016 USAMO Problems/Problem 1"
(→Solution 2) |
Stormstar-- (talk | contribs) m (Removed the second box) |
||
(One intermediate revision by one other user not shown) | |||
Line 9: | Line 9: | ||
First, we provide a inductive construction for <math>S = \left\{ 1, \dots, 8 \right\}</math>. Actually, for <math>n \ge 4</math> we will provide a construction for <math>S = \left\{ 1, \dots, n \right\}</math> which has <math>2^{n-1} + 1</math> elements in a line. (This is sufficient, since we then get <math>129</math> for <math>n = 8</math>.) The idea is to start with the following construction for <math>|S| = 4</math>: <cmath> \begin{array}{ccccccccc} 34 & 1 & 23 & 4 & 12 & 3 & 14 & 2 & 13 \end{array}. </cmath>Then inductively, we do the following procedure to move from <math>n</math> to <math>n+1</math>: take the chain for <math>n</math> elements, delete an element, and make two copies of the chain (which now has even length). Glue the two copies together, joined by <math>\varnothing</math> in between. Then place the element <math>n+1</math> in alternating positions starting with the first (in particular, this hits <math>n+1</math>). For example, the first iteration of this construction gives: <cmath> \begin{array}{ccccccccc} 345 & 1 & 235 & 4 & 125 & 3 & 145 & 2 & 5 \\ 34 & 15 & 23 & 45 & 12 & 35 & 14 & 25 & \end{array} </cmath> | First, we provide a inductive construction for <math>S = \left\{ 1, \dots, 8 \right\}</math>. Actually, for <math>n \ge 4</math> we will provide a construction for <math>S = \left\{ 1, \dots, n \right\}</math> which has <math>2^{n-1} + 1</math> elements in a line. (This is sufficient, since we then get <math>129</math> for <math>n = 8</math>.) The idea is to start with the following construction for <math>|S| = 4</math>: <cmath> \begin{array}{ccccccccc} 34 & 1 & 23 & 4 & 12 & 3 & 14 & 2 & 13 \end{array}. </cmath>Then inductively, we do the following procedure to move from <math>n</math> to <math>n+1</math>: take the chain for <math>n</math> elements, delete an element, and make two copies of the chain (which now has even length). Glue the two copies together, joined by <math>\varnothing</math> in between. Then place the element <math>n+1</math> in alternating positions starting with the first (in particular, this hits <math>n+1</math>). For example, the first iteration of this construction gives: <cmath> \begin{array}{ccccccccc} 345 & 1 & 235 & 4 & 125 & 3 & 145 & 2 & 5 \\ 34 & 15 & 23 & 45 & 12 & 35 & 14 & 25 & \end{array} </cmath> | ||
Now let's check <math>|S| \ge 8</math> is sufficient. Consider a chain on a set of size <math>|S| = 7</math>. (We need <math>|S| \ge 7</math> else <math>2^{|S|} < 100</math>.) Observe that there are sets of size <math>\ge 4</math> can only be neighbored by sets of size <math>\le 2</math>, of which there are <math>\binom 71 + \binom 72 = 28</math>. So there are <math>\le 30</math> sets of size <math>\ge 4</math>. Also, there are <math>\binom 73 = 35</math> sets of size <math>3</math>. So the total number of sets in a chain can be at most <math>30 + 28 + 35 = 93 < 100</math>. | Now let's check <math>|S| \ge 8</math> is sufficient. Consider a chain on a set of size <math>|S| = 7</math>. (We need <math>|S| \ge 7</math> else <math>2^{|S|} < 100</math>.) Observe that there are sets of size <math>\ge 4</math> can only be neighbored by sets of size <math>\le 2</math>, of which there are <math>\binom 71 + \binom 72 = 28</math>. So there are <math>\le 30</math> sets of size <math>\ge 4</math>. Also, there are <math>\binom 73 = 35</math> sets of size <math>3</math>. So the total number of sets in a chain can be at most <math>30 + 28 + 35 = 93 < 100</math>. | ||
− | |||
== Solution 2 == | == Solution 2 == | ||
Line 51: | Line 50: | ||
==See also== | ==See also== | ||
{{USAMO newbox|year=2016|beforetext=|before=First Problem|num-a=2}} | {{USAMO newbox|year=2016|beforetext=|before=First Problem|num-a=2}} | ||
− |
Latest revision as of 18:11, 11 June 2017
Contents
Problem
Let be a sequence of mutually distinct nonempty subsets of a set
. Any two sets
and
are disjoint and their union is not the whole set
, that is,
and
, for all
. Find the smallest possible number of elements in
.
Solution 1
The answer is that .
First, we provide a inductive construction for . Actually, for
we will provide a construction for
which has
elements in a line. (This is sufficient, since we then get
for
.) The idea is to start with the following construction for
:
Then inductively, we do the following procedure to move from
to
: take the chain for
elements, delete an element, and make two copies of the chain (which now has even length). Glue the two copies together, joined by
in between. Then place the element
in alternating positions starting with the first (in particular, this hits
). For example, the first iteration of this construction gives:
Now let's check
is sufficient. Consider a chain on a set of size
. (We need
else
.) Observe that there are sets of size
can only be neighbored by sets of size
, of which there are
. So there are
sets of size
. Also, there are
sets of size
. So the total number of sets in a chain can be at most
.
Solution 2
My proof that is basically the same as the one above. Here is another construction for
that I like because it works with remainders and it's pretty intuitive. The basic idea is to assign different subsets to different remainders when divided by particular numbers, and then to use the Chinese Remainder Theorem to show that all of the subsets are distinct. The motivation for this comes from the fact that we want
and
to always be disjoint, so remainders are a great way to systematically make that happen, since
and
do not have the same remainder modulo any positive integer greater than
Anyway, here is the construction:
Let For
we will choose which elements of the set
belong to
based on the remainder of
modulo
and we will choose which elements of the set
belong to
based on the remainder of
modulo
We do this as follows:
Finally, we specially define
and
It is relatively easy to see that this configuration satisfies all of the desired conditions. We see that so
and
are disjoint, as are
and
The remainder configuration above takes care of the rest, so any two consecutive sets are disjoint. Then, by the Chinese Remainder Theorem, no two integers from
to
have the same combination of residues modulo
and modulo
so all of the sets
are distinct for
It is also easy to verify that none of these match
or
since they all have at most two elements of
and at most two elements of
whereas
and
do not satisfy this; hence all of the sets are distinct. Finally, notice that, for any pair of consecutive sets, at least one of them has at most
elements, while the other has at most
Thus, their union always has at most
elements, so
for all
All of the conditions are satisfied, so this configuration works. We thus conclude that
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.
See also
2016 USAMO (Problems • Resources) | ||
First Problem | Followed by Problem 2 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |