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?
Problem
Source: Vietnam TST 2024 P2
Tags: combinatorics
bin_sherlo
27.03.2024 22:22
Solved with erkosfobiladol. Answer: $12\times 2018$. Example: The $6\times 2018$ rectangle satisifies the condition. After rotating this and replacing $B$ with $C$, we get $2$ rectangles where both have $6\times 2018$ squares. $$ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline A&A&A&B&B&B\\\hline A&A&A&B&B&B\\\hline .&.&.&.&.&.\\\hline A&A&A&B&B&B\\\hline \end{array} $$ Proof: Assume that it's possible to choose more filled squares. Assume that there exists a row with $\geq 2018$ filled squares. Swapping the positions of rows and columns doesnot affect the conditions. Let $l$ be the number of the filled squares in the row or column with maximum filled squares. If there exists a row with $l\geq 2018$ filled squares, $$ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline A&A&A&A&...&A&&&&&\\\hline &&&&&&&&&&\\\hline &&&&&&&&&&\\\hline &&&&&&&&&&\\\hline \end{array} $$The row must be filled by exactly $1$ letter. WLOG let it be $A$. In $i.$ column where $1\leq i\leq l$, there are at most $6$ letters because $A$ in $i.$ column must see $3$ others. So there are at most $6l$ filled squares in the $l\times 2024$ rectangle. Also there can be at most $(2024-l)l$ filled squares in the $(2024-l)\times 2024$ rectangle. Thus there can be at most $6l+(2024-l)l=l(2030-l)$ filled squares. For $l\geq 2018,$ we have $l(2030-l)\leq 2018.12$. In this case, there can be at most $12. 2018$ filled squares. Therefore $l\leq 2017$. Claim: There are at least $7$ rows which have $\geq 7$ filled squares. Proof: Let the rows with $\geq 7$ filled squares be good rows. Denote $m$ as the number of good rows. There can be at most $2017m+(2024-m)6=2011m+2024.6$ filled squares. If $6\geq m\implies 2011.6\geq 2011m\geq 12.2018-6.2024+1\implies 6.4035>12.2018\implies 4035>4036$ which gives a contradiction. The intersection of a good row and a good column must be empty. Denote $g_i$ as the number of filled squares in $i.$ good row. \[\sum{g_i}\geq 12.2018-6.2017+1=6.2019+1\]Intersection of good rows and a column can have at most $6$ filled squares hence \[\sum{g_i}\leq 6.2017\]\[6.2017\geq \sum{g_i}\geq 6.2019+1\]Gives a contradiction.