\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{IMO 1997/1}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 116}
\maketitle
\section*{Problem}
In the plane there is an infinite chessboard.
For any pair of positive integers $m$ and $n$,
consider a right-angled triangle with vertices at lattice points
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 |$.
\begin{enumerate}[(a)]
\ii Calculate $f(m,n)$ for all positive integers $m$ and $n$
which are either both even or both odd.
\ii Prove that $f(m,n) \leq \frac 12 \max \{m,n\}$ for all $m$ and $n$.
\ii Show that there is no constant $C$
such that $f(m,n) < C$ for all $ m$ and $ n$.
\end{enumerate}
\section*{Video}
\href{https://www.youtube.com/watch?v=zOToam5MzlM&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/zOToam5MzlM}}
\section*{External Link}
\url{https://aops.com/community/p356696}
\newpage
\section*{Solution}
In general, we say the \emph{discrepancy} of a region in the plane
equals its black area minus its white area.
We allow negative discrepancies,
so discrepancy is additive and $f(m,n)$ equals the absolute value
of the discrepancy of a right triangle with legs $m$ and $n$.
For (a), the answers are $0$ and $1/2$ respectively.
To see this, consider the figure shown below.
\begin{center}
\begin{asy}
size(8cm);
pair A = (0,5);
pair B = (9,0);
pair M = midpoint(A--B);
for (int i=0; i<=5; ++i) {
draw( (0,i)--(9,i), grey );
}
for (int j=0; j<=9; ++j) {
draw( (j,0)--(j,5), grey );
}
dot("$M$", M, dir(50));
dot("$A$", A, dir(90));
dot("$B$", B, dir(0));
dot("$C$", (0,0), dir(180));
filldraw(A--B--(0,0)--cycle, opacity(0.1)+yellow, black+1.5);
pair P = (0,2.5);
pair Q = (9,2.5);
dot("$P$", P, dir(180));
dot("$Q$", Q, dir(0));
draw(P--Q--B, blue+1.5);
\end{asy}
\end{center}
Notice that triangles $APM$ and $BQM$ are congruent,
and when $m \equiv n \pmod 2$, their colorings actually coincide.
Consequently, the discrepancy of the triangle
is exactly equal to the discrepancy of $CPQB$, which is an $m \times n/2$
rectangle and hence equal to $0$ or $1/2$ according to parity.
For (b), note that a triangle with legs $m$ and $n$, with $m$ even and $n$ odd,
can be dissected into one right triangle with legs $m$ and $n-1$
plus a thin triangle of area $1/2$ which has height $m$ and base $1$.
The former region has discrepancy $0$ by (a),
and the latter region obviously has discrepancy at most its area of $m/2$,
hence $f(m,n) \le m/2$ as needed.
(An alternative slower approach, which requires a few cases,
is to prove that two adjacent columns have at most discrepancy $1/2$.)
For (c), we prove:
\begin{claim*}
For each $k \ge 1$, we have
\[ f(2k, 2k+1) = \frac{2k-1}{6}. \]
\end{claim*}
\begin{proof}
An illustration for $k=2$ is shown below,
where we use $(0,0)$, $(0,2k)$, $(2k+1,0)$ as the three vertices.
\begin{center}
\begin{asy}
size(8cm);
fill( (0,4)--(5,0)--(5,4)--cycle, palered );
draw(box( (0,0), (5,4) ), black);
fill( (0,3)--(1,3)--(1,3.2)--(0,4)--cycle, grey);
fill( (1,2)--(2,2)--(2,2.4)--(1.25,3)--(1,3)--cycle, grey);
fill( (2,1)--(3,1)--(3,1.6)--(2.50,2)--(2,2)--cycle, grey);
fill( (3,0)--(4,0)--(4,0.8)--(3.75,1)--(3,1)--cycle, grey);
fill(shift(1,0)*unitsquare, grey);
fill(shift(0,1)*unitsquare, grey);
for (int i=1; i<4; ++i) {
draw( (0,i)--(5,i), grey );
}
for (int i=1; i<5; ++i) {
draw( (i,0)--(i,4), grey );
}
draw( (0,4)--(5,0)--(0,0)--cycle, blue+2 );
\end{asy}
\end{center}
WLOG, the upper-left square is black, as above.
The $2k$ small white triangles just below the diagonal have area sum
\[ \frac12 \cdot \frac{1}{2k+1} \cdot \frac{1}{2k}
\left[ 1^2 + 2^2 + \dots + (2k)^2 \right] = \frac{4k+1}{12} \]
The area of the $2k$ black polygons sums just below the diagonal to
\[ \sum_{i=1}^{2k} \left( 1
- \frac12 \cdot \frac{1}{2k+1} \cdot \frac{1}{2k} \cdot i^2 \right)
= 2k - \frac{4k+1}{12} = \frac{20k-1}{12}. \]
Finally, in the remaining $1+2+\dots+2k$ squares,
there are $k$ more white squares than black squares.
So, it follows
\[ f(2k, 2k+1)
= \left\lvert -k + \frac{20k-1}{12} - \frac{4k+1}{12} \right\rvert
= \frac{2k-1}{6}. \]
\end{proof}
\end{document}