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

\begin{document}
\title{Croatia TST 2016/2/2}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 22}
\maketitle

\section*{Problem}
Let $n>1$ be an integer.
We have an $n \times n$ board with two diagonally opposite corner cells
colored in black; the rest is colored white.
A legal move consists of picking row or column
and inverting the colour of cells which are in that row/column.
What is the least additional number of cells that we need to colour black
so that we can eventually turn all cells black?

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

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

\newpage

\section*{Solution}
The answer is $2n-4$ additional cells.

We'll do the usual reduction:
all the moves commute with each other and doing
the same move twice does nothing.
Also, it'll be more natural to get all-white to the ``starting'' state;
we'll do so as they are equivalent anyways.

Thus, we may as well assume (by permuting rows/columns)
\begin{itemize}
  \ii we operated on the first $a$ rows;
  \ii we operated on the first $b$ columns.
\end{itemize}
The given hypothesis is equivalent to saying
that if we do this operation on an initially empty board,
then we got $k$ black cells,
and at least two of them are not in the same row or column.
The problem asks for the smallest possible value of $k-2$.

However, the point is that we have the explicit value
\[ k = a(n-b) + b(n-a). \]
It will be more economical actually to write
\[ n^2 - k = ab + (n-a)(n-b)
  \le \sqrt{ \left( a^2+(n-a)^2 \right)
  \left( b^2+(n-b)^2 \right)}. \]
We now analyze two cases:
\begin{itemize}
  \ii If any of $a$ or $b$ are $0$ or $n$,
  we may directly check we need $k \ge 2n$
  in order to have two black cells not in the same row or column.

  \ii Otherwise, $x^2 + (n-x)^2 \le 1 + (n-1)^2$
  for $1 \le x \le n-1$, so
  \[ n^2 - k \le 1^2 + (n-1)^2 \]
  which means $k \ge 2n-2$.
\end{itemize}
In conclusion, $k-2 \ge 2n-4$;
and moreover equality occurs at $a=b=1$,
which is checked to indeed work.

\end{document}
