IMO 1997 problem 1

336 Views Asked by At

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) \leqslant \frac {1} {2} \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$.

1

There are 1 best solutions below

3
On

Warning: This answer appears to contain serious errors (see comment).


Starting from one of such points on the plane draw a rectangle whose sides are $m$ and $n$. Let $R_1$ be the total area of black squares and $R_2$ be that of white squares, in the rectangle. Since by drawing a diagonal we can divide the rectangle into two identical right-angled triangles as described, we have $R_1 = 2S_1$ and $R_2 = 2S_2$. Then, $|R_1 - R_2| = 2 f (m, n)$.

(a) Let both $m$ and $n$ be even: $m = 2M$ and $n = 2N$. Then $R_1 = R_2 = 2NM$, so $f (m, n) = 0$.

Suppose now both $m$ and $n$ are odd: $m = 2M + 1$ and $n = 2N + 1$. Then the larger of $R_1$ and $R_2$ is $(N + 1) (M + 1) + NM$ and the smaller is $N (M + 1) + M (N + 1)$. So $$|R_1 - R_2| = |(N + 1) (M + 1) + NM - N (M + 1) - M (N + 1)| = 1,$$ whence $f (m, n) = \frac {1} {2}$.

(b) For $m$ and $n$ both even or both odd the inequality holds. Now consider the case one of $m$ and $n$ is even and the other is odd. In this case, $R_1 = (N + 1) M + (M + 1) N$ and $R_2 = 2NM$ or vice versa. Therefore, $$|R_1 - R_2| = M + N = \frac {1} {2} (n + m - 1) \leqslant \max \{m ,n\}$$ since $\min \{m, n\} \leqslant \frac {1} {2} (m + n) \leqslant \max \{m, n\}$. Now since $f (m, n) = \frac {1} {2} |R_1 - R_2|$ we have $$f (m, n) \leqslant \frac {1} {2} \max \{m, n\}.$$

(c) Since for many $m$ and $n$ we have $f (m, n) = \frac {1} {4} (m + n - 1)$, it is clear that $f (m, n)$ grows without bound. So the proof is complete.

"Notes on Olympiad Problems", Nima Bavari, Tehran, 2006.