On an infinite white checkered sheet, a square $Q$ of size $12$ × $12$ is selected. Petya wants to paint some (not necessarily all!) cells of the square with seven colors of the rainbow (each cell is just one color) so that no two of the $288$ three-cell rectangles whose centers lie in $Q$ are the same color. Will he succeed in doing this? (Two three-celled rectangles are painted the same if one of them can be moved and possibly rotated so that each cell of it is overlaid on the cell of the second rectangle having the same color.) (Bogdanov. I)
Problem
Source: Silk Road Mathematical Competition 2017, P1.
Tags: combinatorics, srmc
25.05.2017 20:27
First note that there are $8$ possible colors for each cell ($7$ rainbow colors plus white), hence there are $8^2 = 64$ three-celled rectangles with the two outer cells having the same color and $\frac{1}{2}\times 8^2\times 7 = 224$ with two outer cells having different colors. This means there are exactly $288$ possible distinct rectangles - so every rectangle must appear exactly once. For each ($1\times 3$) rectangle $R$, let $o(R)$ and $c(R)$ denote the number of white cells in $R$'s two outer cells and $R$'s center cell respectively. (so $o(R)\in\{0,1,2\}$ and $c(R)\in\{0,1\}$ always.) Since all colors appear equally, $\sum_{R} o(R)=\frac{1}{8}(288\times 2)=72$ and $\sum_{R} c(R)=\frac{1}{8}(288)=36$. Now note that both sums can also be counted from the white cells. The $48$ white cells adjacent to $Q$ contribute $48$ to $\sum_{R} o(R)$ and $0$ to $\sum_{R} c(R)$. (since they appear in the $48$ rectangles that extend outside $Q$ - all as 'outer' cells) Therefore the white cells in $Q$ must contribute $24$ to $\sum_{R} o(R)$ and $36$ to $\sum_{R} c(R)$. However, as $24<36$, this is impossible from the fact that each white cell $w$ in $Q$ contribute exactly $2$ to $\sum_{R} c(R)$ and at least $2$ to $\sum_{R} o(R)$ (that is, there are two rectangles with center $w$ and $\geq 2$ with $w$ as an outer cell) Thus the answer is: Petya will not succeed.
05.03.2023 17:48
First wo prove that every rectangle must appear exactly once. This part is the same as talkon's solution. Assume the colors $c_1, \dots ,c_7, W$. Then we have a look at the rectangles: $c_1c_2c_1, \dots, c_1c_2c_7, c_1c_2W$(probably rotated). Obviously, any cells except the $W$ can't lie outside the $12*12$ square. So there must be a cell next to the $c_1$ on the extended line of $c_2c_1$. Like this: $A_1c_1c_2c_1A_2, A_3c_1c_2c_2, \dots, A_9c_1c_2W$. And there must be two cells among $A_1, \dots, A_9$ having the same color. Then there are two rectangles with the form $Xc_1c_2$ painted the same. Contradiction. So Petya won't succeed.