Problem: We define a \emph{chessboard polygon} to be a simple polygon whose sides are
situated along lines of the form $x=a$ or $y=b$, where $a$ and $b$ are integers.
These lines divide the interior into unit squares, which are shaded alternately
gray and white so that adjacent squares have different colors.
To tile a chessboard polygon by dominoes is to
exactly cover the polygon by non-overlapping $ 1 \times 2$ rectangles.
Finally, a \emph{tasteful tiling} is one which avoids the
two configurations of dominoes and colors shown on the left below.
Two tilings of a $3 \times 4$ rectangle are shown;
the first one is tasteful, while the second is not,
due to the vertical dominoes in the upper right corner.

\begin{center}
\begin{asy}
size(300);
pen rt = linewidth(2.5) + rgb(0.6,0.2,0.2);
void chessboard(int a, int b, int eps, pair P) {
  for(int i = 0; i < a; ++i) {
  for(int j = 0; j < b; ++j) {
    if((i+j+eps)#2 == (i+j+eps)/2)
    fill(shift(P.x+i,P.y+j)*unitsquare,rgb(0.6,0.6,0.6));
  }
  }
  draw(P--P+(a,0)--P+(a,b)--P+(0,b)--cycle, rt);
}

chessboard(2,2,0,(0,0));
chessboard(2,2,1,(2.5,0));
chessboard(4,3,1,(6,0));
chessboard(4,3,1,(11,0));
label("Distasteful tilings",(2.25,2.5),fontsize(10));

/* draw lines */
draw((1,0)--(1,2), rt);
draw((2.5,1)--(4.5,1), rt);
draw((7,0)--(7,2)--(6,2)--(10,2)--(9,2)--(9,0)--(9,1)--(7,1), rt);
draw((8,2)--(8,3), rt);
draw((12,0)--(12,2)--(11,2)--(13,2), rt);
draw((13,1)--(15,1)--(14,1)--(14,3), rt);
draw((13,0)--(13,3), rt);
\end{asy}
\end{center}

Prove that (a) if a chessboard polygon can be tiled by dominoes,
then it can be done so tastefully, and (b) such a tasteful tiling is unique.

Solution: \paragraph{Proof of (a).} This is easier, and by induction.
Let $\mathcal P$ denote the chessboard polygon which can be tiled by dominoes.

Consider a \emph{lower-left} square $s$ of the polygon,
and WLOG is it white (other case similar).
Then we have two cases:
\begin{itemize}
  \ii If there exists a domino tiling of $\mathcal P$
  where $s$ is covered by a vertical domino,
  then delete this domino and apply induction on the rest of $\mathcal P$.
  This additional domino will not cause any distasteful tilings.

  \ii Otherwise, assume $s$ is covered by a horizontal domino
  in \emph{every} tiling.
  Again delete this domino and apply induction on the rest of $\mathcal P$.
  The resulting tasteful tiling should not have another horizontal domino
  adjacent to the one covering $s$, because otherwise
  we could have replaced that $2 \times 2$ square
  with two vertical dominoes to arrive in the first case.
  So this additional domino will not cause any distasteful tilings.
\end{itemize}

\begin{remark*}
  The second case can actually arise, for example in the following picture.
  \begin{center}
  \begin{asy}
    unitsize(0.6cm);
    fill(shift(1,0)*unitsquare,rgb(0.6,0.6,0.6));
    fill(shift(0,1)*unitsquare,rgb(0.6,0.6,0.6));
    fill(shift(2,1)*unitsquare,rgb(0.6,0.6,0.6));
    draw( (0,0)--(0,3)--(1,3)--(1,2)--(3,2)--(3,1)--(2,1)--(2,0)--cycle,
      linewidth(2.5) + rgb(0.6,0.2,0.2));
  \end{asy}
  \end{center}
  Thus one cannot just try to cover $s$ with a vertical
  domino and claim the rest of $\mathcal P$ is tile-able.
  So the induction is not as easy as one might hope.

  One can phrase the solution algorithmically too,
  in the following way: any time we see a distasteful tiling,
  we rotate it to avoid the bad pattern.
  The bottom-left corner eventually becomes stable,
  and an induction shows the termination of the algorithm.
\end{remark*}

\paragraph{Proof of (b).} We now turn to proving uniqueness.
Suppose for contradiction there are two distinct tasteful tilings.
Overlaying the two tilings on top of each other induces
several \emph{cycles} of overlapping dominoes at positions where the tilings differ.

Henceforth, it will be convenient to work with the lattice $\ZZ^2$,
treating the squares as black/white points, and we do so.
Let $\gamma$ be any such cycle and let $s$ denote a
lower left point, and again WLOG it is black.
Orient $\gamma$ counterclockwise henceforth.
Restrict attention to the lattice polygon $\mathcal Q$ enclosed by $\gamma$
(we consider points of $\gamma$ as part of $\mathcal Q$).

In one of the two tilings of (lattice points of) $\mathcal Q$,
the point $s$ will be covered by a horizontal domino;
in the other tiling $s$ will be covered by a vertical domino.
From now on we will focus only on the latter one.
Observe that we now have a set of dominoes along $\gamma$,
such that $\gamma$ points from the white point to the black point
within each domino.

Now impose coordinates so that $s = (0,0)$.
Consider the stair-case sequence of points
$p_0 = s = (0,0)$, $p_1 = (1,0)$, $p_2 = (1,1)$, $p_3 = (2,1)$, and so on.
By hypothesis, $p_0$ is covered by a vertical domino.
Then $p_1$ must be covered by a horizontal domino, to avoid a distasteful tiling.
Then if $p_2$ is in $\mathcal Q$, then it must be covered by a vertical domino
to avoid a distasteful tiling, and so on.
We may repeat this argument as long the points $p_i$ lie inside $\mathcal Q$.
(See figure below; the staircase sequence is highlighted by red halos.)
\begin{center}
\begin{asy}
  unitsize(1.5cm);

  margin m = Margin(3,3);
  arrowbar ar = EndArrow(TeXHead);
  pen gamma = blue + 1;
  draw( (0,0)--(1,0), gamma, ar, m);
  draw( (1,0)--(2,0), gamma, ar, m);
  draw( (2,0)--(3,0), gamma, ar, m);
  draw( (3,0)--(3,-1), gamma, ar, m);
  draw( (3,-1)--(4,-1), gamma, ar, m);
  draw( (4,-1)--(4,0), gamma, ar, m);
  draw( (4,0)--(4,1), gamma, ar, m);
  draw( (4,1)--(4,2), gamma, ar, m);
  draw( (4,2)--(3,2), gamma, ar, m);
  draw( (3,2)--(3,3), gamma, ar, m);
  draw( (3,3)--(4,3), gamma, ar, m);
  draw( (4,3)--(4,4), gamma, ar, m);
  draw( (4,4)--(3,4), gamma, ar, m);
  draw( (3,4)--(2,4), gamma, ar, m);
  draw( (2,4)--(1,4), gamma, ar, m);
  draw( (1,4)--(1,3), gamma, ar, m);
  draw( (1,3)--(0,3), gamma, ar, m);
  draw( (0,3)--(0,2), gamma, ar, m);
  draw( (0,2)--(0,1), gamma, ar, m);
  draw( (0,1)--(0,0), gamma, ar, m);

  fill( (0,0)--(3,0)--(3,-1)--(4,-1)--(4,2)--(3,2)
    --(3,3)--(4,3)--(4,4)--(1,4)--(1,3)--(0,3)--cycle,
    opacity(0.1) + lightcyan);
  label("$s$", (0,0), 1.5*dir(225));
  label("$a$", (3,2), 2*dir(45), red);
  label("$b$", (1,0), 2*dir(225), red);
  draw( (3,2)--(1,0), lightred);

  real r = 0.07;
  filldraw(CR( (3,-1), r), gray, black);
  filldraw(CR( (0,0), r), gray, black);
  filldraw(CR( (2,0), r), gray, black);
  filldraw(CR( (4,0), r), gray, black);
  filldraw(CR( (1,1), r), gray, black);
  filldraw(CR( (3,1), r), gray, black);
  filldraw(CR( (0,2), r), gray, black);
  filldraw(CR( (2,2), r), gray, black);
  filldraw(CR( (4,2), r), gray, black);
  filldraw(CR( (1,3), r), gray, black);
  filldraw(CR( (3,3), r), gray, black);
  filldraw(CR( (2,4), r), gray, black);
  filldraw(CR( (4,4), r), gray, black);

  filldraw(CR( (4,-1), r), white, black);
  filldraw(CR( (1,0), r), white, black);
  filldraw(CR( (3,0), r), white, black);
  filldraw(CR( (0,1), r), white, black);
  filldraw(CR( (2,1), r), white, black);
  filldraw(CR( (4,1), r), white, black);
  filldraw(CR( (1,2), r), white, black);
  filldraw(CR( (3,2), r), white, black);
  filldraw(CR( (0,3), r), white, black);
  filldraw(CR( (2,3), r), white, black);
  filldraw(CR( (4,3), r), white, black);
  filldraw(CR( (1,4), r), white, black);
  filldraw(CR( (3,4), r), white, black);

  real s = 3*r;
  fill(CR( (0,0), s), opacity(0.2)+lightred );
  fill(CR( (1,0), s), opacity(0.2)+lightred );
  fill(CR( (1,1), s), opacity(0.2)+lightred );
  fill(CR( (2,1), s), opacity(0.2)+lightred );
  fill(CR( (2,2), s), opacity(0.2)+lightred );
  fill(CR( (3,2), s), opacity(0.2)+lightred );

  pen domino = heavygreen+1.2;
  path vd = box( (-0.4, -0.4), (0.4, 1.4) );
  path hd = rotate(-90)*vd;
  draw(shift(0,0)*vd, domino);
  draw(shift(1,1)*vd, domino);
  draw(shift(2,2)*vd, domino);
  draw(shift(1,0)*hd, domino);
  draw(shift(2,1)*hd, domino);
  draw(shift(3,2)*hd, domino);
\end{asy}
\end{center}

The curve $\gamma$ by definition should cross $y=x-1$ at the point $b = (1,0)$.
Let $a$ denote the first point of this sequence
after $p_1$ for which $\gamma$ \emph{crosses} $y=x-1$ again.

Now $a$ is tiled by a vertical domino whose black point is to the right of $\ell$.
But the line segment $\ell$ cuts $\mathcal Q$ into two parts,
and the orientation of $\gamma$ has this path also entering from the right.
This contradicts the fact that the orientation of $\gamma$
points only from white to black within dominoes.
This contradiction completes the proof.

\begin{remark*}
  Note the problem is false if you allow holes
  (consider a $3 \times 3$ with the middle square deleted).
\end{remark*}