
C4

GRE

Let $n \geq 1$ be a positive integer. A square of side length $n$ is divided by lines parallel to each side into $n^{2}$ squares of side length 1 . Find the number of parallelograms which have vertices among the vertices of the $n^{2}$ squares of side length 1 , with both sides smaller or equal to 2 , and which have the area equal to 2 .


Solution:

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

![](https://cdn.mathpix.com/cropped/2024_06_05_07a1b610f48bd7c35addg-17.jpg?height=632&width=1277&top_left_y=1207&top_left_x=291)

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 comer 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.

