%  Homework assignment 1 solutions
%  21-110: Problem Solving in Recreational Mathematics, spring 2010
%  Assigned: Wednesday, January 13, 2010. Due: Wednesday, January 20, 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

% copied from the TeXbook, pages 413--415
\font\eightrm=cmr8   \font\sixrm=cmr6
\font\eighti=cmmi8   \font\sixi=cmmi6
\font\eightsy=cmsy8  \font\sixsy=cmsy6
\font\eightbf=cmbx8  \font\sixbf=cmbx6
\font\eighttt=cmtt8
\font\eightit=cmti8
\font\eightsl=cmsl8
\newskip\ttglue
\def\eightpoint{\def\rm{\fam0\eightrm}% switch to 8-point type
  \textfont0=\eightrm \scriptfont0=\sixrm \scriptscriptfont0=\fiverm
  \textfont1=\eighti  \scriptfont1=\sixi  \scriptscriptfont1=\fivei
  \textfont2=\eightsy \scriptfont2=\sixsy \scriptscriptfont2=\fivesy
  \textfont3=\tenex   \scriptfont3=\tenex \scriptscriptfont3=\tenex
  \textfont\itfam=\eightit  \def\it{\fam\itfam\eightit}%
  \textfont\slfam=\eightsl  \def\sl{\fam\slfam\eightsl}%
  \textfont\ttfam=\eighttt  \def\tt{\fam\ttfam\eighttt}%
  \textfont\bffam=\eightbf  \scriptfont\bffam=\sixbf
   \scriptscriptfont\bffam=\fivebf  \def\bf{\fam\bffam\eightbf}%
  \tt \ttglue=.5em plus.25em minus.15em
  \normalbaselineskip=9pt
  \setbox\strutbox=\hbox{\vrule height7pt depth2pt width0pt}%
  \let\sc=\sixrm  \let\big=\eightbig  \normalbaselines\rm}

\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\hint#1\par{\nobreak\medskip\noindent{\it Hint:\/}\enspace#1\par}
\def\itemhint#1\par{\nobreak\medskip\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}}

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

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

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

\problem Find my office. Sign your name on the sheet posted outside my office
door.

\solution My office is in the Physical Plant Building (PPB), room~342. One way
to get there is to go to Wean Hall, take the elevator down to the first floor,
exit the building, follow the sidewalk across the street and around the corner
of the FMS~Building, and cross the plaza to the southwest corner. My office
door is just inside the glass doors. \qed

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

\problem ``How many children do you have, and what are their ages?'' asks the
census taker.

The mother answers, ``I have three children. The product of their ages is~36,
and the sum of their ages is the same as my house number.''

The census taker looks at the house number, thinks for a moment, and responds,
``I'm sorry, but I need more information.''

``My oldest child likes chocolate ice cream,'' says the mother.

``Thank you,'' replies the census taker. ``I have all the information I
require.''

How old are the children?

\solution There are eight possible ways for three children to have ages whose
product is~36:
$$\vbox{\offinterlineskip
\halign{\strut\quad#\hfil\quad&\vrule#&\strut\quad\hfil#\hfil\quad\cr
\hfil Ages&&Sum\cr
\omit&height2pt\cr
\noalign{\hrule}
\omit&height2pt\cr
1, 1, 36&&38\cr
1, 2, 18&&21\cr
1, 3, 12&&16\cr
1, 4, 9&&14\cr
1, 6, 6&&13\cr
2, 2, 9&&13\cr
2, 3, 6&&11\cr
3, 3, 4&&10\cr
}}$$
We don't know the sum of the ages, but we {\it do\/} know that the census taker
knows the sum (she looked at the house number) and yet she is still unable to
determine the three ages. This must be because the house number is~13;
otherwise, knowing the sum would be enough information. So the ages of the
children are either 1,~6, and~6 or 2,~2, and~9. The mother's statement that her
{\it oldest child\/} likes chocolate ice cream rules out the possibility that
the ages are 1,~6, and~6, because in that case there would not be a single
oldest child. Hence we conclude that the ages of the children are 2,~2, and~9.
\qed

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

