Library / /12 of 25

, 2008

Combinatorics Difficulty 5.6 AIME, harder Prove it Ukraine

Peter has several equal squares with dimensions: $4 \times 4$ . Each square is divided into sectors $(1 \times 1)$ . He paints each of these sectors red or blue so that there are no similar patterns in all columns and all rows of all the squares. Rotating the squares is forbidden. How many squares can Peter paint in that way?

Answer: 4.

Solution

Altogether there are $2^4 = 16$ different patterns of painted columns. Since each square has 4 columns, in all there can not be more than $\frac{2^4}{4} = 4$ differently painted squares.

0001	1110	0110	1001
0010	1101	0011	1100
0100	1011	0101	1010
1000	0111	0000	1111

Let's prove that we can paint this number of squares. An example is shown in the table. Checking the columns is enough, if their patterns are different, the symmetry about the diagonal proves the difference of the row patterns.

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 and solution reproduced as published; topic and difficulty added by this site.