Difference between revisions of "2001 USAMO Problems/Problem 1"
Cocohearts (talk | contribs) m (→Solution 2) |
m (→Solution 2) |
||
(10 intermediate revisions by 3 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 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} | |
− | <cmath> | + | 1 & 1 & 1 & 2 & 3 & 4 & 5 & 6 \\ |
− | \begin{ | + | 2 & 7 & 12 & 7 & 8 & 9 & 10 & 11 \\ |
− | + | 3 & 8 & 13 & 12 & 13 & 14 & 15 & 16 \\ | |
− | 1 & 2 & 3 & 4 & 5 & 6 \\ | + | 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> | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | 5 & 10 & 15 & 18 & 20 & 22 \\ | ||
− | |||
− | 6 & 11 & 16 & 19 & 21 & 23 | ||
− | |||
− | \end{ | ||
− | </cmath> | ||
− | |||
Suppose a configuration exists with <math>n \le 22</math>. | Suppose a configuration exists with <math>n \le 22</math>. | ||
Line 38: | Line 21: | ||
Therefore, <math>n = 23</math> is the minimum. | Therefore, <math>n = 23</math> is the minimum. | ||
− | + | == Solution 2 == | |
− | === Solution 3 | + | Similar to the above solution, no color can appear 4 times or more. |
+ | |||
+ | 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. | ||
+ | |||
+ | == 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 | 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> | <cmath> | ||
Line 50: | Line 37: | ||
</cmath> | </cmath> | ||
Hence there must be 23 colors. The construction for <math>n = 23</math> is above. | Hence there must be 23 colors. The construction for <math>n = 23</math> is above. | ||
− | |||
− | |||
== See also == | == See also == |
Latest revision as of 17:19, 5 May 2022
Problem
Each of eight boxes contains six balls. Each ball has been colored with one of 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
for which this is possible.
Solution 1
We claim that is the minimum. Consider the following construction (replacing colors with numbers) which fulfills this:
Suppose a configuration exists with
.
Suppose a ball appears or more times. Then the remaining balls of the
boxes must be distinct, so that there are at least
balls, contradiction. If a ball appears
or more times, the remaining balls of the
boxes must be distinct, leading to
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
, contradiction.
However, by the Pigeonhole Principle, at least one ball must appear times. Without loss of generality suppose that
appears three times, and let the boxes that contain these have balls with colors
. Each of the remaining five boxes can have at most
balls from each of these boxes. Thus, each of the remaining five boxes must have
additional balls
. Thus, it is necessary that we use
balls to fill a
grid by the same rules.
Again, no balls may appear times, but by Pigeonhole, one ball must appear
times. Without loss of generality, let this ball have color
; then the three boxes containing
must have at least
balls, contradiction.
Therefore, is the minimum.
Solution 2
Similar to the above solution, no color can appear 4 times or more.
We can use PIE. Let be the colors in each of the
boxes. Then
. By PIE we know that
Note however that no color can appear 4 times or more, so all the items after
must be equal to 0, so
Now note that for each
,
so
Also no pair of colors appears twice, so for any
and so
Thus,
Given that there are
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
colors in 3 boxes and
colors in 2. Thus
so
, and
and we are done.
Solution 3
Let be the number of balls which are the same color as the
ball in box
(including that ball). For a fixed box
,
, consider the sums
For each fixed
, since no pair of colors is repeated, each of the remaining seven boxes can contribute at most one ball to
. Thus,
. It follows by the convexity of
that
is minimized when one of the
is equal to 3 and the other five equal to 2. Hence
. Note that
Hence there must be 23 colors. The construction for
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.