All cells of $2015 \times 2015$ table colored in one of $4$ colors. We count number of ways to place one tetris T-block in table. Prove that T-block has cell of all $4$ colors in less than $51\%$ of total number of ways.
Problem
Source: St Petersburg Olympiad 2015, Grade 9, P3
Tags: combinatorics
26.11.2017 04:31
Any solution?
26.11.2017 14:13
Call a $T$-block colorful if it has all $4$ colors. Note that there are $4\times 2013\times 2014$ different $T$-blocks. Pair each $T$-block with its "center" cell (marked $\times$ in the following picture) [asy][asy] unitsize(16); draw((0,0)--(0,3)--(1,3)--(1,0)--cycle); draw((0,1)--(2,1)--(2,2)--(0,2)); label("$\times$", (0.5, 1.5), fontsize(16pt)); draw((4,1)--(7,1)--(7,2)--(4,2)--cycle); draw((5,1)--(5,3)--(6,3)--(6,1)); label("$\times$", (5.5, 1.5), fontsize(16pt)); [/asy][/asy] Observe that if two colorful $T$-blocks $T_1,T_2$ share a center cell, then the two cells that's in exactly one of $T_1,T_2$ have the same color, so the other two $T$-blocks with that center cell cannot be colorful. Hence for each center cell, at most two of the four $T$-block with that cell as center are colorful. Therefore, there are at most $$2\times (2015)^2 < 51\% \times (4\times 2013\times 2014)$$colorful $T$-blocks. $\blacksquare$
27.11.2017 17:02
Very nice solution by talkon. Thank you.
22.09.2023 10:51
talkon wrote: Call a $T$-block colorful if it has all $4$ colors. Note that there are $4\times 2013\times 2014$ different $T$-blocks. Pair each $T$-block with its "center" cell (marked $\times$ in the following picture) [asy][asy] unitsize(16); draw((0,0)--(0,3)--(1,3)--(1,0)--cycle); draw((0,1)--(2,1)--(2,2)--(0,2)); label("$\times$", (0.5, 1.5), fontsize(16pt)); draw((4,1)--(7,1)--(7,2)--(4,2)--cycle); draw((5,1)--(5,3)--(6,3)--(6,1)); label("$\times$", (5.5, 1.5), fontsize(16pt)); [/asy][/asy] Observe that if two colorful $T$-blocks $T_1,T_2$ share a center cell, then the two cells that's in exactly one of $T_1,T_2$ have the same color, so the other two $T$-blocks with that center cell cannot be colorful. Hence for each center cell, at most two of the four $T$-block with that cell as center are colorful. Therefore, there are at most $$2\times (2015)^2 < 51\% \times (4\times 2013\times 2014)$$colorful $T$-blocks. $\blacksquare$ How to come up with the result $4\times 2013\times 2014$ different T-blocks?