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 "2001 USAMO Problems/Problem 1"

(solution)
 
m (→‎Solution 2)
 
(19 intermediate revisions by 9 users not shown)
Line 2: Line 2:
 
Each of eight boxes contains six balls. Each ball has been colored with one of <math>n</math> colors, such that no two balls in the same box are the same color, and no two colors occur together in more than one box. Determine, with justification, the smallest integer <math>n</math> for which this is possible.  
 
Each of eight boxes contains six balls. Each ball has been colored with one of <math>n</math> colors, such that no two balls in the same box are the same color, and no two colors occur together in more than one box. Determine, with justification, the smallest integer <math>n</math> for which this is possible.  
  
−
== Solution ==
+
== Solution 1 ==
 
We claim that <math>n=23</math> is the minimum. Consider the following construction (replacing colors with numbers) which fulfills this:
 
We claim that <math>n=23</math> is the minimum. Consider the following construction (replacing colors with numbers) which fulfills this:
 +
<cmath>\left[ \begin{array}{cccccccc}
 +
1 & 1 & 1 & 2 & 3 & 4 & 5 & 6 \\
 +
2 & 7 & 12 & 7 & 8 & 9 & 10 & 11 \\
 +
3 & 8 & 13 & 12 & 13 & 14 & 15 & 16 \\
 +
4 & 9 & 14 & 17 & 17 & 17 & 18 & 19 \\
 +
5 & 10 & 15 & 18 & 20 & 22 & 20 & 21 \\
 +
6 & 11 & 16 & 19 & 21 & 23 & 22 & 23 \end{array} \right]</cmath>
 +
Suppose a configuration exists with <math>n \le 22</math>.
  
−
<cmath>
+
Suppose a ball appears <math>5</math> or more times. Then the remaining balls of the <math>5</math> boxes must be distinct, so that there are at least <math>n \ge 5 \cdot 5 + 1 = 26</math> balls, contradiction. If a ball appears <math>4</math> or more times, the remaining balls of the <math>4</math> boxes must be distinct, leading to <math>5 \cdot 4 + 1 = 21</math> balls. The fifth box can contain at most four balls from the previous boxes, and then the remaining two balls must be distinct, leading to <math>n \ge 2 + 21 = 23</math>, contradiction.
−
\begin{tabular}{|r|r|r|r|r|r|}
+
 
−
\hline
+
However, by the [[Pigeonhole Principle]], at least one ball must appear <math>3</math> times. [[Without loss of generality]] suppose that <math>1</math> appears three times, and let the boxes that contain these have balls with colors <math>\{1,2,3,4,5,6\},\{1,7,8,9,10,11\},\{1,12,13,14,15,16\}</math>. Each of the remaining five boxes can have at most <math>3</math> balls from each of these boxes. Thus, each of the remaining five boxes must have <math>3</math> additional balls <math>> 16</math>. Thus, it is necessary that we use <math>\le 22 - 16 = 6</math> balls to fill a <math>3 \times 5</math> grid by the same rules.
−
1 & 2 & 3 & 4 & 5 & 6 \\
+
 
−
\hline
+
Again, no balls may appear <math>\ge 4</math> times, but by Pigeonhole, one ball must appear <math>3</math> times. [[Without loss of generality]], let this ball have color <math>17</math>; then the three boxes containing <math>17</math> must have at least <math>2 \cdot 3 + 1 = 7</math> balls, contradiction.
−
1 & 7 & 8 & 9 & 10 & 11 \\
 
−
\hline
 
−
1 & 12 & 13 & 14 & 15 & 16 \\
 
−
\hline
 
−
2 & 7 & 12 & 17 & 18 & 19 \\
 
−
\hline
 
−
3 & 8 & 13 & 17 & 20 & 21 \\
 
−
\hline
 
−
4 & 9 & 14 & 17 & 22 & 23 \\
 
−
\hline
 
−
5 & 10 & 15 & 18 & 20 & 22 \\
 
−
\hline
 
−
6 & 11 & 16 & 19 & 21 & 23 \\
 
−
\hline
 
−
\end{tabular}
 
−
</cmath>
 
  
−
Suppose a configuration exists with <math>n \le 22</math>.  
+
Therefore, <math>n = 23</math> is the minimum.
  
−
Suppose an element appears <math>5</math> or more times. Then the remaining elements of the <math>5</math> boxes must be distinct, so that there are at least <math>n \ge 5 \cdot 5 + 1 = 26</math> elements, contradiction. If an element appears <math>4</math> or more times, the remaining elements of the <math>4</math> boxes must be distinct, leading to <math>5 \cdot 4 + 1 = 21</math> elements. The fifth box can contain at most four elements from the previous boxes, and then the remaining two elements must be distinct, leading to <math>n \ge 2 + 21 = 23</math>, contradiction.
+
== Solution 2 ==
  
