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 "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>...")
 
m (Removed the second box)
 
(7 intermediate revisions by 2 users not shown)
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 = \left\{ {1, 2, ..., 8} \right\}.</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> We do this as follows:
 +
<cmath>X_i\cap\left\{ {1, 2, 3, 4} \right\} =
 +
\begin{array}{ll}
 +
      \emptyset & i\equiv 0 \text{ (mod } 9\text{)} \\
 +
      \left\{ {1, 2} \right\} & i\equiv 1 \text{ (mod } 9\text{)} \\
 +
      \left\{ {3} \right\} & i\equiv 2 \text{ (mod } 9\text{)} \\
 +
      \left\{ {1, 4} \right\} & i\equiv 3 \text{ (mod } 9\text{)} \\
 +
      \left\{ {2} \right\} & i\equiv 4 \text{ (mod } 9\text{)} \\
 +
      \left\{ {3, 4} \right\} & i\equiv 5 \text{ (mod } 9\text{)} \\
 +
      \left\{ {1} \right\} & i\equiv 6 \text{ (mod } 9\text{)} \\
 +
      \left\{ {2, 3} \right\} & i\equiv 7 \text{ (mod } 9\text{)} \\
 +
      \left\{ {4} \right\} & i\equiv 8 \text{ (mod } 9\text{)} \\
 +
\end{array}</cmath>
 +
<cmath>X_i\cap\left\{ {5, 6, 7, 8} \right\} =
 +
\begin{array}{ll}
 +
      \emptyset & i\equiv 0 \text{ (mod } 11\text{)} \\
 +
      \left\{ {5, 6} \right\} & i\equiv 1 \text{ (mod } 11\text{)} \\
 +
      \left\{ {7, 8} \right\} & i\equiv 2 \text{ (mod } 11\text{)} \\
 +
      \left\{ {5} \right\} & i\equiv 3 \text{ (mod } 11\text{)} \\
 +
      \left\{ {6, 8} \right\} & i\equiv 4 \text{ (mod } 11\text{)} \\
 +
      \left\{ {5, 7} \right\} & i\equiv 5 \text{ (mod } 11\text{)} \\
 +
      \left\{ {6} \right\} & i\equiv 6 \text{ (mod } 11\text{)} \\
 +
      \left\{ {5, 8} \right\} & i\equiv 7 \text{ (mod } 11\text{)} \\
 +
      \left\{ {6, 7} \right\} & i\equiv 8 \text{ (mod } 11\text{)} \\
 +
      \left\{ {8} \right\} & i\equiv 9 \text{ (mod } 11\text{)} \\
 +
      \left\{ {7} \right\} & i\equiv 10 \text{ (mod } 11\text{)} \\
 +
\end{array}</cmath>
 +
Finally, we specially define <math>X_{99} = \left\{ {1, 2, 3} \right\}</math> and <math>X_{100} = \left\{ {5, 6, 7} \right\}.</math>
 +
 +
It is relatively easy to see that this configuration satisfies all of the desired conditions. We see that <math>X_{98} = \left\{ {4, 7} \right\},</math> so <math>X_{98}</math> and <math>X_{99}</math> are disjoint, as are <math>X_{99}</math> and <math>X_{100}.</math> 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 <math>1</math> to <math>98</math> have the same combination of residues modulo <math>9</math> and modulo <math>11,</math> so all of the sets <math>X_i</math> are distinct for <math>i = 1, 2, ..., 98.</math> It is also easy to verify that none of these match <math>X_{99}</math> or <math>X_{100},</math> since they all have at most two elements of <math>\left\{ {1, 2, 3, 4} \right\}</math> and at most two elements of <math>\left\{ {5, 6, 7, 8} \right\},</math> whereas <math>X_{99}</math> and <math>X_{100}</math> 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 <math>3</math> elements, while the other has at most <math>4.</math> Thus, their union always has at most <math>7</math> elements, so <math>X_i\cup X_{i+1}\neq S</math> for all <math>i = 1, 2, ..., 99.</math>
 +
 +
All of the conditions are satisfied, so this configuration works. We thus conclude that <math>\text{min}\left(\left|S\right|\right) = 8.</math>
  
 
{{MAA Notice}}
 
{{MAA Notice}}
Line 14: 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}}
−
{{USAJMO newbox|year=2016|num-b=2|num-a=4}}
 

Latest revision as of 17:11, 11 June 2017

Problem

Let $X_1, X_2, \ldots, X_{100}$ be a sequence of mutually distinct nonempty subsets of a set $S$. Any two sets $X_i$ and $X_{i+1}$ are disjoint and their union is not the whole set $S$, that is, $X_i\cap X_{i+1}=\emptyset$ and $X_i\cup X_{i+1}\neq S$, for all $i\in\{1, \ldots, 99\}$. Find the smallest possible number of elements in $S$.

Solution 1

The answer is that $|S| \ge 8$.

