%  Homework assignment 8
%  21-110: Problem Solving in Recreational Mathematics, spring 2010
%  Assigned: Wednesday, April 14, 2010. Due: Monday, April 26, 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

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

\def\ipmod#1{\;({\rm mod}\,\,#1)}  % looks better inline than \pmod does

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

\centerline{\titlefont 21-110: Problem Solving in Recreational Mathematics}
\smallskip
\centerline{\bf Homework assignment~8}
\smallskip
\centerline{Assigned Wednesday, April~14, 2010. Due Monday, April~26, 2010.}

\bigskip

\noindent Work at least {\bf FOUR} of the following problems, at least one of
which must be from Part~B. All problems are of equal weight. If you submit
solutions for more than four problems, you will get credit for your best four
(with the proviso that you will get credit for at most three problems from
Part~A).

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 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\centerline{\bf--- Part~A ---}

\nobreak\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem A {\it loop\/} is an edge that joins a vertex to itself. {\it Multiple
edges\/} are two or more edges between the same pair of vertices. (See the
picture below.) A {\it simple graph\/} is a graph with no loops and no multiple
edges. Draw a simple graph with at least two vertices such that no two vertices
have the same degree, or explain why this is impossible.
$$\fig{homework-8-multigraph.mps}$$

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

\problem Draw an example of each of the following:

\nobreak\medskip

\item{(a)} A graph that has an Eulerian circuit but no Hamiltonian circuit.

\nobreak\smallskip

\item{(b)} A graph that has a Hamiltonian circuit but no Eulerian circuit.

\nobreak\medskip

\noindent In both cases, justify that your graph satisfies the required
conditions.

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

\problem Agnes hosts a party. Over the course of the evening some people at the
party shake hands. Near the end of the party, but before any of the guests have
left, Agnes gets everyone's attention and asks how many people shook hands an
odd number of times. Exactly 11~guests say they have done so. Assuming that all
the guests remember how many hands they shook, did Agnes shake an even number or
an odd number of hands? Why?

\hint Vhh Wkhruhp~6.5 rq sdjh~186.

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

\problem (Problem~6.21 from {\it Problem Solving Through Recreational
Mathematics\/}.)\enspace Describe a knight's tour on a $3\times7$ chessboard.

\hint Vhh wkh klqw rq sdjh~402.

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

\problem You decide that you want to visit the six largest cities in
Pennsylvania (according to the 2007 population estimates from the U.S.~Census
Bureau). The shortest distances between these cities, according to Google Maps,
are given in the distance table below.
$$\def\spaceamt{height1pt}
\def\rulespace{\spaceamt&\omit&\spaceamt&\omit&\spaceamt&\omit&\spaceamt&\omit&\spaceamt&\omit&\spaceamt&\omit&\spaceamt&\omit&\spaceamt\cr}
\def\tablerule{\rulespace\noalign{\hrule}\rulespace}
\vbox{\offinterlineskip
\hrule
\halign{&\vrule#&\enspace\hfil\strut#\hfil\enspace\cr
\rulespace
&Distances in miles&&\bf A.&&\bf Erie&&\bf Phila.&&\bf Pgh.&&\bf R.&&\bf S.&\cr\tablerule
&\bf Allentown\relax   &&---&&371&& 55&&279&& 39&& 75&\cr\tablerule
&\bf Erie\relax        &&371&&---&&401&&128&&358&&297&\cr\tablerule
&\bf Philadelphia\relax&& 55&&401&&---&&301&& 57&&124&\cr\tablerule
&\bf Pittsburgh\relax  &&279&&128&&301&&---&&258&&282&\cr\tablerule
&\bf Reading\relax     && 39&&358&& 57&&258&&---&& 97&\cr\tablerule
&\bf Scranton\relax    && 75&&297&&124&&282&& 97&&---&\cr\rulespace}
\hrule}$$

\item{(a)} Draw a weighted graph to represent this information. (Be sure to
label the vertices of the graph.)

\smallskip

\item{(b)} You want to start in Pittsburgh, visit all of these cities, and
return to your starting point. In mathematical terms, what are you trying to
find? Why?

\smallskip

\item{(c)} You would like to keep your total travel distance low. Use your
graph from part~(a) to find an efficient way to tour these six cities. Explain
the method you are using and show all of your steps. What is the total distance
you travel if you go this way?

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

