We can divide all these parallelograms into 7 classes (types I-VII), according to Figure.

!

Type 1: There are $n$ ways to choose the strip for the horizontal (shorter) side of the parallelogram, and $(n-1)$ ways to choose the strip (of the width 2) for the vertical (longer) side. So there are $n(n-1)$ parallelograms of the type I.

Type II: There are $(n-1)$ ways to choose the strip (of the width 2) for the horizontal (longer) side, and $n$ ways to choose the strip for the vertical (shorter) side. So the number of the parallelogram of this type is also $n(n-1)$.

Type III: Each parallelogram of this type is a square inscribed in a unique square $2 \times 2$ of our grid. The number of such squares is $(n-1)^{2}$. So there are $(n-1)^{2}$ parallelograms of type III. For each of the types IV, V, VI, VII, the strip of the width 1 in which the parallelogram is located can be chosen in $n$ ways and for each such choice there are $n-2$ parallelograms located in the chosen strip.

Summing we obtain that the total number of parallelograms is:

$$2 n(n-1)+(n-1)^{2}+4 n(n-2)=7 n^{2}-12 n+1$$

(C5) CYP

We have a $5 \times 5$ chessboard and a supply of $\mathrm{L}$-shaped triominoes, i.e. $2 \times 2$ squares with one corner missing. Two players $A$ and $B$ play the following game: A positive integer $k \leq 25$ is chosen. Starting with $A$, the players take alternating turns marking squares of the chessboard until they mark a total of $k$ squares. (In each turn a player has to mark exactly one new square.)

At the end of the process, player $A$ wins if he can cover without overlapping all but at most 2 unmarked squares with $\mathrm{L}$-shaped triominoes, otherwise player $\boldsymbol{B}$ wins. It is not permitted any marked squares to be covered.

Find the smallest $\boldsymbol{k}$, if it exists, such that player $\boldsymbol{B}$ has a winning strategy.

## Solution:

We will show that player $A$ wins if $k=1,2$ or 3, but player $B$ wins if $k=4$. Thus the smallest $k$ for which $B$ has a winning strategy exists and is equal to 4.

If $k=1$, player $A$ marks the upper left corner of the square and then fills it as follows.

!

If $k=2$, player $A$ marks the upper left corner of the square. Whatever square player $B$ marks, then player $\boldsymbol{A}$ can fill in the square in exactly the same pattern as above except that he doesn't put the triomino which covers the marked square of $B$. Player $A$ wins because he has left only two unmarked squares uncovered.

For $k=3$, player $\boldsymbol{A}$ wins by following the same strategy. When he has to mark a square for the second time, he marks any yet unmarked square of the triomino that covers the marked square of $B$.

Let us now show that for $k=4$ player $B$ has a winning strategy. Since there will be 21 unmarked squares, player $\boldsymbol{A}$ will need to cover all of them with seven L-shaped triominoes. We can assume that in his first move, player $\boldsymbol{A}$ does not mark any square in the bottom two rows of the chessboard (otherwise just rotate the chessboard). In his first move player $\boldsymbol{B}$ marks the square labeled 1 in the following figure.

!

If player $\boldsymbol{A}$ in his next move does not mark any of the squares labeled 2,3 and 4 then player $\boldsymbol{B}$ marks the square labeled 3. Player $\boldsymbol{B}$ wins as the square labeled 2 is left unmarked but cannot be covered with an L-shaped triomino.

If player $\boldsymbol{A}$ in his next move marks the square labeled 2, then player $\boldsymbol{B}$ marks the square labeled 5. Player $B$ wins as the square labeled 3 is left unmarked but cannot be covered with an L-shaped triomino.

Finally, if player $\boldsymbol{A}$ in his next move marks one of the squares labeled 3 or 4, player $\boldsymbol{B}$ marks the other of these two squares. Player $\boldsymbol{B}$ wins as the square labeled 2 is left unmarked but cannot be covered with an L-shaped triomino.

Since we have covered all possible cases, player $B$ wins when $k=4$.