Browse · MathNet
Print62nd 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?

b) Is it possible to arrange 110 pawns in the same way?
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.
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