Competition problem — Combinatorics

Library / /570 of 740

Combinatorics Difficulty 5.2 AIME, harder Prove it United States

Problem:

Betty has a $3 \times 4$ grid of dots. She colors each dot either red or maroon. Compute the number of ways Betty can color the grid such that there is no rectangle whose sides are parallel to the grid lines and whose vertices all have the same color.

Solution

Solution:

First suppose no $3 \times 1$ row is all red or all blue. Then each row is either two red and one blue, or two blue and one red. There are $6$ possible configurations of such a row, and as long as no row is repeated, there's no monochromatic rectangle. This gives $6 \cdot 5 \cdot 4 \cdot 3 = 360$ possibilities.

Now suppose we have a $3 \times 1$ row that's all red. Then the remaining rows must be two blue and one red, and all $3$ such configurations must appear. This gives $4! = 24$ , and having an all blue row is also $4! = 24$ .

The final answer is $360 + 24 + 24 = 408$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.