Problem

Source: 1st National Women's Contest of Mexican Mathematics Olympiad 2022 , levels 1+2 p3

Tags: combinatorics



All the squares of a $2022 \times 2022$ board will be colored white or black. Chips will be placed in several of these boxes, at most one per box. We say that two tokens attack each other, when the following two conditions are met: a) There is a path of squares that joins the squares where the pieces were placed. This path can have a horizontal, vertical, or diagonal direction. b) All the squares in this path, including the squares where the pieces are, are of the same color. For example, the following figure shows a small example of a possible coloring of a $6 \times 6$ board with $A, B, C, D$, and $E$ tiles placed. The pairs of checkers that attack each other are $(D, E)$, $(C, D)$, and $(B, E)$. What is the maximum value of $k$ such that it is possible to color the board and place $k$ tiles without any two of them attacking each other?