Competition problem — Combinatorics

Library / /90 of 105

Combinatorics Difficulty 6.7 National Olympiad Prove it JBMO

Problem:
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

Solution:
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$

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.