%  Homework assignment 2 solutions
%  21-110: Problem Solving in Recreational Mathematics, spring 2010
%  Assigned: Monday, January 25, 2010. Due: Monday, February 1, 2010.
%  Brian Kell <bkell@cmu.edu>

\pdfpagewidth=8.5truein \pdfpageheight=11truein
\hsize=6truein \vsize=9truein
\pdfhorigin=1.25truein \pdfvorigin=1truein

% MetaPost stuff
\input supp-pdf
\def\fig#1{\convertMPtoPDF{#1}{1}{1}}
\def\midfig#1{{%
	\setbox0=\hbox{\fig{#1}}%
	\dimen0=0.5\ht0%
	\advance\dimen0 by-0.3\ht\strutbox
	\lower\dimen0\box0%
}}

\font\titlefont=cmbx12
\font\smfont=cmr8
\font\sansfont=cmss10

\headline={\hfil}
\footline={\hfil}
\topskip=20pt plus2pt

\newcount\pno  \pno=0
\def\problem{\goodbreak\advance\pno by1 \noindent{\bf Problem~\the\pno.} }
\def\problemno#1. {\goodbreak\noindent{\bf Problem~\hbox{#1}.} }
\def\noskiphint#1\par{\nobreak{\hyphenpenalty=10000\noindent{\it Hint:\/}\enspace#1\par}}
\def\hint#1\par{\nobreak\medskip\noskiphint#1\par}
\def\itemhint#1\par{\nobreak\smallskip\item{}{\it Hint:\/}\enspace#1\par}
\def\solution{\nobreak\medskip\noindent{\bf Solution.} }
\def\part#1{\goodbreak\medskip\indent\llap{#1\enspace}\ignorespaces}
\def\firstpart#1{\nobreak\medskip\indent\llap{#1\enspace}\ignorespaces}

