Browse · MathNet
PrintBelarusian Mathematical Olympiad
Belarus counting and probability
Problem
Some cells of a checkered plane are marked so that the figure formed by marked cells satisfies the following two conditions: 1) any cell of the figure has exactly two adjacent cells of ; and 2) the figure can be divided into isosceles trapezoids of area with vertices at the grid nodes (and acute angles of the trapezoids are equal to ).
Prove that the number of marked cells is divisible by .
( A. Yuran )

Prove that the number of marked cells is divisible by .
( A. Yuran )
Solution
It is clear that it is enough to prove the statement of the problem for connected figures , since any disconnected figure is divided into several connected parts, each of which (as we prove) has a number of cells divided by . Let's color some cells of the plane into four colors as shown in the figure.
Without loss of generality, assume that some of the trapezoids is placed as shown in the figure (otherwise, rotate and transfer the coloring). Let's start to bypass the cells of the figure starting with this trapezoid so that we move on from the cell of color to the cell of color (we call such trapezoid a trapezoid ). It is easy to see that with this bypass types of trapezoids alternate in the order . Since at some point we will finish the bypass in the cell of color , from which we started, the number of trapezoids passed is divided by , which means that the total number of cells of the figure is divided by .
Without loss of generality, assume that some of the trapezoids is placed as shown in the figure (otherwise, rotate and transfer the coloring). Let's start to bypass the cells of the figure starting with this trapezoid so that we move on from the cell of color to the cell of color (we call such trapezoid a trapezoid ). It is easy to see that with this bypass types of trapezoids alternate in the order . Since at some point we will finish the bypass in the cell of color , from which we started, the number of trapezoids passed is divided by , which means that the total number of cells of the figure is divided by .
Techniques
Coloring schemes, extremal argumentsInvariants / monovariants