Browse · MathNet
PrintUkrajina 2008
Ukraine 2008 counting and probability
Problem
Peter has several equal squares with dimensions: . Each square is divided into sectors . 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.
Answer: 4.
Solution
Altogether there are different patterns of painted columns. Since each square has 4 columns, in all there can not be more than differently painted squares.
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.
| 0001 | 1110 | 0110 | 1001 |
|---|---|---|---|
| 0010 | 1101 | 0011 | 1100 |
| 0100 | 1011 | 0101 | 1010 |
| 1000 | 0111 | 0000 | 1111 |
Final answer
4
Techniques
Pigeonhole principleEnumeration with symmetry