The $8 \times 8$ board is covered with the same shape as in the picture to the right (each of the shapes can be rotated $90^o$) so that any two do not overlap or extend beyond the edge of the chessboard. Determine the largest possible number of fields of this chessboard can be covered as described above.
Problem
Source: Czech-Polish-Slovak Junior Match 2012, Team p6 CPSJ
Tags: combinatorics, Tiling
socrates
28.09.2022 00:07
Nice problem!
MR.1
11.08.2024 20:08
I think it's 48
Ianis
11.08.2024 21:19
First observe that each shape covers exactly one of the $16$ red boxes below. Hence we can cover at most $16\cdot 3=48$ boxes.$$\begin{matrix}\blacksquare & \blacksquare & \blacksquare & \blacksquare & \blacksquare & \blacksquare & \blacksquare & \blacksquare \\ \blacksquare & \blacksquare & \blacksquare & \blacksquare & \blacksquare & \blacksquare & \blacksquare & \blacksquare \\ \color{red}\blacksquare & \color{red}\blacksquare & \color{red}\blacksquare & \color{red}\blacksquare & \color{red}\blacksquare & \color{red}\blacksquare & \color{red}\blacksquare & \color{red}\blacksquare \\ \blacksquare & \blacksquare & \blacksquare & \blacksquare & \blacksquare & \blacksquare & \blacksquare & \blacksquare \\ \blacksquare & \blacksquare & \blacksquare & \blacksquare & \blacksquare & \blacksquare & \blacksquare & \blacksquare \\ \color{red}\blacksquare & \color{red}\blacksquare & \color{red}\blacksquare & \color{red}\blacksquare & \color{red}\blacksquare & \color{red}\blacksquare & \color{red}\blacksquare & \color{red}\blacksquare \\ \blacksquare & \blacksquare & \blacksquare & \blacksquare & \blacksquare & \blacksquare & \blacksquare & \blacksquare \\ \blacksquare & \blacksquare & \blacksquare & \blacksquare & \blacksquare & \blacksquare & \blacksquare & \blacksquare \\ \end{matrix}$$The following example proves that this bound is achievable.$$\begin{array}{|c|c|c|c|c|c|c|c|}\hline 1&2&3&4&5&6&&\\\hline 7&1&2&3&4&5&6&\\\hline 8&7&1&2&3&4&5&6\\\hline 13&8&7&12&11&10&&\\\hline 15&13&8&9&12&11&10&\\\hline 16&15&13&14&9&12&11&10\\\hline &16&15&&14&9&&\\\hline &&16&&&14&&\\\hline \end{array}$$
magnusarg
11.08.2024 22:37
Lets paint the board like the first attachment. See that the piece always covers exactly one field of the bord. There are $16$ fields painted in orange so there´s at most $16$ pieces. Because there is an example (second attachment) we are done.
Attachments:
