41st IMO shortlist 2000/C5 solution

41st IMO 2000 shortlist

Problem C5

n rectangles are drawn in the plane. Each rectangle has parallel sides and the sides of distinct rectangles lie on distinct lines. The rectangles divide the plane into a number of regions. For each region R let v(R) be the number of vertices. Take the sum ∑ v(R) over the regions which have one or more vertices of the rectangles in their boundary. Show that this sum is less than 40n.

For example, for the two rectangles illustrated the sum is 28 < 80. Note that the unbounded outer region has 12 vertices, and we do not count the central region because it does not contain any vertices of the two rectangles.

Solution

We can classify vertices as convex if the angle inside the region at the vertex is 90^o and concave if it is 270^o. Note that a concave vertex must be a vertex of one of the rectangles. A region has a unique outer boundary and possibly one or more inner boundaries, meaning closed loops which form part of the boundary of the region but whose inside does not form part of the region. For example, the shaded region below has two inner boundaries.

Let a pair (R, P) be a region R and one of its boundaries P. The vertices of the pair are the vertices on P. The number of convex vertices of a pair less the number of concave vertices of the pair is 4 for an outer boundary and -4 for an inner boundary. To see that, lay an arrow along a side of an outer boundary pointing in the anticlockwise direction and move it anticlockwise in a complete circuit of the boundary. It rotates 90^o anticlockwise at a convex vertex and 90^o clockwise at a concave vertex, but it must rotate a total of 360^o anticlockwise in a complete circuit. Similarly for an inner boundary (but the convex and concave vertices are interchanged).

Let N₀ be the number of pairs (R, P) with P an outer boundary which contains at least one of the vertices of the rectangles, and let N₁ be the number of pairs (R, P) with P an inner boundary which contains at least one of the vertices of the rectangles. The rectangles have a total of 4n vertices and each vertex is in at most two outer boundaries. So N₀ <= 8n. On the other hand the unbounded region has an inner boundary which contains at least one of the vertices of the rectangles. So N₁ ≥ 1.

Let B be the set of boundary pairs (R, P) where P contains at least one of the vertices of the rectangles. If b ∈ B, let x_b be the number of convex vertices in P and v_b be the number of concave vertices in P. Then, using the results above, the total number of vertices of regions which have at least one of the rectangles' vertices in their boundaries is ∑_B (x_b + v_b) = ∈_B 2v_b + ∈ (x_b - v_b) = 8n + 4N₀ - 4N₁ ≤ 8n + 4.8n - 4 < 40n.

41st IMO shortlist 2000