IMO 1990 SL 14

Origin: JAP

Problem

In the coordinate plane a rectangle with vertices (0, 0), (m, 0), (0, n), (m, n) is given where both m and n are odd integers. The rectangle is partitioned into triangles in such a way that (i) each triangle in the partition has at least one side (to be called a “good” side) that lies on a line of the form x = j or y = k, where j and k are integers, and the altitude on this side has length 1; (ii) each “bad” side (i.e., a side of any triangle in the partition that is not a “good” one) is a common side of two triangles in the partition. Prove that there exist at least two triangles in the partition each of which has two good sides.

Solution

Let V be the set of all midpoints of bad sides, and E the set of segments connecting two points in V that belong to the same triangle. Each edge in E is parallel to exactly one good side and thus is parallel to the coordinate grid and has half-integer coordinates. Thus, the edges of E are a subset of the grid formed by joining the centers of the squares in the original grid to each other. Let G be a graph whose set of vertices is V and set of edges is E. The degree of each vertex X, denoted by d(X), is 0, 1, or 2. We observe the following cases: (i) d(X) = 0 for some X. Then both triangles containing X have two good sides. (ii) d(X) = 1 for some X. Since  X\inV d(X) = 2|E| is even, it follows that at least another vertex Y has the degree 1. Hence both X and Y belong to triangles having two good sides. (iii) d(X) = 2 for all X \inV . We will show that this case cannot occur. We prove first that centers of all the squares of the m\timesn board belong to V \cupE. A bad side contains no points with half-integer coordinates in its interior other than its midpoint. Therefore either a point X is in V , or it lies on the segment connecting the midpoints of the two bad sides. Evidently, the graph G can be partitioned into disjoint cycles. Each center of a square is passed exactly once in exactly one cycle. Let us color the board black and white in a standard chessboard fashion. Each cycle passes through centers that must alternate in color, and hence it contains an equal number of black and white centers. Consequently,

the numbers of black and white squares on the entire board must be equal, contradicting the condition that m and n are odd. Our proof is thus completed.