%  Homework assignment 2
%  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

\font\titlefont=cmbx12
\font\smfont=cmr8

\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=cmr12

\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\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}
\smallskip
\centerline{Assigned Monday, January~25, 2010. Due Monday, February~1, 2010.}

\bigskip

\noindent Work at least {\bf FOUR} of the following problems. All problems are
of equal weight. If you submit solutions for more than four problems, you will
get credit for your best four.

You are welcome to work with other students, but the solutions you hand~in
should be written in your own words. You are not allowed to see the paper
another student is going to hand~in. If you do collaborate with other students,
list their names. If you use other sources, cite them. Give credit where credit
is due. See the syllabus for more information about academic integrity.

Hints are encrypted with a {\it Caesar cipher}, in which each letter is
replaced by the letter three places ahead in the alphabet, wrapping around to
the beginning if necessary. For example, the letter~{\it A\/} is encrypted
as~{\it D}, and {\it Y\/}~is encrypted as~{\it B}. To decrypt the hints, move
each letter backward three places.

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

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

\hint Wkhuh duh wkluwb-ilyh iuhh kharplqrhv lq doo. Zkdw lv wkhlu wrwdo duhd?
Zkdw glphqvlrqv frxog d uhfwdqjoh zlwk wklv duhd kdyh? Wub frorulqj wkh vtxduhv
ri wkh kharplqrhv dv li wkhb zhuh fxw rxw ri d fkhfnhuerdug, dqg wkhq
fodvvliblqj wkh kharplqrhv lqwr wzr jurxsv edvhg rq wklv frorulqj.

\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.

\itemhint Rqh hasodqdwlrq pdb dssob wr vhyhudo kharplqrhv. Fryhu wkh hdvlhu
fdvhv iluvw.

\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?

\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?

\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.

\hint Wklqn derxw erwk uhiohfwlrq dqg urwdwlrq vbpphwub.

\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!

\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$$

\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$$

\noskiphint Eh fduhixo, dqg gr qrw pdnh xqirxqghg dvvxpswlrqv. Frqvlghu doo
srvvlelolwlhv. Lw pdb khos wr frqvlghu vpdoohu nqdsvdfnv. Iru hadpsoh, zkdw
zrxog eh wkh ehvw zdb wr iloo d nqdsvdfn wkdw fdq krog whq srxqgv?

\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?

\hint Vhh wkh errn iru vrph vxjjhvwlrqv li brx jhw vwxfn. Rqh lpsruwdqw wklqj
wr gr lv wr ghflgh zkdw lv phdqw eb wkh zrug ``gliihuhqw.''

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

\bye
