Maths Olympiad Prep

Library / /51 of 61

Combinatorics Difficulty 7.1 National olympiad, round 2 Prove it Belarus

Some cells of a checkered plane are marked so that the figure AA formed by marked cells satisfies the following two conditions:
1) any cell of the figure AA has exactly two adjacent cells of AA; and
2) the figure AA can be divided into isosceles trapezoids of area 22 with vertices at the grid nodes (and acute angles of the trapezoids are equal to 4545^\circ).

Prove that the number of marked cells is divisible by 88.

( A. Yuran )

Solution

It is clear that it is enough to prove the statement of the problem for connected figures AA, since any disconnected figure is divided into several connected parts, each of which (as we prove) has a number of cells divided by 88. 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 AA starting with this trapezoid so that we move on from the cell of color 11 to the cell of color 22 (we call such trapezoid a trapezoid 121 \to 2). It is easy to see that with this bypass types of trapezoids alternate in the order 12,23,34,411 \to 2, 2 \to 3, 3 \to 4, 4 \to 1. Since at some point we will finish the bypass in the cell of color 11, from which we started, the number of trapezoids passed is divided by 44, which means that the total number of cells of the figure AA is divided by 88.

Figure 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 and solution reproduced as published; topic and difficulty added by this site.