Ali has $6$ types of $2\times2$ squares with cells colored in white or black, and has presented them to Mohammad as forbidden tiles. $a)$ Prove that Mohammad can color the cells of the infinite table (from each $4$ sides.) in black or white such that there's no forbidden tiles in the table. $b)$ Prove that Ali can present $7$ forbidden tiles such that Mohammad cannot achieve his goal.
Problem
Source: 2017 Iran MO 3rd round, first combinatorics exam P3
Tags: Iran, combinatorics
math90
14.09.2017 13:14
We'll prove that at least one of the following colorings is valid:
All cells are white.
All cells are black.
White-black alternating rows.
White-black alternating columns.
A cell $(x,y)$ is white if and only if $2\mid x$ and $2\mid y$.
A cell $(x,y)$ is black if and only if $2\mid x$ and $2\mid y$.
Chessboard coloring.
It's easy to see that each type of $2\times 2$ tiles is contained in exactly one of the listed colorings. Hence, by pigeonhole principle, at least one of the listed colorings doesn't contain a forbidden tile.
Choose the following $2\times 2$ tiles:
1-4. All $2\times 2$ tiles in which the upper-left cell is black and the lower-left cell is white.
5. All-black tile.
6. All-white tile.
7.
$\begin{bmatrix} \text{black} & \text{white} \\ \text{black} & \text{white} \\ \end{bmatrix}$
Assume, for contradiction, that there exists an infinite table coloring which avoids forbidden tiles. Since all-white coloring is invalid, such a coloring must contain a black cell. Look at a $2\times 3$ sub-table:
$\begin{bmatrix}A&B\\C&D\\E&F\\\end{bmatrix}$
and assume WLOG that $A$ is black. Hence $C$,$E$ are black as well. If $D$ is black, then $F$ is black and $C,D,E,F$ is an all-black tile, contradiction. Hence $D$ is white. Since tile (7) is forbidden, $B$ must be black. Hence $D$ is black, contradiction.
Taha1381
22.10.2018 15:37
Does rotating a $2 \times 2$ square produce a new one?
Elthd
25.10.2018 15:30
Hello Maby it is correct 1. All White Square 2. All black square 2. Right and left hemisphere black(need 2 square near by ) 4. Up and down hemisphere black (need 2 square) 5. Like a chess board (need 4square) 6. One black in a 3×3ina center ( need 4 kind of square ) 7.one white in a 3×3in a cebter (4 squar) We can coloer the cell by thease 7methods but All has selection 6 typ of square consequntly we have a one method to coloring