\documentclass[11pt]{scrartcl}
\usepackage{evan}

\begin{document}
\title{USAMO 1998/4}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 41}
\maketitle

\section*{Problem}
A computer screen shows a $98 \times 98$ chessboard, colored in the usual way.
One can select with a mouse any rectangle with sides on the lines
of the chessboard and click the mouse button:
as a result, the colors in the selected rectangle switch
(black becomes white, white becomes black).
Find, with proof, the minimum number of mouse clicks
needed to make the chessboard all one color.

\section*{Video}
\href{https://www.youtube.com/watch?v=0_e8MuvtsJo&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/0\_e8MuvtsJo}}

\section*{External Link}
\url{https://aops.com/community/p343869}

\newpage

\section*{Solution}
The answer is $98$.
One of several possible constructions is to toggle
all columns and rows with even indices.

In the other direction, let $n = 98$ and
suppose that $k$ rectangles are used,
none of which are $n \times n$ (else we may delete it).
Then, for any two orthogonally adjacent cells,
the edge between them must be contained in the edge of
one of the $k$ rectangles.

We define a \emph{gridline} to be a line segment
that runs in the interior of the board from
one side of the board to the other.
Hence there are $2n-2$ gridlines exactly.
Moreover, we can classify these rectangles into two types:
\begin{itemize}
  \ii \emph{Full length rectangles}:
  these span from one edge of the board to the other.
  The two long sides completely cover two gridlines,
  but the other two sides of the rectangle do not.
  \ii \emph{Partial length rectangles}:
  each of four sides can partially cover ``half a'' gridline.
\end{itemize}
See illustration below for $n = 6$.
\begin{center}
\begin{asy}
  unitsize(0.5cm);
  picture base;
  for (int i=1; i<=5; ++i) {
    draw(base, (0,i)--(6,i), black );
    draw(base, (i,0)--(i,6), black );
  }

  picture full;
  picture partial;

  add(full, base);
  add(partial, base);
  label(full, "Full length", (3,0), dir(-90), red);
  label(partial, "Partial length", (3,0), dir(-90), blue);

  filldraw(full, box( (0,3), (6,1) ), lightred+opacity(0.3), red+1.4 );
  filldraw(partial, box( (2,2), (4,5) ), lightcyan+opacity(0.3), blue+1.4 );
  add(shift(0,0)*base);
  add(shift(7,0)*full);
  add(shift(14,0)*partial);
\end{asy}
\end{center}
Since there are $2n-2$ gridlines;
and each rectangle can cover at most two gridlines in total
(where partial-length rectangles are ``worth $\half$''
on each of the four sides),
we immediately get the bound $2k \ge 2n-2$, or $k \ge n-1$.

To finish, we prove that:
\begin{claim*}
  If equality holds and $k = n-1$, then $n$ is odd.
\end{claim*}
\begin{proof}
  If equality holds, then look at the horizontal gridlines
  and say two gridlines are \emph{related} if some rectangle
  has horizontal edges along both gridlines.
  (Hence, the graph has degree either $1$ or $2$ at each vertex,
  for equality to hold.)
  The reader may verify the resulting graph consists only of
  even length cycles and single edges,
  which would mean $n-1$ is even.
\end{proof}
Hence for $n = 98$ the answer is indeed $98$ as claimed.

\end{document}