\centerline{\bf--- Part~B ---}

\nobreak\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (Problem~6.25 from {\it Problem Solving Through Recreational
Mathematics}.)\enspace Three married couples want to cross a river. The only
boat available is capable of holding two people at a time. This would present
no difficulty were it not for the fact that the women are all very jealous, so
that each woman refuses to allow her husband to be in the presence of another
woman unless she herself is also present.

How should they cross the river with the least amount of rowing?

\hint Vhh wkh klqw rq sdjh~402.

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

\problem Eight radio stations, one in each of the eight cities in the distance
table below, are to be assigned frequencies. Two stations cannot be assigned
the same frequency if they are within 200~miles of each other; otherwise their
signals will interfere.
$$\def\spaceamt{height1pt}
\def\rulespace{\spaceamt&\omit&\spaceamt&\omit&\spaceamt&\omit&\spaceamt&\omit&\spaceamt&\omit&\spaceamt&\omit&\spaceamt&\omit&\spaceamt&\omit&\spaceamt&\omit&\spaceamt\cr}
\def\tablerule{\rulespace\noalign{\hrule}\rulespace}
\hss\vbox{\offinterlineskip
\hrule
\halign{&\vrule#&\enspace\hfil\strut#\hfil\enspace\cr
\rulespace
&Distances in miles&&\bf Ashland&&\bf Bristol&&\bf Clinton&&\bf Douglas&&
	\bf Empire&&\bf Franklin&&\bf Greene&&\bf Huron&\cr\tablerule
&\bf Ashland\relax &&---&&292&&221&&366&&357&&127&&240&&298&\cr\tablerule
&\bf Bristol\relax &&292&&---&& 93&&195&&366&&329&&247&&419&\cr\tablerule
&\bf Clinton\relax &&221&& 93&&---&&171&&290&&239&&162&&329&\cr\tablerule
&\bf Douglas\relax &&366&&195&&171&&---&&223&&330&&171&&330&\cr\tablerule
&\bf Empire\relax  &&357&&366&&290&&223&&---&&252&&136&&142&\cr\tablerule
&\bf Franklin\relax&&127&&329&&239&&330&&252&&---&&167&&172&\cr\tablerule
&\bf Greene\relax  &&240&&247&&162&&171&&136&&167&&---&&176&\cr\tablerule
&\bf Huron\relax   &&298&&419&&329&&330&&142&&172&&176&&---&\cr\rulespace}
\hrule}\hss$$

\item{(a)} Draw a conflict graph for this scenario. Explain what the vertices
represent and what causes a conflict.

\smallskip

\item{(b)} Color the vertices of the conflict graph using as few colors as
possible, according to the rules of graph coloring.

\smallskip

\item{(c)} Interpret your coloring from part~(b). How many different
frequencies are needed? How should they be assigned?

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

\problem A map of South America requires four colors if no two countries which
share a common border are to receive the same color; three colors are not
enough. An easy way to see this is to consider Paraguay and its three
neighbors, as shown in the map on the left below. Each of these four countries
(Argentina, Bolivia, Brazil, and Paraguay) borders all of the other three. (In
other words, the dual graph of this map is the complete graph on four
vertices.) So four colors are necessary.

This situation does not arise in a map of the United States---there are no four
states such that each of the four borders all of the other three. So, no matter
which four states you choose, there will always be two of them that do not
border each other. (Verify this for yourself.)

Does this mean that a map of the United States can be colored with just three
colors? If so, show how it can be done by coloring the map of the 48~contiguous
United States (shown on the right below, not to the same scale as the other
map) using just three colors in such a way that no two bordering states receive
the same color. If it cannot be done, explain, as carefully and as thoroughly
as you can, why four colors are necessary.

(Note that Utah and New Mexico touch at only a single point, so they are not
considered to be bordering states. The same is true for Colorado and Arizona.)

\hint Qhydgd dqg lwv qhljkeruv.

$$\hss\vcenter{\pdfximage height3truein{homework-8-paraguay-neighbors.pdf}\pdfrefximage\pdflastximage}
\qquad\qquad
\vcenter{\pdfximage height3truein{homework-8-united-states.pdf}\pdfrefximage\pdflastximage}\hss$$

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

\bye