−
However, by the [[Pigeonhole Principle]], at least one element must appear <math>3</math> times. [[Without loss of generality]] suppose that <math>1</math> appears three times, and let the boxes that contain these have the elements <math>\{1,2,3,4,5,6\},\{1,7,8,9,10,11\},\{1,12,13,14,15,16\}</math>. Each of the remaining five boxes can have at most contain <math>3</math> elements from each of these boxes. Thus, each of the remaining five boxes must have <math>3</math> additional elements <math>> 16</math>. Thus, it is necessary that we use <math>\le 22 - 16 = 6</math> balls to fill a <math>3 \times 5</math> grid by the same rules.  
+
Similar to the above solution, no color can appear 4 times or more.
  
−
Again, no element may appear <math>\ge 4</math> times, but by Pigeonhole, one element must appear <math>3</math> times. [[Without loss of generality]], let this element be <math>17</math>; then the three boxes containing <math>17</math> must have at least <math>2 \cdot 3 + 1 = 7</math> elements, contradiction.
+
We can use PIE. Let <math>S_1,S_2,\cdots ,S_8</math> be the colors in each of the <math>8</math> boxes. Then <math>n=|\cup_{i=1}^8S_i|</math>. By PIE we know that<cmath>|\cup_{i=1}^8S_i|=\sum_{i=1}^8 |S_i|-\sum_{1\leq i<j\leq 8}|S_i\cap S_j|+\sum_{1\leq i<j<k\leq 8}|S_i\cap S_j\cap S_k|-\sum_{1\leq i<j<k<l\leq 8}|S_i\cap S_j\cap S_k\cap S_l|\cdots.</cmath>Note however that no color can appear 4 times or more, so all the items after <math>\sum_{1\leq i<j<k\leq 8}|S_i\cap S_j\cap S_k|</math> must be equal to 0, so<cmath>|\cup_{i=1}^8S_i|=\sum_{i=1}^8 |S_i|-\sum_{1\leq i<j\leq 8}|S_i\cap S_j|+\sum_{1\leq i<j<k\leq 8}|S_i\cap S_j\cap S_k|.</cmath>Now note that for each <math>i</math>, <math>|S_i|=6,</math> so <math>\sum_{i=1}^8 |S_i|=48.</math> Also no pair of colors appears twice, so for any <math>i,j, |S_i\cap S_j|\leq 1,</math> and so <math>\sum_{1\leq i<j\leq 8}|S_i\cap S_j|\leq \binom82=28.</math> Thus, <math>n\geq 48-28+\sum_{1\leq i<j<k\leq 8}|S_i\cap S_j\cap S_k|.</math> Given that there are <math>n</math> colors, to minimize the number of colors in 3 boxes means each color is in either 2 or 3 boxes, and since there are 48 total spots, this means there are <math>48-2n</math> colors in 3 boxes and <math>3n-48</math> colors in 2. Thus <math>n\geq 20+48-2n,</math> so <math>3n\geq 68</math>, and <math>n\geq23</math> and we are done.
  
−
Therefore, <math>n = 23</math> is the minimum.
+
== Solution 3 ==
 +
Let <math>m_{i,j}</math> be the number of balls which are the same color as the <math>j^{\text{th}}</math> ball in box <math>i</math> (including that ball). For a fixed box <math>i</math>, <math>1\leq i\leq 8</math>, consider the sums
 +
<cmath>
 +
S_i = \sum_{j=1}^6 m_{i,j}\quad\text{and}\quad s_i = \sum_{j=1}^6 \frac{1}{m_{i,j}}.
 +
</cmath>
 +
For each fixed <math>i</math>, since no pair of colors is repeated, each of the remaining seven boxes can contribute at most one ball to <math>S_i</math>. Thus, <math>S_i\leq 13</math>. It follows by the convexity of <math>f(x) = 1/x</math> that <math>s_i</math> is minimized when one of the <math>m_{i,j}</math> is equal to 3 and the other five equal to 2. Hence <math>s_i\geq 17/6</math>. Note that
 +
<cmath>
 +
n = \sum_{i=1}^8 \sum_{j=1}^6 \frac{1}{m_{i,j}}\geq 8\cdot\frac{17}{6} = \frac{68}{3}.
 +
</cmath>
 +
Hence there must be 23 colors. The construction for <math>n = 23</math> is above.
  
 
== See also ==
 
== See also ==
Line 41: Line 42:
  
 
[[Category:Olympiad Combinatorics Problems]]
 
[[Category:Olympiad Combinatorics Problems]]
 +
{{MAA Notice}}

Latest revision as of 16:19, 5 May 2022

Problem

Each of eight boxes contains six balls. Each ball has been colored with one of $n$ colors, such that no two balls in the same box are the same color, and no two colors occur together in more than one box. Determine, with justification, the smallest integer $n$ for which this is possible.

Solution 1

