IMO 1997 · Problem 1

In the plane the points with integer coordinates are the vertices of unit squares. The squares are colored alternately black and white (as on a chessboard).

For any pair of positive integers \(m\) and \(n\), consider a right-angled triangle whose vertices have integer coordinates and whose legs, of lengths \(m\) and \(n\), lie along edges of the squares.

Let \(S_1\) be the total area of the black part of the triangle and \(S_2\) be the total area of the white part. Let \[ f(m,n)=|S_1-S_2|. \]

(a) Calculate \(f(m,n)\) for all positive integers \(m\) and \(n\) which are either both even or both odd.

(b) Prove that \(f(m,n)\leq \frac12\max\{m,n\}\) for all \(m\) and \(n\).

(c) Show that there is no constant \(C\) such that \(f(m,n)<C\) for all \(m\) and \(n\).

Official text of the problem. Official problem paper (PDF)

Answer

\[ \boxed{ f(m,n)= \begin{cases} 0,&m,n\text{ both even},\\[2pt] \frac12,&m,n\text{ both odd}. \end{cases}} \]

The bound in (b) holds, and \(f\) is unbounded. In particular, \[ \boxed{f(2k,2k-1)=\frac{2k+1}{6}\qquad(k\geq1).} \]

Solution

Integer translations and reflections in coordinate lines preserve the coloring or interchange the two colors. Thus they preserve the absolute area difference. We may therefore take our triangle to be \[ T_{m,n}=\left\{(x,y):x,y\geq0,\ \frac{x}{m}+\frac{y}{n}\leq1\right\}, \] and assume that the unit square \[ Q_{i,j}=[i,i+1]\times[j,j+1] \] is black precisely when \(i+j\) is even.

For any region \(A\), write \(D(A)\) for its black area minus its white area. This quantity is additive over regions with disjoint interiors, and \(f(m,n)=|D(T_{m,n})|\).

(a) Consider the rectangle \(R=[0,m]\times[0,n]\). The half-turn \[ (x,y)\longmapsto(m-x,n-y) \] interchanges its two triangles separated by the hypotenuse of \(T_{m,n}\). It sends \(Q_{i,j}\) to \(Q_{m-1-i,n-1-j}\), preserving its color whenever \(m+n\) is even.

Consequently, when \(m,n\) have the same parity, the two triangles have equal signed area differences, so \[ 2D(T_{m,n})=D(R). \] If both dimensions are even, the rectangle contains equal numbers of black and white squares, giving \(D(R)=0\). If both are odd, it contains one more black square than white square, giving \(D(R)=1\). Hence \[ f(m,n)=0\quad\text{or}\quad\frac12, \] respectively.

(b) Part (a) already proves the bound when \(m,n\) have the same parity. Otherwise, interchange the coordinates if necessary so that \(m\) is even.

Divide \(T_{m,n}\) into its intersections with the \(m\) vertical strips \[ i\leq x\leq i+1,\qquad i=0,\ldots,m-1. \] On a vertical line inside strip \(i\), the triangle occupies a segment starting at \(y=0\). Along this segment, the colors alternate in unit lengths.

Pair consecutive unit lengths starting from the bottom. Each complete pair has equal black and white lengths. In the remaining segment, whose length is between \(0\) and \(2\), the excess of the bottom color is between \(0\) and \(1\): it increases from \(0\) to \(1\) through the first unit, then decreases to \(0\) through the second.

Thus, by taking areas of these vertical slices, the signed area difference \(d_i\) in strip \(i\) satisfies \[ 0\leq d_i\leq1\quad(i\text{ even}),\qquad -1\leq d_i\leq0\quad(i\text{ odd}). \] There are \(m/2\) strips of each kind. Therefore \[ -\frac m2\leq D(T_{m,n})=\sum_{i=0}^{m-1}d_i\leq\frac m2, \] and hence \[ f(m,n)\leq\frac m2\leq\frac12\max\{m,n\}. \]

(c) Let \(m\geq2\) be even. We calculate \(f(m,m-1)\).

The isosceles triangle \[ H=T_{m,m} \] has \(D(H)=0\) by part (a). Removing \(T_{m,m-1}\) from \(H\) leaves the triangle \(W\) with vertices \[ (0,m-1),\quad(0,m),\quad(m,0). \] Its area is \(m/2\).

Every point of \(W\) satisfies \[ m-1\leq x+y\leq m. \] Consequently, apart from boundaries, the only unit squares meeting \(W\) have index sum \(m-2\) or \(m-1\). Since \(m\) is even, its black portions lie precisely in the squares \[ Q_{i,m-2-i},\qquad i=0,\ldots,m-2. \]

The lower boundary of \(W\) is \[ y=(m-1)\left(1-\frac{x}{m}\right). \] In \(Q_{i,m-2-i}\), the portion above this line is a right triangle at the square’s top-right corner. Intersecting the line with the top and right sides gives its horizontal and vertical leg lengths as \[ \frac{m-1-i}{m-1} \qquad\text{and}\qquad \frac{m-1-i}{m}, \] respectively. Thus the total black area \(B\) of \(W\) is \[ \begin{aligned} B &=\sum_{i=0}^{m-2}\frac{(m-1-i)^2}{2m(m-1)}\\ &=\frac{1}{2m(m-1)}\sum_{r=1}^{m-1}r^2\\ &=\frac{1}{2m(m-1)} \frac{(m-1)m(2m-1)}6 =\frac{2m-1}{12}. \end{aligned} \] Therefore \[ D(W)=2B-\operatorname{area}(W) =\frac{2m-1}{6}-\frac m2 =-\frac{m+1}{6}. \] Since \(D(H)=D(T_{m,m-1})+D(W)=0\), we obtain \[ f(m,m-1)=\frac{m+1}{6}. \] Taking \(m=2k\) and letting \(k\) tend to infinity proves that no constant \(C\) can bound all values of \(f(m,n)\).

The solution was checked against Evan Chen's published IMO solution notes.