%  Homework assignment 6
%  21-110: Problem Solving in Recreational Mathematics, spring 2010
%  Assigned: Friday, March 26, 2010. Due: Monday, April 5, 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~6}
\smallskip
\centerline{Assigned Friday, March~26, 2010. Due Monday, April~5, 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 Normal Pennsylvania license plates have three capital letters followed
by four numerical digits. Assuming there are no other restrictions, how many
possible license plates can Pennsylvania issue? Why?

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

\problem In the handout about finding a formula for a sequence of numbers from
earlier in the course, we made the conjecture that the number of diagonals of a
regular $n$-gon is
$${n(n-3)\over2}.$$
Prove this conjecture.

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

\problem (From {\it The Colossal Book of Short Puzzles and Problems\/} by
Martin Gardner.)\enspace In this country a date such as July~4, 1971, is often
written 7/4/71, but in other countries the month is given second and the same
date is written 4/7/71. If you do not know which system is being used, how many
dates in a year are ambiguous in this two-slash notation?

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

\problem An artist has painted $n$~landscapes, all different. One of her
paintings is unlike all the others, because it shows an unusual white barn. The
artist must select $r$~of her landscapes to be displayed in an exhibition.
(Assume $r\le n$.)

\nobreak\smallskip

\item{(a)} In how many ways can she choose $r$ of her $n$~landscapes to be
exhibited?

\nobreak\smallskip

\item{(b)} Suppose the artist decides that she likes the painting with the
white barn and wants to include it in the exhibition. In how many ways can she
choose $r$ of her $n$~landscapes to be exhibited, if one of the $r$~landscapes
must be the one with the white barn?

\itemhint Vkh kdv douhdgb pdgh rqh fkrlfh. Krz pdqb pruh fkrlfhv pxvw vkh pdnh,
dqg krz pdqb odqgvfdshv grhv vkh kdyh wr fkrrvh iurp?

\nobreak\smallskip

\item{(c)} Suppose, on the other hand, that the artist decides she does not
like the painting with the white barn and wants to keep it out of the
exhibition. In how many ways can she choose $r$ of her $n$~landscapes to be
exhibited, if the one with the white barn must not be chosen?

\itemhint Krz pdqb fkrlfhv grhv vkh kdyh wr pdnh, dqg krz pdqb odqgvfdshv grhv
vkh kdyh wr fkrrvh iurp?

\nobreak\smallskip

\item{(d)} Use the ideas of the previous three parts to prove the general fact
that
$${n\choose r}={n-1\choose r-1}+{n-1\choose r}.$$

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

\problem You find yourself at point~$A$ in a city with streets running
north--south and east--west that form a square grid (i.e., not Pittsburgh). You
need to get to point~$B$, which is five blocks east and five blocks north of
point~$A$.  (See the street map below.) In how many different ways can you walk
from point~$A$ to point~$B$, if you always walk only north or east?
$$\fig{homework-6-streets.mps}$$

\hint Krz pdqb eorfnv pxvw brx zdon lq doo? Krz pdqb ri wkrvh eorfnv pxvw eh
qruwkzdug?

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

\problem How many five-letter ``words'' formed from the letters A,~B, C, and~D
(with repetition allowed) contain exactly two~A's?

\hint Rqh zdb wr pdnh vxfk d zrug lv wr iluvw fkrrvh wkh srvlwlrqv ri wkh D'v
dqg wkhq fkrrvh wkh uhpdlqlqj ohwwhuv.

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

\problem How many integers from 1 to~10,000 are divisible by 3 or~7 (or both)?

\hint Sulqflsoh ri lqfoxvlrq--hafoxvlrq.

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

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

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

\problem (Choosing with replacement, order not important.)\enspace
Five pirates have decided to divide a treasure of 12~identical gold coins
among them. The question we will explore in this problem is: In how many ways
can this be done?

\nobreak\smallskip

% "Coins and joins"? :-)
\def\coin{\,{\circ}\,}
\def\join{\,{\mid}\,}

\item{(a)} One possible way to divide the treasure is as follows: The first
pirate gets 3~coins, the second gets~5, the third gets~1, the fourth gets none,
and the fifth gets~3. Explain how the following sequence of symbols represents
this possibility.
$$\coin\coin\coin\join\coin\coin\coin\coin\coin\join\coin\join\join\coin\coin\coin$$

\item{(b)} Another possible way to divide the treasure is as follows: The first
pirate gets 5~coins, the second gets~1, the third gets~3, the fourth gets~3,
and the fifth gets none. [Note that this division of the gold is
{\it different\/} from the division in part~(a).] Write a sequence of symbols
similar to the one above representing this possibility.

\nobreak\smallskip

\item{(c)} Consider all such sequences of symbols representing possible ways to
divide the gold. What defining characteristics do all such sequences share? Be
as precise as you can.

\itemhint Lq sduwlfxodu, krz pdqb ri hdfk wbsh ri vbpero?

\nobreak\smallskip

\item{(d)} Explain why the number of possible ways to divide the treasure is
$16\choose4$.

\itemhint Xvh wkh suhylrxv sduw.

\nobreak\smallskip

\item{(e)} Explain why, in general, if $r$~indistinguishable objects are to be
distributed into $n$~distinguishable boxes, there are $n+r-1\choose n-1$~ways
to do so.

\nobreak\smallskip

\item{(f)} In what sense can this be described as ``choosing $r$~elements from
a set of size~$n$ with replacement, when the order in which the elements are
chosen is not important''?

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

\problem Given $n$~points on the circumference of a circle, how many ways are
there to draw two different chords connecting pairs of these points such that
the chords intersect in the interior of the circle? (Chords sharing one
endpoint do not count.) The picture below shows seven points on the
circumference of a circle and one way to draw two chords that intersect in the
interior.
$$\fig{homework-6-chords.mps}$$

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

\problem Use the pigeonhole principle to prove that, if any five points are
chosen inside a square whose sides are 2~meters long, there must be two of
these points that are no more than $\sqrt2$~meters apart.

\hint Brx duh sodflqj ilyh remhfwv (wkh srlqwv) lqwr irxu ``erahv.'' Zkdw
vkrxog wkh ``erahv'' eh? Wkh Sbwkdjruhdq wkhruhp zloo suredeob eh khosixo dw
vrph srlqw.

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

\bye
