# Task 7.5

On a checkerboard of size $8 \times 8$, Petya colors several cells. Vasya wins if he can cover all these cells with non-overlapping and non-protruding L-shaped corners consisting of three cells. What is the minimum number of cells Petya should color so that Vasya cannot win?

## Number of points 7  Answer:

64 cells
# Solution

Since 64 is not divisible by 3, the entire board (64 squares) cannot be covered by non-overlapping and non-overflowing L-shaped pieces of three squares. We will show that any 63 colored squares can be covered by such L-shaped pieces. Divide the $8 \times 8$ square into four $4 \times 4$ squares, and each $4 \times 4$ square into four $2 \times 2$ squares. Then the only uncolored square falls into one of the $2 \times 2$ squares, and this square falls into one of the $4 \times 4$ squares. Any three completely colored $2 \times 2$ squares (see the left image) can be covered by L-shaped pieces of three squares, and in the fourth square, any three colored squares can always be covered by one L-shaped piece, so any three completely colored $4 \times 4$ squares can be covered by L-shaped pieces of three squares (see the right image).
![](https://cdn.mathpix.com/cropped/2024_05_06_daa24a2024b4bcb39a05g-3.jpg?height=306&width=504&top_left_y=869&top_left_x=201)