\documentclass[12pt]{article}
\usepackage[Mickael]{ammaths}
\begin{document}
\module{Covering a chessboard with dominoes}{02}{12}{2 periods}
%\prereq{}
\object{\begin{itemize}
\item Work on some covering (tiling) problems.
\end{itemize}}
\mater{\begin{itemize}
\item Problem lists.
\item Solutions.
\item Chessboards and dominoes (one for each pair of students).
\item Beamer with the solutions.
\end{itemize}}
\modpart{Seven problems}{75 mins}
Students work by pairs. Each pair of students has to solve seven problems and tell the answer to the teacher. They get
3 points for every problem solved.
\modpart{The solutions}{Remaining time}
The solutions are shown with a beamer and then handed out to the students. Pairs of students can be chosen randomly to
comment on the solutions.
\newcounter{prob}
\newcommand{\prob}{\stepcounter{prob}\arabic{prob}}
\pagebreak
\moddocdis{Covering a chessboard with dominoes}{02}{12}{Problems}
\vspace*{-0.5cm}
\subsection*{Problem \prob}
Is it possible to cover a whole chessboard with dominoes ?
\subsection*{Problem \prob}
One corner has been removed from a chessboard. Is it possible to cover the remaining portion of the board
with dominoes so that each domino covers exactly two squares? What if two opposite corners are removed ?
\subsection*{Problem \prob}
Two arbitrary but adjacent squares have been removed from a chessboard. Is it possible to cover the
remaining portion of the board with dominoes?
\subsection*{Problem \prob}
Two arbitrary squares of different colors have been removed from a chessboard. Is it possible to cover the remaining
portion of the board with dominoes?
\subsection*{Problem \prob}
Two arbitrary pairs of squares of different colors have been removed from a chessboard. Is it always possible to cover
the remaining portion of the board with dominoes?
\subsection*{Problem \prob}
Three arbitrary pairs of squares of different colors have been removed from a chessboard, so that the chessboard does
not split into two or more separate pieces. Is it always possible to cover the remaining portion of the board with
dominoes?
\subsection*{Problem \prob}
A domino has two edges, a long edge and a short edge. Two adjacent dominoes must be in one of the only three possible
configurations : long edge to long edge, short edge to short edge and long edge to short edge. In a domino tiling of a
chessboard, what is the minimum number of long-edge to long-edge pairs ?
\subsection*{Problem \prob}
Prove that in any cover of a whole chessboard with dominoes, the number of horizontal
dominoes with a black left square and the number of horizontal dominoes with a white left square are equal.
\pagebreak
\moddocdis{Covering a chessboard with dominoes}{02}{12}{Solutions}
\setcounter{prob}{0}
\subsection*{Problem \prob}
\begin{quote}
Is it possible to cover a whole chessboard with dominoes ?
\end{quote}
A chessboard is made of 64 squares, in eight lines of eight squares. By putting four horizontal dominoes on each line,
we cover the board with 32 dominoes.
\bigskip
\subsection*{Problem \prob}
\begin{quote}
One corner has been removed from a chessboard. Is it possible to cover the remaining portion of the board
with dominoes so that each domino covers exactly two squares? What if two opposite corners are removed ?
\end{quote}
If one corner is removed from the chessboard, then the number of squares is odd. As a domino is made of two squares, it
will then be impossible to cover the amputated board with dominoes so that each domino covers exactly two squares : one
would forcedly have one half outside of the board.
If two opposite corners are removed, the amputated board is made of 62 squares, so the problem stated above doesn't
arise. Now, paint the squares black and white as in a regular chessboard. The opposite corners are the same color, so
the amputated board will be made of, say 30 black squares and 32 white squares. But a domino will always cover a black
square and a white square, so it's impossible to cover the amputated board with dominoes.
\pagebreak
\subsection*{Problem \prob}
\begin{quote}
Two arbitrary but adjacent squares have been removed from a chessboard. Is it possible to cover the
remaining portion of the board with dominoes so that each domino piece covers exactly two squares?
\end{quote}
By studying different positions for the removed squares, it's easy to gets convince that it's always possible. But
this is not a satisfactory way to prove it. So, consider, the basic tiling of the chessboard one gets with 32
horizontal dominoes. Three situations may arise for the two removed squares.
\begin{enumerate}
\item If the two removed squares are under the same tiling domino, then the amputated board is obviously tileable with
dominoes.
\end{enumerate}
\medskip
\begin{minipage}{11.5cm}
\begin{enumerate}\setcounter{enumi}{1}
\item If the two removed squares are on the same row, but under two horizontally adjacent dominoes,
then we just have to place one horizontal domino on the row below or above those two squares (depending on the parity of
the number of the row), one vertical domino on the right and one of the left. We get the configuration shown on the ri
ght or its horizontal mirror image, which fills a $4\times 2$ part of the board, the rest of the horizontal dominoes
being unmoved.
\end{enumerate}
\end{minipage}
\begin{minipage}{5cm}
\begin{center}
\newrgbcolor{qrqrqr}{0 0 0}
\psset{xunit=1.0cm,yunit=1.0cm,algebraic=true,dotstyle=*,dotsize=3pt 0,linewidth=0.8pt,arrowsize=3pt 2,arrowinset=0.25}
\begin{pspicture*}(0.82,2.76)(5.25,5.17)
\pspolygon[linestyle=none,fillstyle=solid,fillcolor=qrqrqr](2,4)(3,4)(3,5)(2,5)
\pspolygon[linestyle=none,fillstyle=solid,fillcolor=qrqrqr](3,4)(4,4)(4,5)(3,5)
\psline[linewidth=2pt,linecolor=qrqrqr](2,4)(3,4)
\psline[linewidth=2pt,linecolor=qrqrqr](3,4)(3,5)
\psline[linewidth=2pt,linecolor=qrqrqr](3,5)(2,5)
\psline[linewidth=2pt,linecolor=qrqrqr](2,5)(2,4)
\psline[linewidth=2pt,linecolor=qrqrqr](3,4)(4,4)
\psline[linewidth=2pt,linecolor=qrqrqr](4,4)(4,5)
\psline[linewidth=2pt,linecolor=qrqrqr](4,5)(3,5)
\psline[linewidth=2pt,linecolor=qrqrqr](3,5)(3,4)
\psline[linewidth=2pt](1,5)(1,3)
\psline[linewidth=2pt](2,3)(1,3)
\psline[linewidth=2pt](2,3)(2,5)
\psline[linewidth=2pt](2,5)(1,5)
\psline[linewidth=2pt](2,3)(4,3)
\psline[linewidth=2pt](4,3)(4,4)
\psline[linewidth=2pt](4,5)(5,5)
\psline[linewidth=2pt](5,5)(5,3)
\psline[linewidth=2pt](5,3)(4,3)
\end{pspicture*}
\end{center}
\end{minipage}
\begin{enumerate}\setcounter{enumi}{1}
\item If the two removed squares are on the same column, under two vertically adjacent dominoes,then we just need to
place a vertical domino over the two other halves of these dominoes.
\end{enumerate}
\bigskip
\subsection*{Problem \prob}
\begin{quote}
Two arbitrary squares of different colors have been removed from a chessboard. Is it possible to cover the remaining
portion of the board with dominoes so that each domino piece covers exactly two squares?
\end{quote}
\medskip
\begin{minipage}{9cm}
It's always possible. To see this, draw two forks as on the diagram. This splits the chessboard into a chain of
alternating squares. The chain can be traversed by starting at any square and covering two squares at a time with a
piece of domino. The two removed squares must be a different color, so there will always be an even number of squares
along the chain between them. Start from one side of one of the removed squares and place dominoes along the chain
until you get to the other one. Do the same forom the other side. Note that this wouldn't be possible if the two
removed squares are the same color, as the chains between them will have an odd number of squares.
\end{minipage}
\begin{minipage}{6.5cm}
\begin{center}
\psset{xunit=0.7cm,yunit=0.7cm,algebraic=true,dotstyle=*,dotsize=3pt 0,linewidth=0.8pt,arrowsize=3pt 2,arrowinset=0.25}
\begin{pspicture*}(1.84,-3.26)(10.24,5.22)
\psline(2,5)(2,-3)
\psline(2,-3)(10,-3)
\psline(10,-3)(10,5)
\psline(10,5)(2,5)
\psline(3,5)(3,-3)
\psline(4,5)(4,-3)
\psline(5,-3)(5,5)
\psline(6,5)(6,-3)
\psline(7,-3)(7,5)
\psline(8,5)(8,-3)
\psline(9,-3)(9,5)
\psline(10,4)(2,4)
\psline(2,3)(10,3)
\psline(2,2)(10,2)
\psline(2,1)(10,1)
\psline(10,0)(2,0)
\psline(2,-1)(10,-1)
\psline(10,-2)(2,-2)
\psline[linewidth=3.2pt](3,-2)(3,4)
\psline[linewidth=3.2pt](3,4)(9,4)
\psline[linewidth=3.2pt](9,4)(9,-2)
\psline[linewidth=3.2pt](7,-2)(7,4)
\psline[linewidth=3.2pt](5,-2)(5,4)
\psline[linewidth=3.2pt](4,3)(4,-3)
\psline[linewidth=3.2pt](4,-3)(8,-3)
\psline[linewidth=3.2pt](8,-3)(8,3)
\psline[linewidth=3.2pt](6,3)(6,-3)
\end{pspicture*}
\end{center}
\end{minipage}
\pagebreak
\subsection*{Problem \prob}
\begin{quote}
Two arbitrary pairs of squares of different colors have been removed from a chessboard. Is it always possible to cover
the remaining portion of the board with dominoes so that each domino piece covers exactly two squares?
\end{quote}
The problem has two different answers if we allow the removed squares to isolate one part of the board or not. If we
allow this, then the tiling is not always possible. Consider for exemple the situation were one corner is surrounded by
two removed squares of the same color, the two other ones being anywhere else on the board. Then, the isolated corner is
obviously not tileable with dominoes and so the amputated board is not.
If we restrict the situation to the cases where the board doesn't fall apart, it seems that the tiling is always
possible, but the proof is not easy to write.
\bigskip
\subsection*{Problem \prob}
\begin{quote}
Three arbitrary pairs of squares of different colors have been removed from a chessboard, so that the chessboard does
not split into two or more separate pieces. Is it always possible to cover the remaining portion of the board with
dominoes so that each domino piece covers exactly two squares?
\end{quote}
\medskip
\begin{minipage}{10cm}
This is not always possible to do, as we will show with one special configuration.\\
The figure on the right depicts the lower right corner of the board. Remove the three black squares marked with a right
cross, and the three white squares anywhere else on the board, so that it does not split into two or more pieces. Then
the only way to cover the lower right white square is to put a domino as shown with a crosshatched rectangle. It will
then be impossible to cover the right square just left of this domino.
\end{minipage}
\begin{minipage}{5.5cm}
\begin{center}
\newrgbcolor{qrqrqr}{0 0 0}
\newrgbcolor{fefefe}{1 1 1}
\psset{xunit=0.9cm,yunit=0.9cm,algebraic=true,dotstyle=*,dotsize=3pt 0,linewidth=0.8pt,arrowsize=3pt 2,arrowinset=0.25}
\begin{pspicture*}(3.56,-1.26)(8.24,3.32)
\pspolygon[linestyle=none,fillstyle=solid,fillcolor=qrqrqr](7,0)(8,0)(8,1)(7,1)
\pspolygon[linestyle=none,fillstyle=solid,fillcolor=qrqrqr](5,0)(6,0)(6,1)(5,1)
\pspolygon[linestyle=none,fillstyle=solid,fillcolor=qrqrqr](4,-1)(5,-1)(5,0)(4,0)
\pspolygon[linestyle=none,fillstyle=solid,fillcolor=qrqrqr](6,-1)(7,-1)(7,0)(6,0)
\pspolygon[linestyle=none,fillstyle=solid,fillcolor=qrqrqr](3,0)(4,0)(4,1)(3,1)
\pspolygon[linestyle=none,fillstyle=solid,fillcolor=qrqrqr](4,1)(5,1)(5,2)(4,2)
\pspolygon[linestyle=none,fillstyle=solid,fillcolor=qrqrqr](6,1)(7,1)(7,2)(6,2)
\pspolygon[linestyle=none,fillstyle=solid,fillcolor=qrqrqr](3,2)(4,2)(4,3)(3,3)
\pspolygon[linestyle=none,fillstyle=solid,fillcolor=qrqrqr](5,2)(6,2)(6,3)(5,3)
\pspolygon[linestyle=none,fillstyle=solid,fillcolor=qrqrqr](7,2)(8,2)(8,3)(7,3)
\pspolygon[linestyle=none,fillstyle=solid,fillcolor=qrqrqr](6,3)(7,3)(7,4)(6,4)
\pspolygon[linestyle=none,fillstyle=solid,fillcolor=qrqrqr](4,3)(5,3)(5,4)(4,4)
\psline[linecolor=qrqrqr](7,0)(8,0)
\psline[linecolor=qrqrqr](8,0)(8,1)
\psline[linecolor=qrqrqr](8,1)(7,1)
\psline[linecolor=qrqrqr](7,1)(7,0)
\psline[linecolor=qrqrqr](5,0)(6,0)
\psline[linecolor=qrqrqr](6,0)(6,1)
\psline[linecolor=qrqrqr](6,1)(5,1)
\psline[linecolor=qrqrqr](5,1)(5,0)
\psline[linecolor=qrqrqr](4,-1)(5,-1)
\psline[linecolor=qrqrqr](5,-1)(5,0)
\psline[linecolor=qrqrqr](5,0)(4,0)
\psline[linecolor=qrqrqr](4,0)(4,-1)
\psline[linecolor=qrqrqr](6,-1)(7,-1)
\psline[linecolor=qrqrqr](7,-1)(7,0)
\psline[linecolor=qrqrqr](7,0)(6,0)
\psline[linecolor=qrqrqr](6,0)(6,-1)
\psline[linecolor=qrqrqr](3,0)(4,0)
\psline[linecolor=qrqrqr](4,0)(4,1)
\psline[linecolor=qrqrqr](4,1)(3,1)
\psline[linecolor=qrqrqr](3,1)(3,0)
\psline[linecolor=qrqrqr](4,1)(5,1)
\psline[linecolor=qrqrqr](5,1)(5,2)
\psline[linecolor=qrqrqr](5,2)(4,2)
\psline[linecolor=qrqrqr](4,2)(4,1)
\psline[linecolor=qrqrqr](6,1)(7,1)
\psline[linecolor=qrqrqr](7,1)(7,2)
\psline[linecolor=qrqrqr](7,2)(6,2)
\psline[linecolor=qrqrqr](6,2)(6,1)
\psline[linecolor=qrqrqr](3,2)(4,2)
\psline[linecolor=qrqrqr](4,2)(4,3)
\psline[linecolor=qrqrqr](4,3)(3,3)
\psline[linecolor=qrqrqr](3,3)(3,2)
\psline[linecolor=qrqrqr](5,2)(6,2)
\psline[linecolor=qrqrqr](6,2)(6,3)
\psline[linecolor=qrqrqr](6,3)(5,3)
\psline[linecolor=qrqrqr](5,3)(5,2)
\psline[linecolor=qrqrqr](7,2)(8,2)
\psline[linecolor=qrqrqr](8,2)(8,3)
\psline[linecolor=qrqrqr](8,3)(7,3)
\psline[linecolor=qrqrqr](7,3)(7,2)
\psline[linecolor=qrqrqr](6,3)(7,3)
\psline[linecolor=qrqrqr](7,3)(7,4)
\psline[linecolor=qrqrqr](7,4)(6,4)
\psline[linecolor=qrqrqr](6,4)(6,3)
\psline[linecolor=qrqrqr](4,3)(5,3)
\psline[linecolor=qrqrqr](5,3)(5,4)
\psline[linecolor=qrqrqr](5,4)(4,4)
\psline[linecolor=qrqrqr](4,4)(4,3)
\psline[linecolor=fefefe](4,0)(5,-1)
\psline[linecolor=fefefe](4,-1)(5,0)
\psline[linecolor=fefefe](5,1)(6,0)
\psline[linecolor=fefefe](5,0)(6,1)
\psline[linecolor=fefefe](7,1)(8,0)
\psline[linecolor=fefefe](7,0)(8,1)
\pspolygon[fillcolor=gray,fillstyle=solid,linecolor=gray](6.25,-0.75)(6.25,-0.25)(7.75,-0.25)(7.75,-0.75)
\psline(3,4)(3,-1)
\psline(3,-1)(8,-1)
\psline(8,-1)(8,4)
\psline(8,4)(3,4)
\end{pspicture*}
\end{center}
\end{minipage}
\pagebreak
\subsection*{Problem \prob}
\begin{quote}
A domino has two edges, a long edge and a short edge. Two adjacent dominoes must be in one of the only three possible
configurations : long edge to long edge, short edge to short edge and long edge to short edge. In a domino tiling of a
chessboard, what is the minimum number of long-edge to long-edge pairs ?
\end{quote}
\medskip
\begin{minipage}{8cm}
The tilings shown on the right as only one long-edge to long-edge pair. This is the smallest possible
number of such pairs, as it's impossible to do a tiling with none. Indeed, if you start with a domino in one corner,
avoiding long-edge to long-edge pairs will impose the placement of all the dominoes as shown on the figure, except the
four middle squares. Then we need to place two dominoes on these squares, which will give us three long-edge to
long-edge paris in one case and one in the other.
\end{minipage}
\begin{minipage}{7.5cm}
\begin{center}
\includegraphics[width=6cm]{images/problem8.eps}
\end{center}
\end{minipage}
\bigskip
\subsection*{Problem \prob}
\begin{quote}
Prove that in any cover of chessboard with dominoes, the number of horizontal
dominoes with a black left square and the number of horizontal dominoes with a white left square are equal.
\end{quote}
The proof of this property is given by E. W. Dijsktra :
For a given partitioning, consider one of the seven lines that separate two adjacent columns; it divides the board into
a left and a right part. We observe that
\begin{enumerate}
\item because the column length is even, each column, and hence the left part, contains equal numbers of
black and white squares, and ;
\item because a domino consists of a black and a white square, the dominoes entirely to the left of the line comprise
equal numbers of black and white squares.
\end{enumerate}
Combining the two observations, we conclude that, among the horizontal dominoes crossed by the line, there are as many
with a black left square as with a white one. Since each horizontal domino is crossed by exactly one of the seven lines,
we conclude by summation that the number of horizontal dominoes with a black left square and the number of horizontal
dominoes with a white left square are equal.
\pagebreak
\moddoc{Chessboards}
\begin{center}
\psset{unit=2cm}
\begin{pspicture}(0,0)(8,8)
\multido{\n=0+1}{9}{
\psline(0,\n)(8,\n)
}
\multido{\d=0+1}{9}{
\psline(\d,0)(\d,8)
}
\multido{\n=0+2}{4}{
\multido{\d=0+2}{4}{
\rput(\n,\d){
\pspolygon[linewidth=1.5pt,fillstyle=solid,fillcolor=black](0,0)(0,1)(1,1)(1,0)
}}
}
\multido{\n=1+2}{4}{
\multido{\d=1+2}{4}{
\rput(\n,\d){
\pspolygon[linewidth=1.5pt,fillstyle=solid,fillcolor=black](0,0)(0,1)(1,1)(1,0)
}}
}
\end{pspicture}
\end{center}
\pagebreak
\moddoc{Dominoes}
\psset{unit=2cm}
\begin{pspicture}(0,0)(9,9)
\multido{\n=0+2}{4}{
\multido{\d=0+1}{8}{
\rput(\n,\d){
\pspolygon[linewidth=1.5pt](0,0)(0,1)(1,1)(1,0)
\pspolygon[linewidth=1.5pt,fillstyle=solid,fillcolor=black](1,0)(1,1)(2,1)(2,0)
}}
}
\end{pspicture}
\end{document}