\problem (``Ins and Outs,'' {\it Thinking Mathematically}, page~175.)\enspace
Take a strip of paper and fold it in half several times in the same fashion as
in {\it Paper Strip\/} (page~4). Unfold it and observe that some of the creases
are IN and some are OUT. For example, three folds produce the sequence
$$\rm in\quad in\quad out\quad in\quad in\quad out\quad out$$
What sequence would arise from 10~folds (if that many were possible)?

\solution It is helpful to carefully and precisely describe the folding
procedure and what is meant by ``in'' and ``out.'' {\it Paper Strip\/}
describes the method of folding as follows: ``Imagine taking the ends in your
hands and placing the right hand end on top of the left. Now press the strip
flat so that it is folded in half and has a crease. Repeat the whole operation
on the new strip\dots.'' After folding the strip in half a number of times, the
strip should be unfolded by exactly undoing the folding process (this is
important to note, because different unfolding methods can result in different
sequences of creases).

Once the strip is unfolded, the creases can be classified as either ``in'' or
``out.'' An ``in'' crease is one that, when viewed from the ``top'' (as this
word is used in the description of the folding method), makes an angle of less
than~$180^\circ$, while an ``out'' crease makes an angle of more
than~$180^\circ$. Equivalently, an ``in'' crease is one that tends to make the
adjacent segments of the paper strip come together by folding toward the
viewer, while an ``out'' crease tends to make them fold away from the viewer.

We discussed {\it Paper Strip\/} in class, which asks for the number of creases
resulting from a number of folds. We found that after $n$~folds the strip has
$(2^n-1)$~creases. For example, after 3~folds there are $2^3-1=7$~creases, and
after 10~folds there would be $2^{10}-1=1023$~creases.

In reality, it is impossible to fold a paper strip 10~times. (Actually, this is
not true---in~2002, Britney Gallivan, a California high school student,
succeeded in folding a very long strip of very thin paper in half 12~times, and
in the course of studying the problem developed a mathematical theory to
describe the limits of paper folding.) In any case, a sequence of 1023~``ins''
or~``outs'' is not a very helpful answer to this question and is easy to get
lost in. So we would like to identify a pattern in the creases and describe the
pattern instead.

After some experimentation, a pattern emerges. It appears that the sequence of
creases after $n$~folds consists of the sequence of creases after
$(n-1)$~folds; followed by an ``in''~crease; followed by the sequence of
creases after $(n-1)$~folds, reversed and with all ``ins'' changed to~``outs''
and vice versa. For example, after one fold, the sequence is
$$\rm in;$$
after two folds,
$$\rm\underline{in}\quad in\quad\underline{out};$$
after three folds,
$$\rm\underline{\underline{in}\quad in\quad\underline{out}}\quad in\quad
	\underline{\underline{in}\quad out\quad\underline{out}};$$
and after four folds,
$$\rm\underline{\underline{\underline{in}\quad in\quad\underline{out}}\quad
	in\quad\underline{\underline{in}\quad out\quad\underline{out}}}\quad in\quad
	\underline{\underline{\underline{in}\quad in\quad\underline{out}}\quad
	out\quad\underline{\underline{in}\quad out\quad\underline{out}}}.$$

Because of their symmetry, it turns out that reversing one of these sequences
and changing all ``ins'' to~``outs'' and vice versa is the same as simply
changing the middle ``in'' to an~``out.'' So this pattern can also be described
in a slightly different way. The sequence of creases after $n$~folds consists
of the sequence of creases after $(n-1)$~folds; followed by an ``in''~crease;
followed by the sequence of creases after $(n-1)$~folds again, with the middle
``in''~crease changed to an ``out''~crease.

Why does this pattern appear? I had to spend quite a bit of time folding and
refolding paper to understand what was happening, but in the end I came up with
the following explanation.

Suppose we start with the strip all folded. The sequence of creases we see
(no creases) is the same as if the strip had not been folded at all. Next we
{\it reveal\/} the last fold by undoing one fold. What we see now is a single
``in''~crease, as if a strip had been folded once and then unfolded. Revealing
another fold shows the sequence ``in,~in,~out,'' which is what we would see in
a strip that had been folded twice and then unfolded. In general, adding one
more fold to a paper strip before unfolding it is like doing one more such
``revealing'' step to a strip that is initially folded many times.

