Problem: Let $a$ and $b$ be positive integers.
Every cell of an $(a+b+1)\times (a+b+1)$ grid is colored either amber or bronze
such that there are at least $a^2+ab-b$ amber cells
and at least $b^2+ab-a$ bronze cells.
Prove that it is possible to choose $a$ amber cells and $b$ bronze cells
such that no two of the $a+b$ chosen cells lie in the same row or column.

Solution: \begin{claim*}
  There exists a transversal $T_a$ with at least $a$ amber cells.
  Analogously, there exists a transversal $T_b$ with at least $b$ bronze cells.
\end{claim*}
\begin{proof}
  If one picks a random transversal, the expected value
  of the number of amber cells is at least
  \[ \frac{a^2+ab-b}{a+b+1} = (a-1) + \frac{1}{a+b+1} > a-1. \qedhere \]
\end{proof}

Now imagine we transform $T_a$ to $T_b$ in some number of steps,
by repeatedly choosing cells $c$ and $c'$ and swapping them
with the two other corners of the rectangle formed by their row/column,
as shown in the figure.
\begin{center}
\begin{asy}
  filldraw(shift(0,0)*unitsquare, lightcyan, blue);
  filldraw(shift(3,2)*unitsquare, lightcyan, blue);
  draw(shift(3,0)*unitsquare, dotted+blue);
  draw(shift(0,2)*unitsquare, dotted+blue);
  label("$c$", (0.5,0.5));
  label("$c'$", (3.5,2.5));

  label(scale(2.5)*"$\implies$", (5.5, 1.5));
  filldraw(shift(7,2)*unitsquare, lightcyan, blue);
  filldraw(shift(10,0)*unitsquare, lightcyan, blue);
  draw(shift(7,0)*unitsquare, dotted+blue);
  draw(shift(10,2)*unitsquare, dotted+blue);
\end{asy}
\end{center}
By ``discrete intermediate value theorem'',
the number of amber cells will be either $a$ or $a+1$
at some point during this transformation.
This completes the proof.