IMO 1997 SL 1

Origin: BLR

Problem

An infinite square grid is colored in the chessboard pattern. For any pair of positive integers m, n consider a right-angled triangle whose vertices are grid points and whose legs, of lengths m and n, run along the lines of the grid. Let Sb be the total area of the black part of the triangle and Sw the total area of its white part. Define the function f(m, n) = |Sb −Sw|. (a) Calculate f(m, n) for all m, n that have the same parity. (b) Prove that f(m, n) \leq1 2 max(m, n). (c) Show that f(m, n) is not bounded from above.

Solution

Let ABC be the given triangle, with \angleB = 90◦and AB = m, BC = n. For an arbitrary polygon P we denote by w(P) and b(P) respectively the total areas of the white and black parts of P. (a) Let D be the fourth vertex of the rectangle ABCD. When m and n are of the same parity, the coloring of the rectangle ABCD is centrally symmetric with respect to the midpoint of AC. It fol- lows that w(ABC) = 1 2w(ABCD) and b(ABC) = 1 2b(ABCD); thus f(m, n) = 1 2|w(ABCD) −b(ABCD)|. Hence f(m, n) equals 1 2 if m and n are both odd, and 0 otherwise. (b) The result when m, n are of the same parity follows from (a). Suppose that m > n, where m and n are of different parity. Choose a point E on AB such that AE = 1. Since by (a) |w(EBC) −b(EBC)| = f(m −1, n) \leq 2, we have f(m, n) \leq 2 + |w(EAC) −b(EAC)| \leq 2 + S(EAC) = 1 2 + n−1 = n 2 . Therefore f(m, n) \leq1 2 min(m, n). (c) Let us calculate f(m, n) for m = 2k+1, n = 2k, k \inN. With E defined as in (b), we have BE = BC = 2k. If the square at B is w.l.o.g. white, CE passes only through black squares. The white part of \triangleEAC then consists of 2k similar triangles with areas 1 i 2k i 2k+1 = i2 4k(2k+1), where i = 1, 2, . . ., 2k. The total white area of EAC is 4k(2k + 1)(12 + 22 + \cdot \cdot \cdot + (2k)2) = 4k + 1 . Therefore the black area is (8k−1)/12, and f(2k+1, 2k) = (2k−1)/6, which is not bounded.