Prove that it is guaranteed to find four light bulbs of the same color which form the corners of a rectangle.

Question

Consider a matrix of light bulbs with 7 columns and 280,000 rows. Each bulb can be 1 of 6 different colors. Prove that in this matrix, it is guaranteed to find four light bulbs of the same color which form the four corners of a rectangle.

I know this is a pigeon-hole principle problem, but I'm not sure how to think about it.

For an arbitrary row, we know there are $P^R(6,7)=6^7$ possible color combinations. We also know because there must be a repeat of at least one color per row. But i'm not sure how to prove the rectangle...

Answer 1

Hint: We begin with the fact that each row must have at least one color that is repeated.

If we assume that the same color is repeated in every row, then eventually, we must repeat the selection of the same two positions by Pigeonhole Principle, and a rectangle is formed.

Finally, we notice that in order to avoid this from happening, we try to switch the repeated color, but since we only have finitely many colors, at some point we will run out of choices for colors as well.

Calculating how many rows this takes will net you a number well under $280000$.

Answer 2

Since $6^7<280000$, there will be two rows colored the same. Find a repeated color in one of those two rows; that color is also repeated, in the same positions, in the other of those two rows.