Difference between revisions of "2016 USAMO Problems/Problem 1"
(Created page with "== Problem == Let <math>X_1, X_2, \ldots, X_{100}</math> be a sequence of mutually distinct nonempty subsets of a set <math>S</math>. Any two sets <math>X_i</math> and <math>...") |
(→Solution) |
||
Line 3: | Line 3: | ||
Let <math>X_1, X_2, \ldots, X_{100}</math> be a sequence of mutually distinct nonempty subsets of a set <math>S</math>. Any two sets <math>X_i</math> and <math>X_{i+1}</math> are disjoint and their union is not the whole set <math>S</math>, that is, <math>X_i\cap X_{i+1}=\emptyset</math> and <math>X_i\cup X_{i+1}\neq S</math>, for all <math>i\in\{1, \ldots, 99\}</math>. Find the smallest possible number of elements in <math>S</math>. | Let <math>X_1, X_2, \ldots, X_{100}</math> be a sequence of mutually distinct nonempty subsets of a set <math>S</math>. Any two sets <math>X_i</math> and <math>X_{i+1}</math> are disjoint and their union is not the whole set <math>S</math>, that is, <math>X_i\cap X_{i+1}=\emptyset</math> and <math>X_i\cup X_{i+1}\neq S</math>, for all <math>i\in\{1, \ldots, 99\}</math>. Find the smallest possible number of elements in <math>S</math>. | ||
− | == Solution == | + | == Solution 1== |
The answer is that <math>|S| \ge 8</math>. | The answer is that <math>|S| \ge 8</math>. | ||
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 == | ||
+ | My proof that <math>|S|\ge 8</math> is basically the same as the one above. Here is another construction for <math>|S| = 8</math> 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 <math>X_i</math> and <math>X_{i+1}</math> to always be disjoint, so remainders are a great way to systematically make that happen, since <math>i</math> and <math>i+1</math> do not have the same remainder modulo any positive integer greater than <math>1.</math> Anyway, here is the construction: | ||
+ | |||
+ | Let <math>S = {1, 2, ..., 8}.</math> For <math>i = 1, 2, ..., 98,</math> we will choose which elements of the set <math>\left\{ {1, 2, 3, 4} \right\}</math> belong to <math>X_i</math> based on the remainder of <math>i</math> modulo <math>9,</math> and we will choose which elements of the set <math>\left\{ {5, 6, 7, 8} \right\}</math> belong to <math>X_i</math> based on the remainder of <math>i</math> modulo <math>11.</math> | ||
+ | |||
+ | |||
{{MAA Notice}} | {{MAA Notice}} |
Revision as of 22:18, 27 April 2016
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
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 |
2016 USAJMO (Problems • Resources) | ||
Preceded by Problem 2 |
Followed by Problem 4 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAJMO Problems and Solutions |