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

\begin{document}
\title{Singapore 2019/5}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 24}
\maketitle

\section*{Problem}
In a $m\times n$ chessboard ($m,n\ge 2$),
some dominoes are placed (without overlap)
with each domino covering exactly two adjacent cells.
Show that if no more dominoes can be added to the grid,
then at least $2/3$ of the chessboard is covered by dominoes.

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

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

\newpage

\section*{Solution}
Assume that some dominoes are placed so that
no more dominoes can be added to the grid.
We assume $\min(m,n) \ge 3$ for convenience;
the case $m=1$ is straightforward,
and the case where $m=2$ can be dealt with by hand.

From every unoccupied cell not on the border of the board,
we emit four lasers from the center of the cell
one in each of the four directions;
these must each hit the edge of a domino immediately.
Cells on the border emit two or three lasers only,
according to whether or not they are on the corner.
\begin{center}
\begin{asy}
size(7cm);
for (int i=1; i<6; ++i) {
  draw((0,i)--(6,i), grey);
  draw((i,0)--(i,6), grey);
}
draw(box((0,0),(6,6)), black);

path vdomino = box((0.1,0.1), (0.9,1.9));
filldraw(shift(0,1)*vdomino, lightcyan, blue);
filldraw(shift(0,4)*vdomino, lightcyan, blue);
filldraw(shift(1,0)*vdomino, lightcyan, blue);
filldraw(shift(1,3)*vdomino, lightcyan, blue);
filldraw(shift(2,1)*vdomino, lightcyan, blue);
filldraw(shift(2,4)*vdomino, lightcyan, blue);
filldraw(shift(3,0)*vdomino, lightcyan, blue);
filldraw(shift(3,3)*vdomino, lightcyan, blue);
filldraw(shift(4,1)*vdomino, lightcyan, blue);
filldraw(shift(4,4)*vdomino, lightcyan, blue);
filldraw(shift(5,0)*vdomino, lightcyan, blue);
filldraw(shift(5,3)*vdomino, lightcyan, blue);

void draw_laser(pair O, real r) {
  dot(O+(0.5,0.5), red);
  draw((O+(0.5,0.5))--(O+(0.5,0.5)+0.55*dir(r)), red, EndArrow);
}

draw_laser((0,0), 0);
draw_laser((0,0), 90);
draw_laser((0,3), 0);
draw_laser((0,3), 90);
draw_laser((0,3), 270);

draw_laser((2,0), 0);
draw_laser((2,0), 90);
draw_laser((2,0), 180);
draw_laser((2,3), 0);
draw_laser((2,3), 90);
draw_laser((2,3), 180);
draw_laser((2,3), 270);

draw_laser((4,0), 0);
draw_laser((4,0), 90);
draw_laser((4,0), 180);
draw_laser((4,3), 0);
draw_laser((4,3), 90);
draw_laser((4,3), 180);
draw_laser((4,3), 270);

draw_laser((1,2), 0);
draw_laser((1,2), 90);
draw_laser((1,2), 180);
draw_laser((1,2), 270);
draw_laser((1,5), 0);
draw_laser((1,5), 180);
draw_laser((1,5), 270);

draw_laser((3,2), 0);
draw_laser((3,2), 90);
draw_laser((3,2), 180);
draw_laser((3,2), 270);
draw_laser((3,5), 0);
draw_laser((3,5), 180);
draw_laser((3,5), 270);

draw_laser((5,2), 90);
draw_laser((5,2), 180);
draw_laser((5,2), 270);
draw_laser((5,5), 180);
draw_laser((5,5), 270);
\end{asy}
\end{center}


\begin{claim*}
  Every domino in the grid is hit by at most four lasers;
  this bound improves to three if the domino is on the border of the grid.
\end{claim*}
\begin{proof}
  Each edge of the domino is hit by at most one laser.
\end{proof}

\begin{claim*}
  [Laser double counting]
  The number of dominoes is at least $\frac{mn-1}{3}$.

  Moreover, for equality to occur,
  all four corners must be vacant,
  and the short end of every domino must either touch
  the edge of the grid or an adjacent square.
