On a $5 \times 5$ board, pieces made up of $4$ squares are placed, as seen in the figure, each covering exactly $4$ squares of the board. The pieces can be rotated or turned over. They can also overlap, but they cannot protrude from the board. Suppose that each square on the board is covered by at most two pieces. Find the maximum number of squares on the board that can be covered (by one or two pieces).
Problem
Source: Argentina IberoAmerican TST 2024 P2
Tags: combinatorics
02.10.2024 02:37
I paint the board as the "supper evens" coloration (attachment 1). The piece will always cover exactly one blue square. Then there can be placed at most $2*4=8$ pieces. Now, lets paint the board as the "supper odds" coloration (attachment 2). The piece will always cover exactly one blue square. Because there are at most $8$ pieces one of the $9$ blue squares can not be covered. Leading to the total of covered squares being at most $24$. There is an example (attachments 3 and 4) and we are done . Aops wont let me put the 4th attachment so I let it to readers imagination
Attachments:



12.01.2025 20:44
$\color{green} \boxed{\textbf{SOLUTION}}$ It's easy to show that - It's possible to cover $24$ squares, FTSOC, We can cover $25$ squares, take two $5\times 5$ grids and color them like chess board such that $12$ squares are Black and $13$ squares are White for each grid. Consider the $4$ corner White squares of inner $3\times 3$ grid. It's easy to see that no matter wherever we place the $Z$ box It will go through one of it. So, we can place atmost $8$ $Z$ boxes If, We have to cover all $25$ squares we need to cover $13$ White squares. But for each case we can cover $8$ White squares and minimum $4$ Whites will be covered in both grid, giving maximum of $8+8-4=12$ White square covered. Contradiction $\blacksquare$