Difference between revisions of "2001 USAMO Problems/Problem 1"
(solution) |
(→Solution) |
||
Line 31: | Line 31: | ||
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. | 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. | ||
− | 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 | + | 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 <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. |
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. | 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. | ||
− | Therefore, <math>n = 23</math> is the minimum. | + | Therefore, <math>n = 23</math> is the minimum. |
== See also == | == See also == |
Revision as of 13:25, 11 April 2010
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
We claim that is the minimum. Consider the following construction (replacing colors with numbers) which fulfills this:
Suppose a configuration exists with .
Suppose an element appears or more times. Then the remaining elements of the boxes must be distinct, so that there are at least elements, contradiction. If an element appears or more times, the remaining elements of the boxes must be distinct, leading to 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 , contradiction.
However, by the Pigeonhole Principle, at least one element must appear times. Without loss of generality suppose that appears three times, and let the boxes that contain these have the elements . Each of the remaining five boxes can have at most elements from each of these boxes. Thus, each of the remaining five boxes must have additional elements . Thus, it is necessary that we use balls to fill a grid by the same rules.
Again, no element may appear times, but by Pigeonhole, one element must appear times. Without loss of generality, let this element be ; then the three boxes containing must have at least elements, contradiction.
Therefore, is the minimum.
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 |