We claim that $n=23$ is the minimum. Consider the following construction (replacing colors with numbers) which fulfills this: \[\left[ \begin{array}{cccccccc} 1 & 1 & 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 7 & 12 & 7 & 8 & 9 & 10 & 11 \\ 3 & 8 & 13 & 12 & 13 & 14 & 15 & 16 \\ 4 & 9 & 14 & 17 & 17 & 17 & 18 & 19 \\ 5 & 10 & 15 & 18 & 20 & 22 & 20 & 21 \\ 6 & 11 & 16 & 19 & 21 & 23 & 22 & 23 \end{array} \right]\] Suppose a configuration exists with $n \le 22$.

Suppose a ball appears $5$ or more times. Then the remaining balls of the $5$ boxes must be distinct, so that there are at least $n \ge 5 \cdot 5 + 1 = 26$ balls, contradiction. If a ball appears $4$ or more times, the remaining balls of the $4$ boxes must be distinct, leading to $5 \cdot 4 + 1 = 21$ balls. The fifth box can contain at most four balls from the previous boxes, and then the remaining two balls must be distinct, leading to $n \ge 2 + 21 = 23$, contradiction.

However, by the Pigeonhole Principle, at least one ball must appear $3$ times. Without loss of generality suppose that $1$ appears three times, and let the boxes that contain these have balls with colors $\{1,2,3,4,5,6\},\{1,7,8,9,10,11\},\{1,12,13,14,15,16\}$. Each of the remaining five boxes can have at most $3$ balls from each of these boxes. Thus, each of the remaining five boxes must have $3$ additional balls $> 16$. Thus, it is necessary that we use $\le 22 - 16 = 6$ balls to fill a $3 \times 5$ grid by the same rules.

Again, no balls may appear $\ge 4$ times, but by Pigeonhole, one ball must appear $3$ times. Without loss of generality, let this ball have color $17$; then the three boxes containing $17$ must have at least $2 \cdot 3 + 1 = 7$ balls, contradiction.

Therefore, $n = 23$ is the minimum.

Solution 2

Similar to the above solution, no color can appear 4 times or more.

We can use PIE. Let $S_1,S_2,\cdots ,S_8$ be the colors in each of the $8$ boxes. Then $n=|\cup_{i=1}^8S_i|$. By PIE we know that\[|\cup_{i=1}^8S_i|=\sum_{i=1}^8 |S_i|-\sum_{1\leq i<j\leq 8}|S_i\cap S_j|+\sum_{1\leq i<j<k\leq 8}|S_i\cap S_j\cap S_k|-\sum_{1\leq i<j<k<l\leq 8}|S_i\cap S_j\cap S_k\cap S_l|\cdots.\]Note however that no color can appear 4 times or more, so all the items after $\sum_{1\leq i<j<k\leq 8}|S_i\cap S_j\cap S_k|$ must be equal to 0, so\[|\cup_{i=1}^8S_i|=\sum_{i=1}^8 |S_i|-\sum_{1\leq i<j\leq 8}|S_i\cap S_j|+\sum_{1\leq i<j<k\leq 8}|S_i\cap S_j\cap S_k|.\]Now note that for each $i$, $|S_i|=6,$ so $\sum_{i=1}^8 |S_i|=48.$ Also no pair of colors appears twice, so for any $i,j, |S_i\cap S_j|\leq 1,$ and so $\sum_{1\leq i<j\leq 8}|S_i\cap S_j|\leq \binom82=28.$ Thus, $n\geq 48-28+\sum_{1\leq i<j<k\leq 8}|S_i\cap S_j\cap S_k|.$ Given that there are $n$ colors, to minimize the number of colors in 3 boxes means each color is in either 2 or 3 boxes, and since there are 48 total spots, this means there are $48-2n$ colors in 3 boxes and $3n-48$ colors in 2. Thus $n\geq 20+48-2n,$ so $3n\geq 68$, and $n\geq23$ and we are done.

Solution 3

Let $m_{i,j}$ be the number of balls which are the same color as the $j^{\text{th}}$ ball in box $i$ (including that ball). For a fixed box $i$, $1\leq i\leq 8$, consider the sums \[S_i = \sum_{j=1}^6 m_{i,j}\quad\text{and}\quad s_i = \sum_{j=1}^6 \frac{1}{m_{i,j}}.\] For each fixed $i$, since no pair of colors is repeated, each of the remaining seven boxes can contribute at most one ball to $S_i$. Thus, $S_i\leq 13$. It follows by the convexity of $f(x) = 1/x$ that $s_i$ is minimized when one of the $m_{i,j}$ is equal to 3 and the other five equal to 2. Hence $s_i\geq 17/6$. Note that \[n = \sum_{i=1}^8 \sum_{j=1}^6 \frac{1}{m_{i,j}}\geq 8\cdot\frac{17}{6} = \frac{68}{3}.\] Hence there must be 23 colors. The construction for $n = 23$ is above.

See also

2001 USAMO (Problems • Resources)
Preceded by
First question 		Followed by
Problem 2
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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2001_USAMO_Problems/Problem_1&oldid=173793"