Difference between revisions of "2001 USAMO Problems/Problem 1"
ProbaBillity (talk | contribs) (→Solution: Changed "element" to "ball") |
|||
Line 41: | Line 41: | ||
[[Category:Olympiad Combinatorics Problems]] | [[Category:Olympiad Combinatorics Problems]] | ||
+ | {{MAA Notice}} |
Revision as of 13:37, 4 July 2013
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 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.
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.