Competition problem — Combinatorics

Combinatorics Difficulty 5.3 AIME, harder Prove it Belarus

a) Is it possible for some $n$ to arrange 100 pawns in the cells of an $n \times n$ table so that at most one pawn stands in each cell and exactly 2 pawns stand in each $2 \times 2$ square?

b) Is it possible to arrange 110 pawns in the same way?

Solution

a) It is impossible.

For $n = 14$ we can divide the table into 49 of $2 \times 2$ squares. If there are exactly 2 pawns in each of them, then the total number of the pawns in the table is equal to $2 \cdot 49 = 98$ . Since we have more than 98 pawns, we have $n > 14$ . On the other hand, if $n \geq 15$ , then there are at least 105 pawns in the table (see solution of Problem A.8). It follows that 100 pawns cannot be arranged in the table.

b) It is possible.

The required arrangement of the 110 pawns for $n = 15$ is given in the figure.

Looking for a route rather than 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 and solution reproduced as published; topic and difficulty added by this site.