\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 $n \times n$ board with two diagonally
opposite corner cells coloured in black,
the rest is coloured 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}}
\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}