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:
The smallest such is 23 .
We first show that cannot be achieved. We present two arguments.
First argument 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 reamining seven boxes can contributed 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.
Second argument Assume that some color, say red, occurs four times. Then the first box containing red contains 6 colors, the second contains red and 5 colors not mentioned so far. and likewise for the third and fourth boxes. A fifth box can contain at most one color used in each of these four, so must contain 2 colors not mentioned. so far, and a sixth box must contain 1 color not mentioned so far. for a total of . a contradiction.
Next, assume that no color occurs four times; this forces at least four colors to occur three times. In particular, there are two colors that occur at least three times and which both occur in a single box, say red and blue. Now the box containing red and blue contains 6 colors, the other boxes containing red each contain 5 colors not mentioned so far. and the other boxes containing blue each contain 3 colors not mentioned so far (each may contain one color used in each of the boxes containing red but not blue). A sixth box must contain one color not mentioned so far, for a total of , again a contradiction.
We now give a construction for , guided by the second argument. We still cannot have a color occur four times, so at least two colors must occur three times. Call these red and green. Put one red in each of three boxes. and fill these with 15 other colors. Put one green in each of three boxes, and fill each of these boxes with one color from each of the three boxes containing red and two new colors. We now have used colors, and each box contains two colors that have only been used once so far. Split those colors between the last two boxes. The resulting arrangement is:
| 1 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|
| 1 | 8 | 9 | 10 | 11 | 12 |
| 1 | 13 | 14 | 15 | 16 | 17 |
| 2 | 3 | 8 | 13 | 18 | 19 |
| 2 | 4 | 9 | 14 | 20 | 21 |
| 2 | 5 | 10 | 15 | 22 | 23 |
| 6 | 11 | 16 | 18 | 20 | 22 |
| 7 | 12 | 17 | 19 | 21 | 23 |
Note: Thanks to David Savit. for his help in assembling this solution: he also showed that for 10 boxes of eight balls, the minimum number of colors is 39 . The general case of boxes of balls, or even more generally of boxes of balls for other small values of , may be of interest.
The problems on this page are the property of the MAA's American Mathematics Competitions