Difference between revisions of "2001 USAMO Problems/Problem 1"

Revision as of 12:16, 5 July 2014

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

Solution 1

We claim that $n=23$ is the minimum. Consider the following construction (replacing colors with numbers) which fulfills this:

$\begin{tabular}{|r|r|r|r|r|r|} \hline 1 & 2 & 3 & 4 & 5 & 6 \\ \hline 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}$

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

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.

@@ Line 3: / Line 3: @@
 == Solution ==
+=== Solution 1===
 We claim that <math>n=23</math> is the minimum. Consider the following construction (replacing colors with numbers) which fulfills this:
@@ Line 36: / Line 37: @@
 Therefore, <math>n = 23</math> is the minimum.
+=== Solution 2 ===
+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 ==

2001 USAMO (Problems • Resources)
Preceded by First question	Followed by Problem 2
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

Page

Toolbox

Search