First, we provide a inductive construction for $S = \left\{ 1, \dots, 8 \right\}$. Actually, for $n \ge 4$ we will provide a construction for $S = \left\{ 1, \dots, n \right\}$ which has $2^{n-1} + 1$ elements in a line. (This is sufficient, since we then get $129$ for $n = 8$.) The idea is to start with the following construction for $|S| = 4$: \[\begin{array}{ccccccccc} 34 & 1 & 23 & 4 & 12 & 3 & 14 & 2 & 13 \end{array}.\]Then inductively, we do the following procedure to move from $n$ to $n+1$: take the chain for $n$ elements, delete an element, and make two copies of the chain (which now has even length). Glue the two copies together, joined by $\varnothing$ in between. Then place the element $n+1$ in alternating positions starting with the first (in particular, this hits $n+1$). For example, the first iteration of this construction gives: \[\begin{array}{ccccccccc} 345 & 1 & 235 & 4 & 125 & 3 & 145 & 2 & 5 \\ 34 & 15 & 23 & 45 & 12 & 35 & 14 & 25 & \end{array}\] Now let's check $|S| \ge 8$ is sufficient. Consider a chain on a set of size $|S| = 7$. (We need $|S| \ge 7$ else $2^{|S|} < 100$.) Observe that there are sets of size $\ge 4$ can only be neighbored by sets of size $\le 2$, of which there are $\binom 71 + \binom 72 = 28$. So there are $\le 30$ sets of size $\ge 4$. Also, there are $\binom 73 = 35$ sets of size $3$. So the total number of sets in a chain can be at most $30 + 28 + 35 = 93 < 100$.

Solution 2

My proof that $|S|\ge 8$ is basically the same as the one above. Here is another construction for $|S| = 8$ 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 $X_i$ and $X_{i+1}$ to always be disjoint, so remainders are a great way to systematically make that happen, since $i$ and $i+1$ do not have the same remainder modulo any positive integer greater than $1.$ Anyway, here is the construction:

Let $S = \left\{ {1, 2, ..., 8} \right\}.$ For $i = 1, 2, ..., 98,$ we will choose which elements of the set $\left\{ {1, 2, 3, 4} \right\}$ belong to $X_i$ based on the remainder of $i$ modulo $9,$ and we will choose which elements of the set $\left\{ {5, 6, 7, 8} \right\}$ belong to $X_i$ based on the remainder of $i$ modulo $11.$ We do this as follows: \[X_i\cap\left\{ {1, 2, 3, 4} \right\} = \begin{array}{ll} \emptyset & i\equiv 0 \text{ (mod } 9\text{)} \\ \left\{ {1, 2} \right\} & i\equiv 1 \text{ (mod } 9\text{)} \\ \left\{ {3} \right\} & i\equiv 2 \text{ (mod } 9\text{)} \\ \left\{ {1, 4} \right\} & i\equiv 3 \text{ (mod } 9\text{)} \\ \left\{ {2} \right\} & i\equiv 4 \text{ (mod } 9\text{)} \\ \left\{ {3, 4} \right\} & i\equiv 5 \text{ (mod } 9\text{)} \\ \left\{ {1} \right\} & i\equiv 6 \text{ (mod } 9\text{)} \\ \left\{ {2, 3} \right\} & i\equiv 7 \text{ (mod } 9\text{)} \\ \left\{ {4} \right\} & i\equiv 8 \text{ (mod } 9\text{)} \\ \end{array}\] \[X_i\cap\left\{ {5, 6, 7, 8} \right\} = \begin{array}{ll} \emptyset & i\equiv 0 \text{ (mod } 11\text{)} \\ \left\{ {5, 6} \right\} & i\equiv 1 \text{ (mod } 11\text{)} \\ \left\{ {7, 8} \right\} & i\equiv 2 \text{ (mod } 11\text{)} \\ \left\{ {5} \right\} & i\equiv 3 \text{ (mod } 11\text{)} \\ \left\{ {6, 8} \right\} & i\equiv 4 \text{ (mod } 11\text{)} \\ \left\{ {5, 7} \right\} & i\equiv 5 \text{ (mod } 11\text{)} \\ \left\{ {6} \right\} & i\equiv 6 \text{ (mod } 11\text{)} \\ \left\{ {5, 8} \right\} & i\equiv 7 \text{ (mod } 11\text{)} \\ \left\{ {6, 7} \right\} & i\equiv 8 \text{ (mod } 11\text{)} \\ \left\{ {8} \right\} & i\equiv 9 \text{ (mod } 11\text{)} \\ \left\{ {7} \right\} & i\equiv 10 \text{ (mod } 11\text{)} \\ \end{array}\] Finally, we specially define $X_{99} = \left\{ {1, 2, 3} \right\}$ and $X_{100} = \left\{ {5, 6, 7} \right\}.$

It is relatively easy to see that this configuration satisfies all of the desired conditions. We see that $X_{98} = \left\{ {4, 7} \right\},$ so $X_{98}$ and $X_{99}$ are disjoint, as are $X_{99}$ and $X_{100}.$ 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 $1$ to $98$ have the same combination of residues modulo $9$ and modulo $11,$ so all of the sets $X_i$ are distinct for $i = 1, 2, ..., 98.$ It is also easy to verify that none of these match $X_{99}$ or $X_{100},$ since they all have at most two elements of $\left\{ {1, 2, 3, 4} \right\}$ and at most two elements of $\left\{ {5, 6, 7, 8} \right\},$ whereas $X_{99}$ and $X_{100}$ 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 $3$ elements, while the other has at most $4.$ Thus, their union always has at most $7$ elements, so $X_i\cup X_{i+1}\neq S$ for all $i = 1, 2, ..., 99.$

All of the conditions are satisfied, so this configuration works. We thus conclude that $\text{min}\left(\left|S\right|\right) = 8.$

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

See also

2016 USAMO (Problems • Resources)
First Problem Followed by
Problem 2
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2016_USAMO_Problems/Problem_1&oldid=86015"