Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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 contain <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.  
+
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 12:25, 11 April 2010

Problem

Each of eight boxes contains six balls. Each ball has been colored with one of $n$ 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 $n$ for which this is possible.

Solution

We claim that $n=23$ is the minimum. Consider the following construction (replacing colors with numbers) which fulfills this:

\[\begin{tabular}{|r|r|r|r|r|r|} \hline 1 & 2 & 3 & 4 & 5 & 6 \\ \hline 1 & 7 & 8 & 9 & 10 & 11 \\ \hline 1 & 12 & 13 & 14 & 15 & 16 \\ \hline 2 & 7 & 12 & 17 & 18 & 19 \\ \hline 3 & 8 & 13 & 17 & 20 & 21 \\ \hline 4 & 9 & 14 & 17 & 22 & 23 \\ \hline 5 & 10 & 15 & 18 & 20 & 22 \\ \hline 6 & 11 & 16 & 19 & 21 & 23 \\ \hline \end{tabular}\]

Suppose a configuration exists with $n \le 22$.

Suppose an element appears $5$ or more times. Then the remaining elements of the $5$ boxes must be distinct, so that there are at least $n \ge 5 \cdot 5 + 1 = 26$ elements, contradiction. If an element appears $4$ or more times, the remaining elements of the $4$ boxes must be distinct, leading to $5 \cdot 4 + 1 = 21$ 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 $n \ge 2 + 21 = 23$, contradiction.

However, by the Pigeonhole Principle, at least one element must appear $3$ times. Without loss of generality suppose that $1$ appears three times, and let the boxes that contain these have the elements $\{1,2,3,4,5,6\},\{1,7,8,9,10,11\},\{1,12,13,14,15,16\}$. Each of the remaining five boxes can have at most $3$ elements from each of these boxes. Thus, each of the remaining five boxes must have $3$ additional elements $> 16$. Thus, it is necessary that we use $\le 22 - 16 = 6$ balls to fill a $3 \times 5$ grid by the same rules.

Again, no element may appear $\ge 4$ times, but by Pigeonhole, one element must appear $3$ times. Without loss of generality, let this element be $17$; then the three boxes containing $17$ must have at least $2 \cdot 3 + 1 = 7$ elements, contradiction.

Therefore, $n = 23$ 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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2001_USAMO_Problems/Problem_1&oldid=34281"