Now, each ``revealing'' step mirrors all of the previously existing creases
(doubling their number, reversing their order, and also changing all
``in''~creases to ``out''~creases), and adds a new ``in''~crease in the middle.
This explains the pattern we observed.

% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % %
%                                                                             %
%  The following section describes an idea that was beautiful but wrong, so   %
%  it has been removed.                                                       %
%                                                                             %
% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % %

%{
%\font\digitsfont=cmtt12 at 17pt
%\def\0{\mathop{\hbox{\digitsfont0}}\limits}
%\def\1{\mathop{\hbox{\digitsfont1}}\limits}
%A third way to describe the pattern of creases involves the binary number system.
%In this system, numbers are written as sums of powers of~2 (the powers of~2 are
%$2^0=1$, $2^1=2$, $2^2=4$, $2^3=8$, and so on), never using any power of~2 more
%than once. To write a number~$k$ in binary, first make a table of the powers
%of~2:
%$$\vbox{\halign{\hfil$#$\hfil&&\quad\hfil$#$\hfil\cr
%	2^0&2^1&2^2&2^3&2^4&2^5&2^6&2^7&2^8&2^9&2^{10}&2^{11}&2^{12}&2^{13}&2^{14}&2^{15}&\ldots\cr
%	1&2&4&8&16&32&64&128&256&512&1024&2048&4096&8192&16384&32768&\ldots\cr}}$$
%Then find the largest power of~2 that is no larger than the number~$k$. Write
%this power of~2 as the first term of the sum. Subtract this power of~2 from the
%number~$k$, find the largest power of~2 that is no larger than the number that
%remains, and repeat until there is no remainder. For example, the number~41 is
%the sum
%$$41=\underbrace{32}_{2^5}+\underbrace8_{2^3}+\underbrace1_{2^0},$$
%and the number~21110 is the sum
%$$21110=\underbrace{16384}_{2^{14}}+\underbrace{4096}_{2^{12}}
%	+\underbrace{512}_{2^9}+\underbrace{64}_{2^6}+\underbrace{32}_{2^5}
%	+\underbrace{16}_{2^4}+\underbrace4_{2^2}+\underbrace2_{2^1}.$$
%Usually these sums are written in a more compact form using the digits {\tt1}
%and~{\tt0}. To do this, simply write the digit~{\tt1} for each power of~2 used
%in the sum, and the digit~{\tt0} for each power of~2 not used (with the higher
%powers of~2 toward the left). So the number~41 is written in binary as
%{\tt101001}, indicating
%$$\1^{2^5}\quad\0^{2^4}\quad\1^{2^3}\quad\0^{2^2}\quad\0^{2^1}\quad\1^{2^0},$$
%and 21110 is written in binary as {\tt101001001110110}, indicating
%$$\1^{2^{14}}\quad\0^{2^{13}}\quad\1^{2^{12}}\quad\0^{2^{11}}\quad\0^{2^{10}}
%	\quad\1^{2^9}\quad\0^{2^8}\quad\0^{2^7}\quad\1^{2^6}\quad\1^{2^5}\quad
%	\1^{2^4}\quad\0^{2^3}\quad\1^{2^2}\quad\1^{2^1}\quad\0^{2^0}.$$
%
%What does this have to do with the pattern of creases in a strip of folded
%paper? Well, some numbers are written in binary with an odd number of~{\tt1}'s
%(for example, 41~is written with three~{\tt1}'s), while others are written with
%an even number of~{\tt1}'s (for example, 21110~is written with eight~{\tt1}'s).
%It turns out that to determine whether the $k$th~crease in a strip of paper is
%``in'' or~``out,'' we just need to know whether the number~$k$, when written in
%binary, uses an even or odd number of~{\tt1}'s. If $k$ uses an odd number
%of~{\tt1}'s, the $k$th~crease will be an ``in''~crease, and if $n$ uses an even
%number of~{\tt1}'s, the $k$th crease will be an ``out''~crease. The number of
%times the paper was folded to make the creases is irrelevant! So the
%41st~crease (from the left) will always be an ``in''~crease, and the
%21110th~crease will always be an ``out''~crease (as long as there are at least
%this many creases, of course). The advantage of this description is that it can
%be quickly determined whether a particular crease is ``in'' or~``out'' without
%needing to generate the entire sequence of ``ins'' and~``outs.'' Can you see
%why this works? (It's not obvious.) The number of~{\tt1}'s used in a binary
%representation is often called the {\it Hamming weight}, named after the
%20th-century American mathematician Richard Hamming.
%
%}  % end \font\digitsfont, \def\0, \def\1

Just for completeness, here is the sequence of creases produced by 10~folds.
(This was generated by a computer program, not by hand!)

{\nobreak\medskip\narrower\eightpoint

\noindent in in out in in out out in in in out out in out out in in in out in
in out out out in in out out in out out in in in out in in out out in in in out
out in out out out in in out in in out out out in in out out in out out in in
in out in in out out in in in out out in out out in in in out in in out out out
in in out out in out out out in in out in in out out in in in out out in out
out out in in out in in out out out in in out out in out out in in in out in in
out out in in in out out in out out in in in out in in out out out in in out
out in out out in in in out in in out out in in in out out in out out out in in
out in in out out out in in out out in out out out in in out in in out out in
in in out out in out out in in in out in in out out out in in out out in out
out out in in out in in out out in in in out out in out out out in in out in in
out out out in in out out in out out in in in out in in out out in in in out
out in out out in in in out in in out out out in in out out in out out in in in
out in in out out in in in out out in out out out in in out in in out out out
in in out out in out out in in in out in in out out in in in out out in out out
in in in out in in out out out in in out out in out out out in in out in in out
out in in in out out in out out out in in out in in out out out in in out out
in out out out in in out in in out out in in in out out in out out in in in out
in in out out out in in out out in out out in in in out in in out out in in in
out out in out out out in in out in in out out out in in out out in out out out
in in out in in out out in in in out out in out out in in in out in in out out
out in in out out in out out out in in out in in out out in in in out out in
out out out in in out in in out out out in in out out in out out in in in out
in in out out in in in out out in out out in in in out in in out out out in in
out out in out out in in in out in in out out in in in out out in out out out
in in out in in out out out in in out out in out out in in in out in in out out
in in in out out in out out in in in out in in out out out in in out out in out
out out in in out in in out out in in in out out in out out out in in out in in
out out out in in out out in out out in in in out in in out out in in in out
out in out out in in in out in in out out out in in out out in out out in in in
out in in out out in in in out out in out out out in in out in in out out out
in in out out in out out out in in out in in out out in in in out out in out
out in in in out in in out out out in in out out in out out out in in out in in
out out in in in out out in out out out in in out in in out out out in in out
out in out out out in in out in in out out in in in out out in out out in in in
out in in out out out in in out out in out out in in in out in in out out in in
in out out in out out out in in out in in out out out in in out out in out out
in in in out in in out out in in in out out in out out in in in out in in out
out out in in out out in out out out in in out in in out out in in in out out
in out out out in in out in in out out out in in out out in out out out in in
out in in out out in in in out out in out out in in in out in in out out out in
in out out in out out in in in out in in out out in in in out out in out out
out in in out in in out out out in in out out in out out out in in out in in
out out in in in out out in out out in in in out in in out out out in in out
out in out out out in in out in in out out in in in out out in out out out in
in out in in out out out in in out out in out out

\nobreak\medskip}  % end \narrower

\noindent It should be clear why this is not the ideal form of the answer to
this question. \qed

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

\problem (Exercise~1.5 from {\it Problem Solving Through Recreational
Mathematics}, page~27.)\enspace Six players---Pietrovich, Cavelli, St.~Jacques,
Smith, Lord Bottomly, and Fernandez---are competing in a chess tournament over
a period of five days. Each player plays each of the others once. Three matches
are played simultaneously during each of the five days. The first day, Cavelli
beat Pietrovich after 36~moves. The second day, Cavelli was again victorious
when St.~Jacques failed to complete 40~moves within the required time limit.
The third day had the most exciting match of all when St.~Jacques declared that
he would checkmate Lord Bottomly in 8~moves and succeeded in doing so. On the
fourth day, Pietrovich defeated Smith.

Who played against Fernandez on the fifth day?

{
\newbox\vsbox  \setbox\vsbox=\hbox{\ vs.\ }
\def\cday#1{\multispan2\enspace\hfil Day~#1\enspace\hfil}
\def\vsday#1{\omit\hfil\hbox to\wd\vsbox{\hss Day~#1\hss}}

\solution The hint on page~381 of the book suggests that we should make a chart
showing what happens each day, and we should begin by determining whom
St.~Jacques can play on the fourth day. Putting the information given in the
problem into a chart, we have the following:
$$\vbox{\offinterlineskip
\halign{&\enspace\strut\hfil#\unskip\copy\vsbox&\strut#\unskip\hfil\enspace&\vrule#\cr
\vsday1&&&\vsday2&&&\vsday3&&&\vsday4&&&\cday5\cr
\omit&\omit&height2pt&\omit&\omit&height2pt&\omit&\omit&height2pt&\omit&\omit&height2pt&\omit&\omit\cr
\noalign{\hrule}
\omit&\omit&height2pt&\omit&\omit&height2pt&\omit&\omit&height2pt&\omit&\omit&height2pt&\omit&\omit\cr
Cav   &Piet  &&Cav   &St.~J &&St.~J &Lord~B&&Piet  &Smith &&\omit &\omit \cr
}}$$

On the fourth day, St.~Jacques cannot play Pietrovich or Smith, because they
are playing each other. He also cannot play Cavelli or Lord Bottomly, as he
has played them already. This means that St.~Jacques must play Fernandez on the
fourth day. Now that we have two matches determined for the fourth day, the
third match is easy---it must be between the two remaining players, Cavelli and
Lord Bottomly.
$$\vbox{\offinterlineskip
\halign{&\enspace\strut\hfil#\unskip\copy\vsbox&\strut#\unskip\hfil\enspace&\vrule#\cr
\vsday1&&&\vsday2&&&\vsday3&&&\vsday4&&&\cday5\cr
\omit&\omit&height2pt&\omit&\omit&height2pt&\omit&\omit&height2pt&\omit&\omit&height2pt&\omit&\omit\cr
\noalign{\hrule}
\omit&\omit&height2pt&\omit&\omit&height2pt&\omit&\omit&height2pt&\omit&\omit&height2pt&\omit&\omit\cr
Cav   &Piet  &&Cav   &St.~J &&St.~J &Lord~B&&Piet  &Smith &&\omit &\omit \cr
\omit &\omit &&\omit &\omit &&\omit &\omit &&St.~J &Fern  &&\omit &\omit \cr
\omit &\omit &&\omit &\omit &&\omit &\omit &&Cav   &Lord~B&&\omit &\omit \cr
}}$$

We know whom St.~Jacques plays on three of the days. Let's consider his
opponent on the first day. It cannot be Cavelli, Lord Bottomly, or Fernandez,
because these are his opponents on other days. This leaves either Pietrovich or
Smith. But Pietrovich is playing Cavelli on the first day, so only Smith is
available to play St.~Jacques. The remaining match on Day~1 must be Lord
Bottomly versus Fernandez. Furthermore, the only player St.~Jacques has not yet
met is Pietrovich; they must play on the fifth day.
$$\vbox{\offinterlineskip
\halign{&\enspace\strut\hfil#\unskip\copy\vsbox&\strut#\unskip\hfil\enspace&\vrule#\cr
\vsday1&&&\vsday2&&&\vsday3&&&\vsday4&&&\vsday5&\cr
\omit&\omit&height2pt&\omit&\omit&height2pt&\omit&\omit&height2pt&\omit&\omit&height2pt&\omit&\omit\cr
\noalign{\hrule}
\omit&\omit&height2pt&\omit&\omit&height2pt&\omit&\omit&height2pt&\omit&\omit&height2pt&\omit&\omit\cr
Cav   &Piet  &&Cav   &St.~J &&St.~J &Lord~B&&Piet  &Smith &&St.~J &Piet  \cr
St.~J &Smith &&\omit &\omit &&\omit &\omit &&St.~J &Fern  &&\omit &\omit \cr
Lord~B&Fern  &&\omit &\omit &&\omit &\omit &&Cav   &Lord~B&&\omit &\omit \cr
}}$$

Pietrovich must play Lord Bottomly on one of the days. The only day they are
both available is the second day. Once we have filled this in, we see that
Smith and Fernandez must play each other on the second day, since they are the
only two left. Also, Pietrovich and Lord Bottomly each have just one hole left
in their schedules; Pietrovich must play Fernandez on the third day, and Lord
Bottomly must play Smith on the fifth day. Finally we see that Cavelli plays
Smith on the third day, and Cavelli plays Fernandez on the fifth day. Our
completed chart is shown below.
$$\vbox{\offinterlineskip
\halign{&\enspace\strut\hfil#\unskip\copy\vsbox&\strut#\unskip\hfil\enspace&\vrule#\cr
\vsday1&&&\vsday2&&&\vsday3&&&\vsday4&&&\vsday5&\cr
\omit&\omit&height2pt&\omit&\omit&height2pt&\omit&\omit&height2pt&\omit&\omit&height2pt&\omit&\omit\cr
\noalign{\hrule}
\omit&\omit&height2pt&\omit&\omit&height2pt&\omit&\omit&height2pt&\omit&\omit&height2pt&\omit&\omit\cr
Cav   &Piet  &&Cav   &St.~J &&St.~J &Lord~B&&Piet  &Smith &&St.~J &Piet  \cr
St.~J &Smith &&Piet  &Lord~B&&Piet  &Fern  &&St.~J &Fern  &&Lord~B&Smith \cr
Lord~B&Fern  &&Smith &Fern  &&Cav   &Smith &&Cav   &Lord~B&&Cav   &Fern  \cr
}}$$

\noindent So it was Cavelli who played against Fernandez on the fifth day. \qed

}  % end \vsbox, \def\vslap

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

\problem A sculpture in an art gallery consists of a wooden cube suspended from
the ceiling by a thin wire. The wire is attached to the cube at one of its
corners, so that the cube hangs at an angle. A fly lands on the top corner of
the cube (the one at which the wire is attached) at 12:00~noon. Every five
minutes thereafter (at 12:05,~12:10, 12:15, and so on) the fly moves along one
of the edges of the cube to reach a neighboring corner. The path of the fly
around the cube is random (subject to the restriction that it can only move
along edges of the cube). What is the probability that the fly will be at the
bottom corner of the cube (the corner nearest the floor) at~12:31?

\solution We can color the corners of the cube with two colors (say, black and
white) in such a way that adjacent corners are given opposite colors, as shown
below.
$$\fig{homework-1-sol-cube.mps}$$

With this coloring, every move of the fly takes it from a corner of one color
to a corner of the opposite color. Since the fly makes a move every five
minutes, it will have made exactly six moves by~12:31. The fly began at a black
corner, so after six moves it must also be at a black corner. In particular, it
cannot be at the bottom corner of the cube, which is white. So the probability
that the fly will be at the bottom corner of the cube at~12:31 is~0. \qed

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

\problem Three guests check into a hotel and ask what the nightly rate is. The
clerk says a room costs 30~dollars a night, so each guest gives the clerk
ten dollars, and they head up to the room.

A while later, the clerk realizes he overcharged the guests; the room they are
staying in is only 25~dollars a night. So he takes five one-dollar bills from
the cash box and hands them to the bellhop with instructions to return the
money.

On the way up to the room, the bellhop realizes that five dollars cannot be
split evenly among three guests, so he pockets two dollars and returns three
dollars to the guests.

Now, each of the guests initially paid ten dollars for the room, but later
received a dollar back, so effectively each guest paid nine dollars. In total,
then, the room cost the guests 27~dollars. With the two dollars the bellhop
kept, this comes to 29~dollars. What happened to the missing dollar?

\solution This is a dishonest and misleading question. There is no missing
dollar.

If we carefully keep track of where all of the money ends up, we find that the
clerk has 25~dollars in the cash box, the bellhop has two dollars in his
pocket, and the three guests have one dollar each. This comes to 30~dollars, as
it should.

The question is misleading because the addition is done incorrectly in the last
paragraph. It is true that in all the three guests paid 27~dollars, but that
total includes both the cost of the room and the two-dollar ``tip'' for the
bellhop. It does not make sense to add the bellhop's two dollars to the
27-dollar total, because it is already included. What {\it should\/} be added
to the 27~dollars in order to get a total of~30 is the three dollars the guests
received as change. \qed

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

\problem (Note: The two parts of this question are not meant to be related to
each other, apart from the fact that they are both about arranging coins.)

\nobreak\medskip

\item{(a)} Place 10~coins in five straight lines so that each line contains
exactly four coins.

\nobreak\medskip

\item{(b)} Can you arrange four coins so that if you choose {\it any\/} three
of them (i.e., no matter which three of the four you pick), the three coins
you chose form the corners of an equilateral triangle?

\solution

\firstpart{(a)} There are several solutions to this puzzle. Here are two:
$$\midfig{homework-1-sol-star.mps}\qquad\midfig{homework-1-sol-tepee.mps}$$
To make such a figure, it is easier to begin with the five lines than with the
10~coins. Let any five straight lines be drawn in a plane so that no two of the
lines are parallel and no three of the lines meet in a single point. Then every
line will intersect every other line (so there will be four points of
intersection along each line), and in all there will be 10~points of
intersection among the five lines. Placing a coin on each point of intersection
will give a solution to this puzzle.

\part{(b)} It is impossible to solve this puzzle in two dimensions; three
dimensions are required. The trick is to place three of the coins flat on a
tabletop so that they form an equilateral triangle, and then suspend the fourth
coin above the center of the triangle so that it sits at the top of a
triangular pyramid (a regular tetrahedron), as shown below.

$$\fig{homework-1-sol-tetrahedron.mps}\eqno\hbox{\qed}$$

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

\problem (From the article ``Number Games and Other Mathematical Recreations''
in the 15th~edition of the Encyclop\ae dia Britannica.)\enspace Three travelers
were aboard a train that had just emerged from a tunnel, leaving a smudge of
soot on the forehead of each. While they were laughing at each other, and
before they could look into a mirror, a neighboring passenger suggested that
although no one of the three knew whether he himself was smudged, there was a
way of finding out without using a mirror.

He suggested: ``Each of the three of you look at the other two; if you see at
least one whose forehead is smudged, raise your hand.'' Each raised his hand at
once. ``Now,'' said the neighbor, ``as soon as one of you knows for sure
whether his own forehead is smudged or not, he should drop his hand, but not
before.''

After a moment or two, one of the men dropped his hand with a smile of
satisfaction, saying: ``I know.''

How did that man know that his forehead was smudged?

\solution Let's give the three travelers names: Augustus, Bertrand, and Kurt
(after three famous logicians). Suppose Augustus is the one who figures out
that his forehead is smudged. Let's look at the situation from his point of
view.

He sees two men with smudged foreheads and raised hands. He cannot conclude
anything from this directly. Perhaps Bertrand and Kurt are raising their hands
because they see Augustus' smudged forehead, but it is equally possible that
they are raising their hands merely because they see each other.

Augustus reasons as follows: ``I will assume, for the sake of argument, that my
own forehead is clean. Then Bertrand and Kurt must be raising their hands
because they see each other. What does the situation look like from Bertrand's
point of view? He sees Kurt's smudged forehead and my clean one, and he sees
Kurt raising his hand. Kurt is raising his hand because he sees a smudged
forehead, and clearly it is not mine (because mine is clean), so Bertrand can
easily conclude that his own forehead must be smudged. The situation is exactly
the same for Kurt. Therefore, assuming that my own forehead is clean, Bertrand
and Kurt can quickly determine that their own foreheads are smudged.

``But wait! Neither Bertrand nor Kurt is dropping his hand. They must not be
able to conclude anything about their own foreheads. This must mean that my
assumption is wrong, and my own forehead is smudged!'' \qed

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

\bye