\end{claim*}
\begin{proof}
  We make the additional observation
  that the number of dominoes on the border is at least
  the number of vacant squares on the border.
  Indeed, if one travels around the perimeter of the border,
  between any two vacant squares there is some domino present.

  Let $D$ be the number of dominoes, so $mn-2D$ is the number of
  vacant squares.
  Let $Y$ be the number of dominoes which touch the border,
  and $X$ the number of vacant cells on the border, so that $X \le Y$.
  Finally, let $0 \le e \le 4$ be the number of vacant corners.

  By double counting the lasers, we now have
  \[ 4(mn-2D) - X - e \le 4D - Y. \]
  Since $X \le Y$ and $e \le 4$,
  we recover $3D \ge mn-1$ as claimed,
  with equality if $X=Y$, $e=4$, and every edge
  of every domino is either on the border or touched by a laser.
\end{proof}

\begin{claim*}
  We can't have $3D = mn-1$ exactly.
\end{claim*}
\begin{proof}
  We take the standing assumptions from the previous claim
  that all four corners are empty and every edge
  of every domino is hit by a laser unless it's at the edge of board.

  Consider the northwest vacant cell $A$;
  it is border by two different dominoes.
  We consider two different possibilities illustrated below
  for the layout of the two dominoes touching $A$.
  \begin{center}
  \begin{asy}
  picture case1;
  picture case2;

  path vdomino = box((0.1,0.1), (0.9,1.9));
  size(10cm);

  // common parts
  for (int i=1; i<6; ++i) {
    draw(case1, (0,i)--(6,i), grey);
    draw(case1, (i,0)--(i,6), grey);
  }
  draw(case1, (0,0)--(0,6)--(6,6), black);
  label(case1, "$A$", (0.5,5.5), red);
  filldraw(case1, shift(0,3)*vdomino, lightcyan, blue);
  case2 = rotate(0)*case1;

  // first case
  filldraw(case1, shift(1,4)*vdomino, lightcyan, blue);
  label(case1, "$1$", (2.5,5.5), red);
  label(case1, "$2$", (1.5,3.5), red);
  label(case1, "$3$", (0.5,2.5), red);
  label(case1, "$4$", (2.5,2.5), red);
  filldraw(case1, shift(2,3)*vdomino, palegreen, deepgreen+dashed);
  filldraw(case1, shift(1,1)*vdomino, palegreen, deepgreen+dashed);

  // second case
  filldraw(case2, shift(1,5)*reflect( (0,0), (1,1) )*vdomino, lightcyan, blue);
  label(case2, "$5$", (1.5,4.5), red);
  filldraw(case2, shift(1,2)*vdomino, palegreen, deepgreen+dashed);
  filldraw(case2, shift(2,4)*reflect( (0,0), (1,1) )*vdomino, palegreen, deepgreen+dashed);
  label(case2, "$6$", (2.5,3.5), red);

  label(case1, "First case", (3,0), dir(-90));
  label(case2, "Second case", (3,0), dir(-90));

  add(shift(-8,0)*case1);
  add(shift(0,0)*case2);
  \end{asy}
  \end{center}

  In first case, the dominoes point the same way, say vertically.
  Consider the cell marked $1$; it must be vacant
  (since either a horizontal or vertical domino would
  violate the equality case condition).
  The cell immediately below $1$ must be occupied,
  and again we see the domino should be vertical.
  This means the cells marked $2$, $3$, $4$ indicated must be vacant,
  and we get a vertical domino touching all three.
  This then lets us repeat the process to find that all dominoes
  in the first three columns are vertical.
  We can then extend the process to the right as well;
  eventually, we find all dominoes are vertical.
  But then $D > mn/3$ can clearly not hold.

  The second case is easier:
  the cell marked $5$ must be vacant,
  and we must have the two dominoes shown
  since the short ends of these dominoes cannot touch the blue ones.
  Then the cells marked $6$ is vacant,
  and we can repeat this argument.
  Eventually though we reach the edge of the board and a
  contradiction takes place.
\end{proof}

\end{document}
