Difference between revisions of "2001 USAMO Problems/Problem 1"
m (Alternate Solution is incorrect) |
5849206328x (talk | contribs) (→Solution) |
||
(2 intermediate revisions by 2 users not shown) | |||
Line 3: | Line 3: | ||
== Solution == | == Solution == | ||
+ | === 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: | ||
Line 29: | Line 30: | ||
Suppose a configuration exists with <math>n \le 22</math>. | Suppose a configuration exists with <math>n \le 22</math>. | ||
− | Suppose | + | Suppose a ball appears <math>5</math> or more times. Then the remaining balls of the <math>5</math> boxes must be distinct, so that there are at least <math>n \ge 5 \cdot 5 + 1 = 26</math> balls, contradiction. If a ball appears <math>4</math> or more times, the remaining balls of the <math>4</math> boxes must be distinct, leading to <math>5 \cdot 4 + 1 = 21</math> 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 <math>n \ge 2 + 21 = 23</math>, contradiction. |
− | However, by the [[Pigeonhole Principle]], at least one | + | However, by the [[Pigeonhole Principle]], at least one ball 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 balls with colors <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> balls from each of these boxes. Thus, each of the remaining five boxes must have <math>3</math> additional balls <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 | + | Again, no balls may appear <math>\ge 4</math> times, but by Pigeonhole, one ball must appear <math>3</math> times. [[Without loss of generality]], let this ball have color <math>17</math>; then the three boxes containing <math>17</math> must have at least <math>2 \cdot 3 + 1 = 7</math> balls, contradiction. |
Therefore, <math>n = 23</math> is the minimum. | 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 == | == See also == | ||
Line 41: | Line 53: | ||
[[Category:Olympiad Combinatorics Problems]] | [[Category:Olympiad Combinatorics Problems]] | ||
+ | {{MAA Notice}} |
Latest revision as of 13:16, 5 July 2014
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
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
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.