There are three types of piece shown as below. Today Alice wants to cover a $100 \times 101$ board with these pieces without gaps and overlaps. Determine the minimum number of $1\times 1$ pieces should be used to cover the whole board and not exceed the board. (There are an infinite number of these three types of pieces.) [asy][asy] size(9cm,0); defaultpen(fontsize(12pt)); draw((9,10) -- (59,10) -- (59,60) -- (9,60) -- cycle); draw((59,10) -- (109,10) -- (109,60) -- (59,60) -- cycle); draw((9,60) -- (59,60) -- (59,110) -- (9,110) -- cycle); draw((9,110) -- (59,110) -- (59,160) -- (9,160) -- cycle); draw((109,10) -- (159,10) -- (159,60) -- (109,60) -- cycle); draw((180,11) -- (230,11) -- (230,61) -- (180,61) -- cycle); draw((180,61) -- (230,61) -- (230,111) -- (180,111) -- cycle); draw((230,11) -- (280,11) -- (280,61) -- (230,61) -- cycle); draw((230,61) -- (280,61) -- (280,111) -- (230,111) -- cycle); draw((280,11) -- (330,11) -- (330,61) -- (280,61) -- cycle); draw((280,61) -- (330,61) -- (330,111) -- (280,111) -- cycle); draw((330,11) -- (380,11) -- (380,61) -- (330,61) -- cycle); draw((330,61) -- (380,61) -- (380,111) -- (330,111) -- cycle); draw((401,11) -- (451,11) -- (451,61) -- (401,61) -- cycle); [/asy][/asy] Proposed by amano_hina
Problem
Source: IMOC 2022 C3
Tags: combinatorics, dominoes
10.10.2022 21:52
The answer is $2$ Firts assume that we can cover the board without $1\times 1$ pieces. Consider the following colouring of the board: Color the first $1\times 100$ row black, the second white, ..., the $101$-th row black. Observe that every piece of type I (that with 5 cells) covers $4$ black and $1$ white or $4$ white and $1$ black cells. So blacks-white differ by 3 The same is true for the pieces of type II(here they differ by 0 so a multiply of 3 again). So if we cover the whole board then we must have $3|B-W=100$ which is not the case( $B$ is the total number of black squares and $W$ the total number of white ones. Similarly we can see that we can't use only one $1\times 1$ piece to cover the board. Color the first $1\times 101$ column black, the second white etc. Then we must have $3|B-W\pm 1\equiv \pm 1 \pmod 3$ which is again impossible, ( where we add $+1$ when the $1\times 1$ piece is white and $-1$ when it is black. Now it remains to find a tilling using only $2$ unit squares. The following tilling finishes the proof.
Attachments:
