Problem

Source: Vietnam TST 2024 P2

Tags: combinatorics



In a garden, which is organized as a $2024\times 2024$ board, we plant three types of flowers: roses, daisies, and orchids. We want to plant flowers such that the following conditions are satisfied: (i) Each grid is planted with at most one type of flower. Some grids can be left blank and not planted. (ii) For each planted grid $A$, there exist exactly $3$ other planted grids in the same column or row such that those $3$ grids are planted with flowers of different types from $A$'s. (iii) Each flower is planted in at least $1$ grid. What is the maximal number of the grids that can be planted with flowers?