Problem

Source: 2024 Argentina L3 P2

Tags: combinatorics



Consider a square $8 \times 8$ board with its $64$ cells initially white. Determine the minimum number of colors needed to color the cells (each one with only one color) in such a way that if four cells on the board can be covered by an $L$-shaped tile as shown in the figure, then the four cells are of different colors. [asy][asy] size(1.5cm); draw((0,1)--(1,1)--(1,2)--(0,2)--(0,1)--(0,0)--(1,0)--(2,0)--(2,1)--(1,1)--(1,0)--(1,1)--(1,2)--(1,3)--(0,3)--(0,2)); [/asy][/asy] Note: The $L$-shaped tile can be rotated or flipped.