IMO 2000 SL C5

Origin: RUS | Category: Combinatorics

Problem

In the plane we have n rectangles with parallel sides. The sides of distinct rectangles lie on distinct lines. The boundaries of the rectangles cut the plane into connected regions. A region is nice if it has at least one of the vertices of the n rectangles on its boundary. Prove that the sum of the numbers of the vertices of all nice regions is less than 40n. (There can be nonconvex regions as well as regions with more than one boundary curve.)

Solution

We say that a vertex of a nice region is convex if the angle of the region at that vertex equals 90◦; otherwise (if the angle is 270◦), we say that a vertex is concave. For a simple broken line C contained in the boundary of a nice region R we call the pair (R, C) a boundary pair. Such a pair is called outer if the region R is inside the broken line C, and inner otherwise. Let Bi, Bo be the sets of inner and outer boundary pairs of nice regions respectively, and let B = Bi \cupBo. For a boundary pair b = (R, C) denote by cb and vb respectively the number of convex and concave vertices of R that belong to C. We have the following facts: (1) Each vertex of a rectangle corresponds to one concave angle of a nice region and vice versa. This correspondence is bijective, so  b\inB vb = 4n.

(2) For a boundary pair b = (R, C) the sum of angles of R that are on C equals (cb + vb −2)180◦if b is outer, and (cb + vb + 2)180◦if b is inner. On the other hand the sum of angles is obviously equal to cb\cdot90◦+vb\cdot270◦. It immediately follows that cb−vb = . 4 if b \inBo, −4 if b \inBi. (3) Since every vertex of a rectangle appears in exactly two boundary pairs and each boundary pair contains at least one vertex of a rectangle, the number K of boundary pairs is less than or equal to 8n. (4) The set Bi is nonempty, because every boundary of the infinite region is inner. Consequently, the sum of the numbers of the vertices of all nice regions is equal to  b\inB (cb + vb) =  b\inB (2vb + (cb −vb)) \leq2 \cdot 4n + 4(K −1) −4 \leq40n −8.