Skip to main content
OlympiadHQ

Browse · MathNet

Print

62nd Belarusian Mathematical Olympiad

Belarus counting and probability

Problem

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

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

problem
Solution
a) It is impossible.

For we can divide the table into 49 of squares. If there are exactly 2 pawns in each of them, then the total number of the pawns in the table is equal to . Since we have more than 98 pawns, we have . On the other hand, if , 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 is given in the figure.

Final answer
a) No; b) Yes

Techniques

Counting two waysColoring schemes, extremal arguments