% Pilfered from an example on page 106 of the TeXbook
\def\qed{{\unskip\nobreak\hfil\penalty50
	\hskip1em\hbox{}\nobreak\hfil\hbox{\vrule\vbox to6pt{\hrule\hbox to5.2pt{\hss}\vfil\hrule}\vrule}
	\parfillskip=0pt \finalhyphendemerits=0 \par}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Crossword macros: Brian Kell, 11-14 August 2005

\font\gridnfont=cmr8
\font\gridlfont=cmr10

\newdimen\squaresize\squaresize=20pt\relax
\newdimen\padding\padding=1pt\relax
\newdimen\colwidth\colwidth=\hsize\advance\colwidth by-7pc\divide\colwidth by2

\newcount\n % number to be put in the next numbered square
\newcount\s % whether this square should be numbered

\def\nsquare{\vbox to\squaresize{\vskip\padding\hbox to\squaresize{%
	\hskip\padding\gridnfont\the\n\hss}\vss}\global\advance\n by1 }
\def\lsquare#1{\ifnum\s>0 \rlap{\nsquare}\fi\vbox to\squaresize{%
	\vss\vss\hbox to\squaresize{\hss\gridlfont#1\hss}\vss}\global\s=0 }
\def\bsquare{\vbox{\hrule height\squaresize depth0pt width\squaresize}}
\def\wsquare{\vbox to\squaresize{\vfil\hbox to\squaresize{\hfil}}}

\def\crossword#1{{
\global\n=1 \global\s=0
\offinterlineskip
\vbox{\hrule{#1}}}}

\def\row#1{\hbox{\vrule{#1}}\hrule}

{\catcode`A=13 \catcode`B=13 \catcode`C=13 \catcode`D=13 \catcode`E=13
\catcode`F=13 \catcode`G=13 \catcode`H=13 \catcode`I=13 \catcode`J=13
\catcode`K=13 \catcode`L=13 \catcode`M=13 \catcode`N=13 \catcode`O=13
\catcode`P=13 \catcode`Q=13 \catcode`R=13 \catcode`S=13 \catcode`T=13
\catcode`U=13 \catcode`V=13 \catcode`W=13 \catcode`X=13 \catcode`Y=13
\catcode`Z=13 \catcode`.=13 \catcode`/=13 \catcode`*=13
\global\def A{\lsquare{\char65}\vrule}\global\def B{\lsquare{\char66}\vrule}
\global\def C{\lsquare{\char67}\vrule}\global\def D{\lsquare{\char68}\vrule}
\global\def E{\lsquare{\char69}\vrule}\global\def F{\lsquare{\char70}\vrule}
\global\def G{\lsquare{\char71}\vrule}\global\def H{\lsquare{\char72}\vrule}
\global\def I{\lsquare{\char73}\vrule}\global\def J{\lsquare{\char74}\vrule}
\global\def K{\lsquare{\char75}\vrule}\global\def L{\lsquare{\char76}\vrule}
\global\def M{\lsquare{\char77}\vrule}\global\def N{\lsquare{\char78}\vrule}
\global\def O{\lsquare{\char79}\vrule}\global\def P{\lsquare{\char80}\vrule}
\global\def Q{\lsquare{\char81}\vrule}\global\def R{\lsquare{\char82}\vrule}
\global\def S{\lsquare{\char83}\vrule}\global\def T{\lsquare{\char84}\vrule}
\global\def U{\lsquare{\char85}\vrule}\global\def V{\lsquare{\char86}\vrule}
\global\def W{\lsquare{\char87}\vrule}\global\def X{\lsquare{\char88}\vrule}
\global\def Y{\lsquare{\char89}\vrule}\global\def Z{\lsquare{\char90}\vrule}
\global\def.{\ifnum\s>0 \nsquare\else\wsquare\fi\vrule\global\s=0 }
\global\def/{\bsquare\vrule}\global\def*{\global\s=1 }}

\def\begincrosswordsemantics{
\global\catcode`A=13 \global\catcode`B=13 \global\catcode`C=13
\global\catcode`D=13 \global\catcode`E=13 \global\catcode`F=13
\global\catcode`G=13 \global\catcode`H=13 \global\catcode`I=13
\global\catcode`J=13 \global\catcode`K=13 \global\catcode`L=13
\global\catcode`M=13 \global\catcode`N=13 \global\catcode`O=13
\global\catcode`P=13 \global\catcode`Q=13 \global\catcode`R=13
\global\catcode`S=13 \global\catcode`T=13 \global\catcode`U=13
\global\catcode`V=13 \global\catcode`W=13 \global\catcode`X=13
\global\catcode`Y=13 \global\catcode`Z=13
\global\catcode`.=13 \global\catcode`/=13 \global\catcode`*=13
\global\catcode` =9}

\def\endcrosswordsemantics{
\global\catcode`A=11 \global\catcode`B=11 \global\catcode`C=11
\global\catcode`D=11 \global\catcode`E=11 \global\catcode`F=11
\global\catcode`G=11 \global\catcode`H=11 \global\catcode`I=11
\global\catcode`J=11 \global\catcode`K=11 \global\catcode`L=11
\global\catcode`M=11 \global\catcode`N=11 \global\catcode`O=11
\global\catcode`P=11 \global\catcode`Q=11 \global\catcode`R=11
\global\catcode`S=11 \global\catcode`T=11 \global\catcode`U=11
\global\catcode`V=11 \global\catcode`W=11 \global\catcode`X=11
\global\catcode`Y=11 \global\catcode`Z=11
\global\catcode`.=12 \global\catcode`/=12 \global\catcode`*=12
\global\catcode` =10}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\centerline{\titlefont 21-110: Problem Solving in Recreational Mathematics}
\smallskip
\centerline{\bf Homework assignment~2 solutions}

\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Suppose you have one copy of each free hexomino. Prove that it is
impossible to arrange them into a rectangle.

\solution There are 35~free hexominoes. Each hexomino consists of six squares,
so the total area of all 35~free hexominoes is $35\times6=210$~squares. The
prime factorization of~210 is $2\times3\times5\times7$, so the possible
dimensions of a rectangle having an area of~210 are $1\times210$,~$2\times105$,
$3\times70$, $5\times42$, $6\times35$, $7\times30$, $10\times21$,
and~$14\times15$. We can rule out the $1\times210$ and~$2\times105$ rectangles
right away, because many of the hexominoes cannot possibly fit in a rectangle
having a width less than~3.

In all of the remaining cases, we observe that one of the dimensions of the
rectangle is even (since 2~is a factor of~210), and so, if we color the squares
of the rectangle like a checkerboard, there must be the same number of light
and dark squares: along the even dimension of the rectangle, adjacent rows of
squares alternate colors, so these rows can be divided into pairs, with each
pair having the same number of light and dark squares. Therefore, in any of the
possible rectangles colored checkerboard-style, there must be 105~light squares
and 105~dark squares.

Now we color the free hexominoes with light squares and dark squares in a
checkered pattern, as if they had been cut from a checkerboard. Most of the
hexominoes (24~of them) have three dark squares and three light squares. Let's
call these the ``odd'' hexominoes, since they cover an odd number of squares of
each color. These are the odd hexominoes:
$$\displaylines{%
\midfig{homework-2-sol-hexomino-i-checker.mps}\qquad
\midfig{homework-2-sol-hexomino-l-checker.mps}\qquad
\midfig{homework-2-sol-hexomino-low-y-checker.mps}\qquad
\midfig{homework-2-sol-hexomino-v-checker.mps}\qquad
\midfig{homework-2-sol-hexomino-p-checker.mps}\qquad
\midfig{homework-2-sol-hexomino-short-t-checker.mps}\qquad
\midfig{homework-2-sol-hexomino-d-checker.mps}\qquad
\midfig{homework-2-sol-hexomino-c-checker.mps}\qquad
\midfig{homework-2-sol-hexomino-hi-f-checker.mps}\cr
\noalign{\smallskip}
\midfig{homework-2-sol-hexomino-long-z-checker.mps}\qquad
\midfig{homework-2-sol-hexomino-italic-x-checker.mps}\qquad
\midfig{homework-2-sol-hexomino-o-checker.mps}\qquad
\midfig{homework-2-sol-hexomino-wb-checker.mps}\qquad
\midfig{homework-2-sol-hexomino-wa-checker.mps}\qquad
\midfig{homework-2-sol-hexomino-j-checker.mps}\qquad
\midfig{homework-2-sol-hexomino-short-z-checker.mps}\qquad
\midfig{homework-2-sol-hexomino-long-n-checker.mps}\cr
\noalign{\smallskip}
\midfig{homework-2-sol-hexomino-s-checker.mps}\qquad
\midfig{homework-2-sol-hexomino-r-checker.mps}\qquad
\midfig{homework-2-sol-hexomino-q-checker.mps}\qquad
\midfig{homework-2-sol-hexomino-e-checker.mps}\qquad
\midfig{homework-2-sol-hexomino-hi-4-checker.mps}\qquad
\midfig{homework-2-sol-hexomino-g-checker.mps}\qquad
\midfig{homework-2-sol-hexomino-m-checker.mps}}$$

The remaining 11~hexominoes cover two dark squares and four light squares, or
four dark squares and two light squares (depending on how we choose to color
each one). Let's call these the ``even'' hexominoes, since they cover an even
number of squares of each color. These are the even hexominoes:
$$\hbox to\hsize{\midfig{homework-2-sol-hexomino-hi-y-checker.mps}\hfil
\midfig{homework-2-sol-hexomino-u-checker.mps}\hfil
\midfig{homework-2-sol-hexomino-long-t-checker.mps}\hfil
\midfig{homework-2-sol-hexomino-low-f-checker.mps}\hfil
\midfig{homework-2-sol-hexomino-x-checker.mps}\hfil
\midfig{homework-2-sol-hexomino-a-checker.mps}\hfil
\midfig{homework-2-sol-hexomino-wc-checker.mps}\hfil
\midfig{homework-2-sol-hexomino-short-n-checker.mps}\hfil
\midfig{homework-2-sol-hexomino-k-checker.mps}\hfil
\midfig{homework-2-sol-hexomino-h-checker.mps}\hfil
\midfig{homework-2-sol-hexomino-low-4-checker.mps}}$$

There are an even number of odd hexominoes and an odd number of even
hexominoes. Since ``$\hbox{even}\times\hbox{odd}=\hbox{even}$'' and
``$\hbox{odd}\times\hbox{even}=\hbox{even}$,'' the 35~free hexominoes will
always cover an even number of squares of each color in all, no matter how they
are arranged on a (large) checkerboard. But all of the possible rectangles have
105~squares of each color, which is odd. So there is no way to arrange the
35~free hexominoes into a rectangle. \qed

\nobreak\medskip

\noindent[\thinspace This proof is yet another example of the use of
{\it parity}, that~is, evenness or oddness. The mouse-in-a-maze problem
discussed in class, and the fly-on-a-cube problem from the last homework, also
used parity in their solutions. Parity is a simple but often surprisingly
useful tool.\thinspace]

\bigbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem There are exactly~11 free hexominoes that can be folded to make a
cube. These hexominoes are called {\it nets\/} of the cube.

\nobreak\smallskip

\item{(a)} Draw the 11~nets of the cube.

\nobreak\smallskip

\item{(b)} Explain why each of the other free hexominoes is not a net of the
cube.

\nobreak\smallskip

\item{(c)} All of the nets of the cube have the same perimeter. What is this
common perimeter? Why is it not the same as the number of edges of a cube?

\solution

\firstpart{(a)} The 11~nets of the cube are shown below.
$$\hbox to\hsize{\midfig{homework-2-sol-hexomino-x.mps}\hfil
\midfig{homework-2-sol-hexomino-long-t.mps}\hfil
\midfig{homework-2-sol-hexomino-italic-x.mps}\hfil
\midfig{homework-2-sol-hexomino-s.mps}\hfil
\midfig{homework-2-sol-hexomino-hi-f.mps}\hfil
\midfig{homework-2-sol-hexomino-low-f.mps}\hfil
\midfig{homework-2-sol-hexomino-long-z.mps}\hfil
\midfig{homework-2-sol-hexomino-wb.mps}\hfil
\midfig{homework-2-sol-hexomino-hi-4.mps}\hfil
\midfig{homework-2-sol-hexomino-wc.mps}\hfil
\midfig{homework-2-sol-hexomino-m.mps}}$$

\part{(b)} First we can rule out any hexomino that has four squares in a
$2\times2$~arrangement, since such an arrangement makes it impossible to fold
the hexomino so that each square forms a face of a cube. Therefore the
following eight hexominoes are not nets of the cube:
$$\midfig{homework-2-sol-hexomino-p.mps}\qquad
\midfig{homework-2-sol-hexomino-d.mps}\qquad
\midfig{homework-2-sol-hexomino-o.mps}\qquad
\midfig{homework-2-sol-hexomino-a.mps}\qquad
\midfig{homework-2-sol-hexomino-r.mps}\qquad
\midfig{homework-2-sol-hexomino-short-n.mps}\qquad
\midfig{homework-2-sol-hexomino-k.mps}\qquad
\midfig{homework-2-sol-hexomino-q.mps}$$

\noindent We can also rule out the hexominoes that have five or more squares in
a straight line, because attempting to fold such a hexomino into a cube would
result in overlapping squares (and therefore we would not be able to form all
six faces of the cube). This eliminates the following four hexominoes:
$$\midfig{homework-2-sol-hexomino-i.mps}\qquad
\midfig{homework-2-sol-hexomino-l.mps}\qquad
\midfig{homework-2-sol-hexomino-hi-y.mps}\qquad
\midfig{homework-2-sol-hexomino-low-y.mps}$$

\noindent Similarly, each of the remaining hexominoes has at least one pair of
squares that would overlap if we attempted to fold the hexomino into a cube.
One such pair is marked for each of the 12~hexominoes below, showing that they
cannot be nets of the cube.
$$\hbox to\hsize{\midfig{homework-2-sol-hexomino-v-xed.mps}\hfil
\midfig{homework-2-sol-hexomino-short-t-xed.mps}\hfil
\midfig{homework-2-sol-hexomino-u-xed.mps}\hfil
\midfig{homework-2-sol-hexomino-c-xed.mps}\hfil
\midfig{homework-2-sol-hexomino-wa-xed.mps}\hfil
\midfig{homework-2-sol-hexomino-j-xed.mps}\hfil
\midfig{homework-2-sol-hexomino-short-z-xed.mps}\hfil
\midfig{homework-2-sol-hexomino-long-n-xed.mps}\hfil
\midfig{homework-2-sol-hexomino-h-xed.mps}\hfil
\midfig{homework-2-sol-hexomino-e-xed.mps}\hfil
\midfig{homework-2-sol-hexomino-low-4-xed.mps}\hfil
\midfig{homework-2-sol-hexomino-g-xed.mps}}$$

\part{(c)} The nets of the cube all have perimeter~14 (this is easy to check).
A cube has 12~edges. The reason these numbers are not the same is that the
14~``outer edges'' of a net of the cube do not directly produce the edges of
the cube in a one-to-one fashion. Rather, each edge of the cube is formed in
one of two ways: either as a fold on an ``inner edge'' of the net (that~is, a
dividing line between two adjacent squares in the hexomino), or as a seam
between two ``outer edges'' of the net. Therefore the perimeter of the net,
having length~14, contributes exactly seven of the edges of the cube, and the
five ``inner edges'' of the net contribute the remaining five edges of the cube
(note that every net of the cube has exactly five ``inner edges''). This
accounts for all~12 of the edges of the cube. \qed

\bigbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem The following questions refer to two-dimensional shapes in the plane.

\nobreak\smallskip

\item{(a)} Draw a shape that has reflection symmetry but not rotation symmetry.
Show the line of symmetry.

\nobreak\smallskip

\item{(b)} Draw a shape that has rotation symmetry but not reflection symmetry.
Describe the rotation symmetry (how many degrees do you need to rotate the
shape in order to have it look the same?).

\nobreak\smallskip

\item{(c)} Draw a shape that has neither reflection symmetry nor rotation
symmetry. Explain why this shape has neither of these symmetries.

\nobreak\smallskip

\item{(d)} Draw a shape that has both reflection symmetry and rotation
symmetry. Show the line of symmetry and describe the rotation symmetry.

\nobreak\smallskip

\item{(e)} Is there a shape that has {\it two\/} lines of symmetry but does
{\it not\/} have rotation symmetry? If so, give an example. If not, why not?

\solution There are many possible shapes that can be drawn, but simple examples
can be found among the letters of the alphabet (or among the polyominoes!).

\firstpart{(a)} The letter~{\sansfont T} has reflection symmetry about a
vertical line, but it does not have rotation symmetry.
$$\midfig{homework-2-sol-t.mps}$$

\part{(b)} The letter~{\sansfont Z} has rotation symmetry of~$180^\circ$ about
its center, but it does not have reflection symmetry.
$$\midfig{homework-2-sol-z.mps}$$

\part{(c)} The letter~{\sansfont F} has neither reflection symmetry nor
rotation symmetry. There is no line about which it can be reflected and look
the same as before, nor is there any angle by which it can be rotated and look
the same (other than a trivial $360^\circ$~rotation).
$$\midfig{homework-2-sol-f.mps}$$

\part{(d)} The letter~{\sansfont X} has both reflection symmetry, about both a
horizontal and a vertical line, and rotation symmetry about its center
by~$180^\circ$.
$$\midfig{homework-2-sol-x.mps}$$

\part{(e)} If a shape has two lines of reflection symmetry, it must also have
rotation symmetry. Imagine a cutout of such a shape that is painted red on one
side and blue on the other, with the red side initially face-up. Mark the
``top'' edge of the shape somehow, so that we can detect a rotation. Now
``reflect'' it about one of its lines of symmetry by flipping it over (this
causes the blue side to come up), and then reflect it a second time about its
{\it other\/} line of symmetry (this causes the red face to come up again). We
see that the end result is as if we had simply rotated the original shape by
some angle. (Try this with a piece of paper.) But the shape looks the same as
it did originally, except for the markings we made, because each of the
reflections kept the shape the same. So the shape must have rotation symmetry
as well as reflection symmetry. (The moral of the story is that two reflections
are equivalent to one rotation.) \qed

\bigbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Consider all of the free polyominoes up to area~6 (that~is, the
monomino, the domino, the trominoes, the tetrominoes, the pentominoes, and the
hexominoes). Classify them according to their symmetry.

\solution There are 56~of these free polyominoes in all: one monomino, one
domino, two trominoes, five tetrominoes, 12~pentominoes, and 35~hexominoes. Out
of all of these, there are three that have the greatest symmetry possible for
shapes made up of connected squares, namely, four lines of symmetry (one
horizontal, one vertical, and two diagonal) and rotational symmetry
by~$90^\circ$. These three polyominoes are shown below.
$$\midfig{homework-2-sol-monomino.mps}\qquad
\midfig{homework-2-sol-tetromino-square.mps}\qquad
\midfig{homework-2-sol-pentomino-x.mps}$$

The next most symmetrical of these polyominoes are those in the shape of
(non-square) rectangles. These polyominoes have two lines of symmetry (one
horizontal and one vertical) and rotational symmetry by~$180^\circ$. There are
six such polyominoes, shown below.
$$\midfig{homework-2-sol-domino.mps}\qquad
\midfig{homework-2-sol-tromino-straight.mps}\qquad
\midfig{homework-2-sol-tetromino-straight.mps}\qquad
\midfig{homework-2-sol-pentomino-i.mps}\qquad
\midfig{homework-2-sol-hexomino-i.mps}\qquad
\midfig{homework-2-sol-hexomino-o.mps}$$

Next, there are nine of these polyominoes having only one line of symmetry,
either horizontal or vertical (depending on orientation), and no rotational
symmetry.
$$\midfig{homework-2-sol-tetromino-t.mps}\qquad
\midfig{homework-2-sol-pentomino-t.mps}\qquad
\midfig{homework-2-sol-pentomino-u.mps}\qquad
\midfig{homework-2-sol-hexomino-low-y.mps}\qquad
\midfig{homework-2-sol-hexomino-d.mps}\qquad
\midfig{homework-2-sol-hexomino-c.mps}\qquad
\midfig{homework-2-sol-hexomino-long-t.mps}\qquad
\midfig{homework-2-sol-hexomino-x.mps}\qquad
\midfig{homework-2-sol-hexomino-e.mps}$$
In addition, five of the polyominoes up to area~6 have one diagonal line of
symmetry and no rotational symmetry. These might be considered to have the
same symmetry as the previous nine---after all, they have the same number of
lines of symmetry and the same (i.e., no) rotational symmetry---but we have
listed them separately here because they seem to have a different ``flavor''
than the others. (This is not a mathematically precise statement.)
$$\midfig{homework-2-sol-tromino-right.mps}\qquad
\midfig{homework-2-sol-pentomino-v.mps}\qquad
\midfig{homework-2-sol-pentomino-w.mps}\qquad
\midfig{homework-2-sol-hexomino-a.mps}\qquad
\midfig{homework-2-sol-hexomino-k.mps}$$

Then there are seven of these polyominoes that have $180^\circ$~rotational
symmetry but no lines of reflection symmetry (not even diagonally, as you will
see if you examine them carefully):
$$\midfig{homework-2-sol-tetromino-s.mps}\qquad
\midfig{homework-2-sol-pentomino-z.mps}\qquad
\midfig{homework-2-sol-hexomino-long-z.mps}\qquad
\midfig{homework-2-sol-hexomino-italic-x.mps}\qquad
\midfig{homework-2-sol-hexomino-wb.mps}\qquad
\midfig{homework-2-sol-hexomino-s.mps}\qquad
\midfig{homework-2-sol-hexomino-short-n.mps}$$

The remaining 26~polyominoes with area no greater than~6 have neither
reflection symmetry nor rotational symmetry (other than trivial
$360^\circ$~rotational symmetry). They are listed below.
$$\displaylines{%
\hbox to\hsize{\midfig{homework-2-sol-tetromino-l.mps}\hfil
\midfig{homework-2-sol-pentomino-l.mps}\hfil
\midfig{homework-2-sol-pentomino-y.mps}\hfil
\midfig{homework-2-sol-pentomino-f.mps}\hfil
\midfig{homework-2-sol-pentomino-p.mps}\hfil
\midfig{homework-2-sol-pentomino-n.mps}\hfil
\midfig{homework-2-sol-hexomino-l.mps}\hfil
\midfig{homework-2-sol-hexomino-hi-y.mps}\hfil
\midfig{homework-2-sol-hexomino-v.mps}\hfil
\midfig{homework-2-sol-hexomino-p.mps}\hfil
\midfig{homework-2-sol-hexomino-short-t.mps}\hfil
\midfig{homework-2-sol-hexomino-u.mps}\hfil
\midfig{homework-2-sol-hexomino-hi-f.mps}}\cr
\noalign{\smallskip}
\hbox to\hsize{\midfig{homework-2-sol-hexomino-low-f.mps}\hfil
\midfig{homework-2-sol-hexomino-wa.mps}\hfil
\midfig{homework-2-sol-hexomino-j.mps}\hfil
\midfig{homework-2-sol-hexomino-short-z.mps}\hfil
\midfig{homework-2-sol-hexomino-wc.mps}\hfil
\midfig{homework-2-sol-hexomino-long-n.mps}\hfil
\midfig{homework-2-sol-hexomino-r.mps}\hfil
\midfig{homework-2-sol-hexomino-q.mps}\hfil
\midfig{homework-2-sol-hexomino-h.mps}\hfil
\midfig{homework-2-sol-hexomino-low-4.mps}\hfil
\midfig{homework-2-sol-hexomino-hi-4.mps}\hfil
\midfig{homework-2-sol-hexomino-g.mps}\hfil
\midfig{homework-2-sol-hexomino-m.mps}}\cr
}$$

There are at least two potential types of symmetry that are not exhibited by
any of these 56~``small'' polyominoes: two lines of {\it diagonal\/} symmetry
and $180^\circ$~rotational symmetry, but no horizontal or vertical symmetry;
and $90^\circ$~rotational symmetry but no reflection symmetry. The smallest
polyomino having the first type of symmetry has area~7, and the smallest having
the second type of symmetry has area~8. Can you find them? \qed

\bigbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Design at least two interesting tessellations, based on different
fundamental tilings. (For example, one may be based on the regular tiling of
squares, and the other may be based on a semiregular tiling of hexagons and
triangles.) Present your tessellations carefully---neatness is important. I
suggest cutting out a template from heavy paper or cardboard to trace, or
cutting out many individual tiles to paste together. Use color to highlight the
repeating nature of your tessellations and explain any other interesting
features. Be creative!

\solution Here's a modification of the ``jumping man'' tiling I sketched in
class. It's based on the tiling of parallelograms shown on the left.
$$\midfig{homework-2-sol-tessellation-1-base.mps}\qquad
	\midfig{homework-2-sol-tessellation-1.mps}$$
I tried to make a tessellation of airplanes from the regular tiling of
hexagons, but I had a hard time getting the airplanes to look right. Here's the
best I could come up with.
$$\midfig{homework-2-sol-tessellation-2-base.mps}\qquad
	\midfig{homework-2-sol-tessellation-2.mps}$$
(This tessellation was harder to work with than the first one, because the
tiles aren't all facing the same direction.) \qed

\bigbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Solve the following crossword. Every numbered word in the puzzle must
appear in the given word list, and no word may be used more than once. Explain
the process you used.

\newbox\crosswordbox
\setbox\crosswordbox=\hbox{%
\begincrosswordsemantics$\crossword{%  for some reason math mode is required
\row{*.*.*. /*.*.*.}%
\row{*. . . /*. . .}%
\row{*. . .*. . / /}%
\row{*. . / . /*.*.}%
\row{ / /*. .*. . .}%
\row{*.*. . /*. . .}%
\row{*. . . /*. . .}%
}$\endcrosswordsemantics\unskip % shouldn't need \unskip: bug in crossword macro
}

\newbox\wordlistbox
\setbox\wordlistbox=\hbox{\hsize=3in\vbox to\ht\crosswordbox{%
\noindent{\bf Word list:}\enspace an, as, at, do, eh, in, it, lo, me, no, oh,
so, to; ago, aim, ale, all, and, ant, ash, ate, awe, din, dot, elk, end, has,
hat, ice, ink, key, kid, lie, lot, mow, new, not, ode, owe, pat, pin, set, ski,
spa, tag, tea, toe, ton, vat, wed, who, win, won, woo, zap, zip; also, apes,
hall, have, head, iris, iron, noon, peas, soot, tend, urns, used, vase, zone;
adore, aside, astir, hooks, legal, shark, shear, snort, stare, stars, start,
syrup, voted.\par
\vfil}}

$$\box\crosswordbox\qquad\box\wordlistbox$$

\solution The solution to this puzzle is {\it unique}, meaning that there is
only one solution. We shall proceed in a very careful and systematic manner to
fill in the words, entering each word into the puzzle only when we have
logically deduced that it is the only possibility. By doing so, not only will
we have found a solution, but we will also have proved that the solution is
unique. (The following description is a somewhat polished form of my reasoning,
so I have edited out some of the dead ends I tried, red herrings I chased, and
false steps I took.)

{
\catcode`_=13
% swiped from the definition of \_ on page 356 of the TeXbook and tweaked a bit
\def_{\leavevmode \kern.06em \vbox{\hrule width0.6em}\kern.06em\relax}
\def\\#1{{\smfont #1}}

A helpful first step is to write down the words of each length in columns on
graph paper, to make it easier to find, say, all of the three-letter words
whose middle letter is~\\A. We will also want to cross off the words as we use
them in the puzzle, so that we avoid using any word more than once.

It will be helpful to have some notation for referring to an entry in the
puzzle that is partially filled in (and, by extension, the set of words that
can fit there). Let's use underscores~(_) to represent blanks, so ``\\{_A__}''
represents a four-letter word whose second letter is~\\A. Sometimes we won't
know exactly what letter goes in a certain square, but we will know it has to
be one of only a few choices. In this situation, we'll use a list of letters in
square brackets~\\{[\thinspace]}. So, for instance, ``\\{_[AER]T}'' represents
a three-letter word whose second letter is either \\A,~\\E, or~\\R, and whose
last letter is~\\T.

The five-letter words seem to be a good place to start---there are only 13~of
them in the word list (whereas there are 43~three-letter words), and they will
cross many other words, making it more likely that we will be able to eliminate
some possibilities.

Let's start by considering the possibilities for the five-letter word at
9~Across. By examining the crossing words, we see that we can eliminate
\\{ADORE}, because it would require the word at 2~Down to be \\{__D_}, and no
four-letter word in the word list has D as its third letter. Similarly, we can
eliminate \\{ASTIR}, because there is no three-letter word of the form~\\{__R}
for 4~Down. Going through the whole list of five-letter words, we can further
eliminate \\{HOOKS} (there is no~\\{__H_} for 1~Down); \\{SHARK} and \\{SHEAR}
(there is no~\\{__H_} for 2~Down); \\{SNORT}, \\{STARE}, \\{STARS}, and
\\{START} (there is no~\\{R__} for 10~Down); and \\{SYRUP} (there is no
\\{__Y_} for 2~Down). This leaves only \\{ASIDE},~\\{LEGAL}, and~\\{VOTED} as
possible words for 9~Across.

Likewise, we can reject the following words for 14~Across: \\{ASIDE}
(no~\\{_D__} for 12~Down), \\{ASTIR} (no~\\{_I__} for 12~Down), \\{HOOKS}
(no~\\{_K__} for 12~Down), \\{LEGAL} (no~\\{G__} for 15~Down), \\{SHARK}
(no~\\{_K__} for 13~Down), \\{SNORT} and~\\{START} (no~\\{_T__} for 13~Down),
\\{SYRUP} (no~\\{R__} for 15~Down), and \\{VOTED} (no~\\{_D__} for 13~Down).
This leaves only \\{ADORE},~\\{SHEAR}, \\{STARE}, and~\\{STARS} as
possibilities for 14~Across.

So the fourth letter of 10~Across (the first letter of 10~Down) must be either
\\D,~\\A, or~\\E, and the second letter of 14~Across (the third letter of
10~Down) must be either \\D,~\\H, or~\\T. In other words, 10~Down must look
like~\\{[ADE]_[DHT]}. There are only five three-letter words like this in the
word list: \\{AND},~\\{ANT}, \\{ASH}, \\{DOT}, and~\\{END}. Fitting these
together, we see that there are just seven possibilities for the combination of
words at 9~Across, 10~Down, and 14~Across: \\{ASIDE}, \\{DOT}, \\{STARE};
\\{ASIDE}, \\{DOT}, \\{STARS}; \\{LEGAL}, \\{AND}, \\{ADORE};
\\{LEGAL}, \\{ANT}, \\{STARE}; \\{LEGAL}, \\{ANT}, \\{STARS};
\\{LEGAL}, \\{ASH}, \\{SHEAR}; and \\{VOTED}, \\{END}, \\{ADORE}.

Suppose 9~Across is \\{LEGAL}. This forces 3~Down to be \\{TAG}, since that is
the only \\{__G} in the word list, and it forces 1~Down to be \\{HALL}, since
that is the only \\{__L_}. But then 7~Across must be \\{A_A}, and there are no
words like this in the list. So we conclude that 9~Across cannot be~\\{LEGAL}.

Suppose 9~Across is \\{VOTED}. This forces 1~Down to be \\{HAVE} (that's the
only \\{__V_}), and so 11~Across must be \\{EH} (the only~\\{E_}). But then
2~Down is \\{__OH}, which is impossible. So 9~Across cannot be~\\{VOTED}.

This means that 9~Across must be \\{ASIDE}, and therefore 10~Down is \\{DOT}
and 14~Across is either \\{STARE} or~\\{STARS}. Let's fill in what we know.

\begincrosswordsemantics
$$\crossword{%
\row{*.*.*. /*.*.*. }%
\row{*. . . /*. . . }%
\row{*A S I*D E / / }%
\row{*. . / O /*.*. }%
\row{ / /*S T*A R . }%
\row{*.*. . /*. . . }%
\row{*. . . /*. . . }%
}$$
\endcrosswordsemantics

Okay, let's attack the northwest corner next. First we see that 3~Down must be
\\{SKI} (the only~\\{__I}), so 1~Across must be \\{HAS} (the only~\\{__S}).
This means that 1~Down is \\{H_A_}, which makes it \\{HEAD}, and 2~Down is
\\{A_S_}, which makes it \\{ALSO}. (In doing this, we have also filled in
\\{ELK} at 7~Across and \\{DO}~at 11~Across, so we cross out these words from
the word list too.) That corner wasn't too bad. The puzzle so far looks like
this:

\begincrosswordsemantics
$$\crossword{%
\row{*H*A*S /*.*.*. }%
\row{*E L K /*. . . }%
\row{*A S I*D E / / }%
\row{*D O / O /*.*. }%
\row{ / /*S T*A R . }%
\row{*.*. . /*. . . }%
\row{*. . . /*. . . }%
}$$
\endcrosswordsemantics

On to the southwest corner. The possibilities for 14~Down are \\{SET}
and~\\{SPA} (remember that \\{SKI} has already been used). But \\{SPA} at
14~Down would require 16~Across to be either \\{ZAP} or~\\{ZIP}, as these are
the only words that fit~\\{__P}, so then 16~Down would need to be~\\{Z_},
which is a problem. Therefore 14~Down must be~\\{SET}.

So 19~Across is \\{__T}. The possibilities here are \\{ANT},~\\{HAT}, \\{LOT},
\\{NOT}, \\{PAT}, and~\\{VAT} (\\{DOT}~and~\\{SET} have already been used). We
can discard most of these possibilities because they require crossing words
that do not exist in the word list: \\{ANT}~would require 16~Down to be~\\{_A};
\\{HAT}~would make 17~Down~\\{_A}; \\{LOT}~makes 16~Down~\\{_L};
\\{PAT}~requires 16~Down to be~\\{_P}; and \\{VAT} needs \\{_V} at 16~Down. The
only possibility remaining is~\\{NOT}, which must be the word at 19~Across.

Hence 16~Down is~\\{_N}, either \\{AN} or~\\{IN}; and 17~Down is~\\{_O}, one of
\\{LO},~\\{NO}, \\{SO}, or~\\{TO} (since \\{DO} has already been used).
Therefore 16~Across must look like \\{[AI][LNST]E}. There are two words like
this in the word list: \\{ALE}~and~\\{ATE}. We don't know for sure which of
these is the correct word at 16~Across, so we'll come back later. However, we
do know that the first letter is~\\A, making 16~Down~\\{AN}.

\begincrosswordsemantics
$$\crossword{%
\row{*H*A*S /*.*.*. }%
\row{*E L K /*. . . }%
\row{*A S I*D E / / }%
\row{*D O / O /*.*. }%
\row{ / /*S T*A R . }%
\row{*A*. E /*. . . }%
\row{*N O T /*. . . }%
}$$
\endcrosswordsemantics

Continuing to the southeast corner, we first look at 12~Down. There are three
possibilities for \\{_R__}, namely, \\{IRIS},~\\{IRON}, and~\\{URNS}. But
\\{URNS} would require 12~Across to be~\\{U_}, which doesn't work. So the first
letter of 12~Down must be~\\I. This means 12~Across is either \\{IN} or~\\{IT}.
We already know that 14~Across is either \\{STARE} or~\\{STARS}, so 13~Down
looks like \\{[NT][ES]__}. Both \\{NS__} and~\\{TS__} cause problems, so
14~Across must be \\{STARE}. This means 13~Down is \\{[NT]E__}; the only word
like this is~\\{TEND}, and so 12~Across is~\\{IT}.

Now if 12~Down were \\{IRIS} we would have \\{__SD} at 20~Across, which would
be impossible to fill; so 12~Down must be \\{IRON}. Then 18~Across looks like
\\{_ON}, so it's either \\{TON} or~\\{WON}, and 20~Across looks like \\{_ND},
making it either \\{AND} or~\\{END}. So 15~Down is of the form~\\{A[TW][AE]}.
Again we find that there are two possibilities, either \\{ATE} or~\\{AWE}, and
we can't decide between them at the moment. In any case, we know that
15~Down ends with~\\E, so 20~Across is~\\{END}.

\begincrosswordsemantics
$$\crossword{%
\row{*H*A*S /*.*.*. }%
\row{*E L K /*. . . }%
\row{*A S I*D E / / }%
\row{*D O / O /*I*T }%
\row{ / /*S T*A R E }%
\row{*A*. E /*. O N }%
\row{*N O T /*E N D }%
}$$
\endcrosswordsemantics

Finally we come to the northeast corner. This corner is the most difficult of
the four, because the only foothold we have is that 4~Down looks like~\\{__E},
and almost all of the possibilities seem plausible at first. Upon careful
examination, however, we will see that only one of them will actually work. The
eight possibilities for 4~Down are \\{ALE},~\\{ATE}, \\{AWE}, \\{ICE}, \\{LIE},
\\{ODE}, \\{OWE}, and~\\{TOE}. We'll consider each of these separately.
Essentially we will try each possibility until we get stuck, and then backtrack
to try the next possibility.

The easiest possibility to eliminate is~\\{ICE}. Putting \\{ICE} at 4~Down
would make 8~Across look like \\{C__}, but none of the three-letter words in
the list begin with~\\C. So 4~Down cannot be~\\{ICE}.

If 4~Down is~\\{ALE}, then 8~Across is~\\{L__}, so it is either \\{LIE}
or~\\{LOT}. If it's \\{LIE}, then 5~Down must be~\\{_I}, which is no good.
If it's \\{LOT}, then 6~Down must be~\\{_T}, forcing it to be~\\{AT} (because
\\{IT} is already used). But then 4~Across is~\\{A_A}, which is impossible. So
4~Down can't be~\\{ALE}.

If 4~Down is~\\{ATE}, then 8~Across is~\\{T__}, so it must be \\{TAG},~\\{TEA},
\\{TOE}, or~\\{TON}. If it's \\{TAG}, then 5~Down must be~\\{_A}, which is a
problem. If it's \\{TEA}, then \\{_A} shows up at 6~Down this time---same
problem. If 8~Across is~\\{TOE}, then 6~Down is~\\{_E}, which means it must
be~\\{ME}. This makes 4~Across look like~\\{A_M}. The only choice is~\\{AIM},
but that puts \\{IO} at 5~Down, which is not a word. So \\{TOE} is no good for
8~Across. The last possibility for 8~Across is~\\{TON}, which would make
6~Down~\\{_N}, requiring~\\{IN} (since \\{AN} has already been used). Then
4~Across looks like \\{A_I}, which can't be filled. So 4~Down cannot
be~\\{ATE}.

If 4~Down is~\\{LIE}, then 4~Across looks like \\{L__}, so it must be~\\{LOT}
(because we just used~\\{LIE}). This means 5~Down is~\\{O_}, which means it
must be~\\{OH}; but then 8~Across looks like \\{IH_}, which doesn't work. So
4~Down can't be~\\{LIE}.

If 4~Down is~\\{ODE}, then 8~Across is~\\{D__}, making it~\\{DIN} (since
\\{DOT} is already used). Then 5~Down is an impossible~\\{_I}. So 4~Down cannot
be~\\{ODE}.

If 4~Down is~\\{OWE}, then 4~Across looks like \\{O__}, so it must be~\\{ODE}
(because we just used~\\{OWE}). Then 5~Down is~\\{D_}, but we've already
used~\\{DO}, which is the only such word in the list. So 4~Down can't
be~\\{OWE}.

If 4~Down is~\\{TOE}, then 8~Across is~\\{O__}, either \\{ODE} or~\\{OWE}. So
5~Down is either \\{_D} or~\\{_W}, both of which are impossible. So 4~Down
cannot be~\\{TOE}.

Therefore, the only possibility for 4~Down is~\\{AWE}. Phew!

Let's go back to the spaces we left blank earlier. We knew 15~Down was either
\\{ATE} or~\\{AWE}, but we didn't know which. Now that we've used \\{AWE}, we
see that 15~Down must be \\{ATE}, giving \\{TON} at 18~Across. And now that
we've used \\{ATE} there, we know 16~Across must be \\{ALE}, giving \\{LO} for
17~Down.

We have just four squares left. Let's consider 4~Across. It looks like \\{A__},
so the possibilities are \\{AGO},~\\{AIM}, \\{ALL}, \\{AND}, \\{ANT},
and~\\{ASH} (\\{ALE},~\\{ATE}, and~\\{AWE} have already been used). But \\{AGO}
would make 5~Down look like~\\{G_}, which is no good; \\{ALL}~would require
both 5~Down and 6~Down to be~\\{L_}, but \\{LO} is the only word like this (and
anyway it's already been used); \\{AND}~would need \\{D_} at 6~Down, but
\\{DO} has been used; and \\{ASH} would make 6~Down look like~\\{H_}, which
can't be filled. So there are really only two possibilities for 4~Across,
\\{AIM}~and~\\{ANT}.

The word at 8~Across looks like \\{W__}, so it's one of \\{WED},~\\{WHO},
\\{WIN}, \\{WON}, or~\\{WOO}. We see that \\{WED} needs \\{_D} at 6~Down, and
\\{WIN} needs \\{_I} at 5~Down, both of which are impossible. This narrows the
possibilities at 8~Across to \\{WHO},~\\{WON}, and~\\{WOO}.

Therefore, the second letter of 4~Across (the first letter of 5~Down) is either
\\I or~\\N, and the second letter of 8~Across (the second letter of 5~Down) is
either \\H or~\\O. So 5~Down is \\{IH},~\\{IO}, \\{NH}, or~\\{NO}; only \\{NO}
is a word in the list, so we fill in \\{NO} at 5~Down. This makes 4~Across
\\{ANT}, so 6~Down is~\\{TO} (the only~\\{T_} in the list), giving \\{WOO} at
8~Across.

The completed puzzle appears below.

\begincrosswordsemantics
$$\crossword{%
\row{*H*A*S /*A*N*T }%
\row{*E L K /*W O O }%
\row{*A S I*D E / / }%
\row{*D O / O /*I*T }%
\row{ / /*S T*A R E }%
\row{*A*L E /*T O N }%
\row{*N O T /*E N D }%
}\eqno\hbox{\qed}$$
\endcrosswordsemantics

}  % end \def_, \def\\

\bigbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Indiana Jones has made it through the deadly traps of an ancient
temple and has discovered ten treasures inside. Unfortunately, his knapsack is
too small to carry them all, so he must choose (wisely). He has made the
following estimates of the objects' weights and values. If his knapsack can
hold at most 20~pounds of treasure, which objects should he take to maximize
the value of his loot?
$$\hss\vbox{\offinterlineskip
\halign{\quad\strut#\hfil\quad&\vrule#&\quad\hfil\strut#\quad&&\hfil\strut#\quad\cr
Treasure&&Weight&Value\cr
\omit&height2pt&\omit&\omit\cr
\noalign{\hrule}
\omit&height2pt&\omit&\omit\cr
Crown of Atahualpa&&4 lb.&\$\phantom04,000\cr
Itzcoatl's Orb&&6 lb.&9,000\cr
Tablet of the Heavens&&7 lb.&7,000\cr
Golden Quetzal&&13 lb.&17,000\cr
Mask of the Ancients&&5 lb.&5,000\cr
}}\qquad\vbox{\offinterlineskip
\halign{\quad\strut#\hfil\quad&\vrule#&\quad\hfil\strut#\quad&&\hfil\strut#\quad\cr
Treasure&&Weight&Value\cr
\omit&height2pt&\omit&\omit\cr
\noalign{\hrule}
\omit&height2pt&\omit&\omit\cr
Key of Silver Light&&2 lb.&\$\phantom02,000\cr
Idol of Inti&&10 lb.&15,000\cr
Eternal Quipu&&5 lb.&8,000\cr
Goblet of Uxmal&&3 lb.&4,000\cr
Sacred Stone of Cuzco&&8 lb.&11,000\cr
}}\hss$$

\solution We might first try sorting the objects by value, and then choosing
the highest-value items one by one, so long as we still have room in the
knapsack. First we sort the treasures in descending order by value. (We'll put
the Goblet of Uxmal ahead of the Crown of Atahualpa, because they are have the
same value but the goblet weighs less.)

$$\vbox{\offinterlineskip
\halign{\quad\strut#\hfil\quad&\vrule#&\quad\hfil\strut#\quad&&\hfil\strut#\quad\cr
Treasure&&Weight&Value\cr
\omit&height2pt&\omit&\omit\cr
\noalign{\hrule}
\omit&height2pt&\omit&\omit\cr
Golden Quetzal&&13 lb.&\$17,000\cr
Idol of Inti&&10 lb.&15,000\cr
Sacred Stone of Cuzco&&8 lb.&11,000\cr
Itzcoatl's Orb&&6 lb.&9,000\cr
Eternal Quipu&&5 lb.&8,000\cr
Tablet of the Heavens&&7 lb.&7,000\cr
Mask of the Ancients&&5 lb.&5,000\cr
Goblet of Uxmal&&3 lb.&4,000\cr
Crown of Atahualpa&&4 lb.&4,000\cr
Key of Silver Light&&2 lb.&2,000\cr
}}$$

Now let's fill the knapsack. We'll take the Golden Quetzal, since it has the
highest value. Since the Golden Quetzal weighs 13~pounds, we have 7~pounds of
capacity left. We cannot take either of the next two items in the list, the
Idol of Inti or the Sacred Stone of Cuzco, because they weigh too much. So
we'll take Itzcoatl's Orb, which weighs 6~pounds. This gives us 19~pounds,
worth~\$26,000. Since there is no 1-pound item, this is the best we can do by
this method. (Such a method, in which we simply take the ``best'' available
choice at each step without considering how our choice will affect future
options, is called a ``greedy algorithm.'')

But we can do better if we modify the method slightly. We weren't able to fill
our knapsack because there is no 1-pound item to take. So let's try the same
method, except that we will skip an item if it would give us a total of exactly
19~pounds. (We'll call this approach the ``modified greedy algorithm.'') As
before we take the Golden Quetzal and skip the Idol of Inti and the Sacred
Stone of Cuzco. This time we will also skip Itzcoatl's Orb and take the Eternal
Quipu instead, giving us 18~pounds so far. Then we still have room to take the
Key of Silver Light. This solution gives us a full 20~pounds of treasure
worth~\$27,000.

However, there is another way to sort the treasure. Instead of sorting by value
with no regard to weight, we can sort by value per pound. (As before, if two
objects have the same value per pound, let's put the lighter one first.)
Sorting the treasures in this way gives the list on the following page.

\vfill\eject

$$\vbox{\offinterlineskip
\halign{\quad\strut#\hfil\quad&\vrule#&\quad\hfil\strut#\quad&\hfil\strut#\quad&\hfil\strut#\hfil\quad\cr
Treasure&&Weight&Value&Value per pound\cr
\omit&height2pt&\omit&\omit\cr
\noalign{\hrule}
\omit&height2pt&\omit&\omit\cr
Eternal Quipu&&5 lb.&\$\phantom08,000&\$1,600/lb.\cr
Itzcoatl's Orb&&6 lb.&9,000&\phantom\$1,500/lb.\cr
Idol of Inti&&10 lb.&15,000&\phantom\$1,500/lb.\cr
Sacred Stone of Cuzco&&8 lb.&11,000&\phantom\$1,375/lb.\cr
Goblet of Uxmal&&3 lb.&4,000&\phantom\$1,333/lb.\cr
Golden Quetzal&&13 lb.&17,000&\phantom\$1,308/lb.\cr
Key of Silver Light&&2 lb.&2,000&\phantom\$1,000/lb.\cr
Crown of Atahualpa&&4 lb.&4,000&\phantom\$1,000/lb.\cr
Mask of the Ancients&&5 lb.&5,000&\phantom\$1,000/lb.\cr
Tablet of the Heavens&&7 lb.&7,000&\phantom\$1,000/lb.\cr
}}$$

If we apply the greedy algorithm to this list, we begin by taking the Eternal
Quipu and Itzcoatl's Orb, bringing us to a total of 11~pounds. We do not have
enough room for the Idol of Inti, but we can take the Sacred Stone of Cuzco. We
must stop here, because we have reached 19~pounds; the value of our treasure
is~\$28,000.

This is an improvement upon the solutions we obtained earlier. Perhaps we can
improve even further if we try the modified greedy algorithm. We choose the
Eternal Quipu and Itzcoatl's Orb and skip the Idol of Inti, as before, but now
we skip the Sacred Stone of Cuzco as well, because that would give us a total
of 19~pounds. Instead we take the Goblet of Uxmal, the Key of Silver Light, and
the Crown of Atahualpa. We have filled our knapsack with 20~pounds, but when we
calculate the value it turns out that we have done worse; we have only
\$27,000.

The greedy algorithm and the modified greedy algorithm are simple methods to
use, and they usually work well to get an {\it approximation\/} of the best
solution, but neither of these methods is {\it guaranteed\/} to give the best
solution. In this problem there is a better solution than any of the four we
have found so far.

Let's go about this in a very systematic way. We have already found a solution
worth \$28,000. If we are going to improve upon this, we must include in our
solution at least one of the five highest-value items (the Golden Quetzal, the
Idol of Inti, the Sacred Stone of Cuzco, Itzcoatl's Orb, or the Eternal Quipu)
because the other five items are worth only \$22,000 in all. So we will
consider the five high-value items separately from the five low-value items.

The low-value items are listed below, sorted in ascending order by weight
(and, incidentally, also by value).

$$\vbox{\offinterlineskip
\halign{\quad\strut#\hfil\quad&\vrule#&\quad\hfil\strut#\quad&&\hfil\strut#\quad\cr
Treasure&&Weight&Value\cr
\omit&height2pt&\omit&\omit\cr
\noalign{\hrule}
\omit&height2pt&\omit&\omit\cr
Key of Silver Light&&2 lb.&\$2,000\cr
Goblet of Uxmal&&3 lb.&4,000\cr
Crown of Atahualpa&&4 lb.&4,000\cr
Mask of the Ancients&&5 lb.&5,000\cr
Tablet of the Heavens&&7 lb.&7,000\cr
}}$$

We will make a list of ways to form various weights from these low-value
treasures. It is easy to see that the only way to make 2~pounds is to take the
Key of Silver Light. Similarly, the only way to make 3~pounds is to take the
Goblet of Uxmal, and the only way to make 4~pounds is to take the Crown of
Atahualpa. To make 5~pounds, however, we have a choice: either we can take the
Mask of the Ancients alone, or we can take the Key of Silver Light and the
Goblet of Uxmal. In general, when our aim is to form a total weight of
$n$~pounds, we must also consider all of the possible ways to write $n$ as a
sum of smaller numbers (out of 2,~3, 4, 5, and~7). Following this approach, we
construct the table on the next page.

\vfill\eject

$$\vbox{\offinterlineskip
\halign{\quad\hfil\strut#&\quad\hfil\strut#\hfil&\quad\strut#\hfil&\quad\hfil\strut#\quad\cr
Weight&As a sum&Treasures&Value\cr
\noalign{\vskip2pt\hrule\vskip2pt}
2 lb.&2&Key&\$\phantom02,000\cr
\noalign{\vskip2pt\hrule\vskip2pt}
3 lb.&3&Goblet&4,000\cr
\noalign{\vskip2pt\hrule\vskip2pt}
4 lb.&4&Crown&4,000\cr
\noalign{\vskip2pt\hrule\vskip2pt}
5 lb.&5&Mask&5,000\cr
	&$2+3$&Key, goblet&6,000\cr
\noalign{\vskip2pt\hrule\vskip2pt}
6 lb.&$2+4$&Key, crown&6,000\cr
\noalign{\vskip2pt\hrule\vskip2pt}
7 lb.&7&Tablet&7,000\cr
	&$2+5$&Key, mask&7,000\cr
	&$3+4$&Goblet, crown&8,000\cr
\noalign{\vskip2pt\hrule\vskip2pt}
8 lb.&$3+5$&Goblet, mask&9,000\cr
\noalign{\vskip2pt\hrule\vskip2pt}
9 lb.&$2+7$&Key, tablet&9,000\cr
	&$4+5$&Crown, mask&9,000\cr
	&$2+3+4$&Key, goblet, crown&10,000\cr
\noalign{\vskip2pt\hrule\vskip2pt}
10 lb.&$3+7$&Goblet, tablet&11,000\cr
	&$2+3+5$&Key, goblet, mask&11,000\cr
\noalign{\vskip2pt\hrule\vskip2pt}
11 lb.&$4+7$&Crown, tablet&11,000\cr
	&$2+4+5$&Key, crown, mask&11,000\cr
\noalign{\vskip2pt\hrule\vskip2pt}
12 lb.&$5+7$&Mask, tablet&12,000\cr
	&$2+3+7$&Key, goblet, tablet&13,000\cr
	&$3+4+5$&Goblet, crown, mask&13,000\cr
\noalign{\vskip2pt\hrule\vskip2pt}
13 lb.&$2+4+7$&Key, crown, tablet&13,000\cr
\noalign{\vskip2pt\hrule\vskip2pt}
14 lb.&$2+5+7$&Key, mask, tablet&14,000\cr
	&$3+4+7$&Goblet, crown, tablet&15,000\cr
	&$2+3+4+5$&Key, goblet, crown, mask&15,000\cr
\noalign{\vskip2pt\hrule\vskip2pt}
15 lb.&$3+5+7$&Goblet, mask, tablet&16,000\cr
\noalign{\vskip2pt\hrule\vskip2pt}
16 lb.&$4+5+7$&Crown, mask, tablet&16,000\cr
	&$2+3+4+7$&Key, goblet, crown, tablet&17,000\cr
\noalign{\vskip2pt\hrule\vskip2pt}
17 lb.&$2+3+5+7$&Key, goblet, mask, tablet&18,000\cr
\noalign{\vskip2pt\hrule\vskip2pt}
18 lb.&$2+4+5+7$&Key, crown, mask, tablet&18,000\cr
\noalign{\vskip2pt\hrule\vskip2pt}
19 lb.&$3+4+5+7$&Goblet, crown, mask, tablet&19,000\cr
\noalign{\vskip2pt\hrule\vskip2pt}
21 lb.&$2+3+4+5+7$&Key, goblet, crown, mask, tablet&22,000\cr
}}$$

To use this table, we will consider some combination of the high-value
treasures, see how much room is left in the knapsack, and then find the best
combination of low-value treasures in the table above that will fit. For
example, if we choose the Sacred Stone of Cuzco and Itzcoatl's Orb as our
high-value treasures, which together weigh 14~pounds, we will have 6~pounds of
capacity remaining. Looking at the ``6~lb.''\ row and the rows above it in this
table, we see that our best option is to take the Key of Silver Light and the
Crown of Atahualpa (or, equivalently, the Key of Silver Light and the Goblet of
Uxmal---perhaps this is actually a better choice, since it gives us the same
value with less weight).

Proceeding in this way, we can find the best collection of treasures to take by
considering all possible combinations of the high-value items. Of course, we
can safely ignore those that put us overweight: the Golden Quetzal and the Idol
of Inti together weigh 23~pounds, and the Golden Quetzal and the Sacred Stone
of Cuzco together weigh 21~pounds. Furthermore, any combination of three or
more high-value items will weigh more than 20~pounds (except the three lightest
ones, the Sacred Stone of Cuzco, Itzcoatl's Orb, and the Eternal Quipu, which
weigh 19~pounds together). These impossible combinations of high-value items
are omitted from the following table.

$$\def\B{$\bullet$}\vbox{\offinterlineskip
\halign{%
	\quad\hfil\strut#\hfil&\quad\hfil\strut#\hfil&\quad\hfil\strut#\hfil
	&\quad\hfil\strut#\hfil&\quad\hfil\strut#\hfil\quad&\vrule#%
	&\quad\hfil\strut#&\quad\strut#\hfil&\quad\hfil\strut#\quad\cr
Quetzal&Idol&Stone&Orb&Quipu&&Remaining&Low-value items&\llap{Total value}\cr
\omit&\omit&\omit&\omit&\omit&height2pt\cr
\noalign{\hrule}
\omit&\omit&\omit&\omit&\omit&height2pt\cr
\B&  &  &  &  &&7 lb.&Goblet, crown&\$25,000\cr
  &\B&  &  &  &&10 lb.&Goblet, tablet&26,000\cr
  &  &\B&  &  &&12 lb.&Key, goblet, tablet&24,000\cr
  &  &  &\B&  &&14 lb.&Goblet, crown, tablet&24,000\cr
  &  &  &  &\B&&15 lb.&Goblet, mask, tablet&24,000\cr
\omit&\omit&\omit&\omit&\omit&height2pt\cr
\noalign{\hrule}
\omit&\omit&\omit&\omit&\omit&height2pt\cr
\B&  &  &\B&  &&1 lb.&\it(None)&26,000\cr
\B&  &  &  &\B&&2 lb.&Key&27,000\cr
  &\B&\B&  &  &&2 lb.&Key&28,000\cr
  &\B&  &\B&  &&4 lb.&Crown&28,000\cr
  &\B&  &  &\B&&5 lb.&Key, goblet&29,000\cr
\omit&\omit&\omit&\omit&\omit&height2pt\cr
\noalign{\hrule}
\omit&\omit&\omit&\omit&\omit&height2pt\cr
  &  &\B&\B&  &&6 lb.&Key, crown&26,000\cr
  &  &\B&  &\B&&7 lb.&Goblet, crown&27,000\cr
  &  &  &\B&\B&&9 lb.&Key, goblet, crown&27,000\cr
  &  &\B&\B&\B&&1 lb.&\it(None)&28,000\cr
}}$$

From this we see that the best choice is to take the Idol of Inti, the Eternal
Quipu, the Key of Silver Light, and the Goblet of Uxmal, which weigh 20~pounds
together and have a total value of~\$29,000. Moreover this solution is
{\it unique\/}: there is only one best solution.

(With the particular numbers used in this problem, it turns out that we would
have found this optimal solution by using the greedy algorithm based on value
per pound if we would have broken ties by putting the {\it heavier\/} item
first rather than the lighter one. But this isn't a general rule that will
always give the best possible solution.) \qed

\nobreak\medskip

\noindent[\thinspace This problem is an example of what computer scientists
call the {\it 0--1~knapsack problem}, so called because each type of item is to
be put into the knapsack either 0~times or 1~time. The general version of the
knapsack problem allows several copies of each item to be put in the knapsack
(for example, perhaps Indiana Jones is buying donuts to put in his knapsack and
must decide how many chocolate donuts, how many glazed donuts, and how many
strawberry donuts to buy); sometimes fractional parts of items are allowed. The
knapsack problem has many practical applications; it shows up whenever choices
have to be made because of a restriction on some kind of capacity. However, it
is a hard problem to solve exactly. It is believed, but not known for certain,
that there is no efficient method that will always give the best possible
solution for the knapsack problem.\thinspace]

\bigbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (``Cubes Cubed,'' {\it Thinking Mathematically}, page~36.)\enspace
I have eight cubes. Two of them are painted red, two white, two blue and two
yellow but otherwise they are indistinguishable. I wish to assemble them into
one large cube with each colour appearing on each face. In how many ways can I
assemble the cube?

\solution The answer to this question depends greatly on the way we choose to
decide whether two assemblages of the small cubes are in fact {\it different}.
One possibility is to say that two assemblages are the same if one of them can
be rotated somehow (in three dimensions) to get the other, and different
otherwise. Under this definition of {\it different}, we do not get a different
arrangement of the small cubes if we simply rotate everything by~$90^\circ$,
for example. This seems to be a sensible definition, and it is the one we will
use here.

Since there are eight small cubes, the large cube must have dimensions
$2\times2\times2$, that~is, two small cubes on each edge. Hence each small cube
occupies one of the eight corners of the large cube, and so each small cube
appears on three faces of the larger cube. The large cube has six faces, of
course, so in order to have each color on each face the two small cubes of any
one color must be located at diagonally opposite corners of the large cube.

This means that the arrangement of the small cubes is completely determined
once we have arranged four cubes for one of the faces. For instance, if we
arrange four cubes, one of each color, to make the bottom layer of the large
cube, then we are forced to put the cubes in the top layer so that the blue
cube in the top layer is diagonally opposite the blue cube in the bottom layer
(and the same for the other colors).

For example, consider the following arrangement for the bottom layer, seen from
above.
$$\fig{homework-2-sol-cube-rbyw-layer.mps}$$
This arrangement forces the top layer to be as shown below:
$$\fig{homework-2-sol-cube-ywrb-layer.mps}$$
So the large cube as a whole looks like the following. (In this picture the
corners of the cube are colored to indicate the colors of the small cubes
located there, and the bottom layer is drawn with heavy lines.)
$$\fig{homework-2-sol-cube-rbyw-bottom.mps}$$

Therefore we can list all of the possible assemblages of the small cubes by
simply listing all the ways to arrange four cubes in the bottom layer. Since we
have decided (in our definition of {\it different\/}) that we can freely rotate
a cube without changing it, let's draw the bottom layer so that it always has
the red cube on the left side. We can list the possibilities for the bottom
layer by noting that the cube opposite the red one can be either white, blue,
or yellow, and then the other two positions can be taken by the remaining two
cubes in either order. (The order of these is important, because switching
their order cannot be accomplished by rotation.)

So we have the following six possibilities for the bottom layer:
$$\matrix{%
\midfig{homework-2-sol-cube-rbwy-layer.mps}&%
\midfig{homework-2-sol-cube-rwby-layer.mps}&%
\midfig{homework-2-sol-cube-rbyw-layer.mps}\cr
\noalign{\medskip}
\midfig{homework-2-sol-cube-rywb-layer.mps}&%
\midfig{homework-2-sol-cube-rybw-layer.mps}&%
\midfig{homework-2-sol-cube-rwyb-layer.mps}\cr}$$
These correspond to the following arrangements for the large cube (the bottom
layer is drawn with heavy lines):
$$\hss\matrix{%
\midfig{homework-2-sol-cube-rbwy-bottom.mps}&%
\midfig{homework-2-sol-cube-rwby-bottom.mps}&%
\midfig{homework-2-sol-cube-rbyw-bottom.mps}\cr
\noalign{\medskip}
\midfig{homework-2-sol-cube-rywb-bottom.mps}&%
\midfig{homework-2-sol-cube-rybw-bottom.mps}&%
\midfig{homework-2-sol-cube-rwyb-bottom.mps}\cr}\hss$$

How can we tell when two arrangements of these are the same? Well, if we can
identify a face of one large cube that looks the same as a face of another
large cube, the two cubes must be the same (because once we have decided what
one face looks like, we have determined the entire arrangement). If we look at
the top face of the first cube above, we see that the colors go
``red--yellow--white--blue'' (starting at red and going around
counterclockwise). As it turns out, we can find a face with this sequence of
colors on all six of the arrangements! This is illustrated below. (Remember
that we are going around the face in the clockwise direction, imagining that we
are holding the cube so that the face in question is facing toward us. For the
bottom face and the two faces on the back side, this will appear to be the
counterclockwise direction in these pictures.)
$$\hss\matrix{%
\midfig{homework-2-sol-cube-rbwy-top.mps}&%
\midfig{homework-2-sol-cube-rwby-side.mps}&%
\midfig{homework-2-sol-cube-rbyw-side.mps}\cr
\noalign{\medskip}
\midfig{homework-2-sol-cube-rywb-bottom.mps}&%
\midfig{homework-2-sol-cube-rybw-side.mps}&%
\midfig{homework-2-sol-cube-rwyb-side.mps}\cr}\hss$$

Therefore there is essentially only one way to arrange the four small cubes
into one large cube so that each color appears on each face. \qed

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bye
