%  Homework assignment 6 solutions
%  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%
}}

% AMSFonts
\input amssym.tex

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

\headline={\hfil}
\footline={\hfil Page~\folio\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
\def\clap#1{\hbox to 0pt{\hss$\scriptstyle{#1}$\hss}}
\def\lcm{\mathop{\rm lcm}}  \def\gcd{\mathop{\rm gcd}}
\def\labs{\mathopen|}  \def\rabs{\mathclose|}  \def\abs#1{\labs{#1}\rabs}
\def\N{{\mathord{\Bbb N}}}  \def\Z{{\mathord{\Bbb Z}}}
\def\frac#1#2{{\textstyle{{#1}\over{#2}}}}

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

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

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

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

\solution Our task is to choose a valid sequence of letters and digits for a
Pennsylvania license plate. We can divide this task into seven steps: in the
first three steps we choose a letter from A through~Z (in other words, we are
choosing three letters, with replacement, and order is important), and in the
last four steps we choose a digit from 0 through~9 (we are choosing four
digits, with replacement, and order is important). There are 26~possible ways
to perform each of the first three steps, and there are 10~possible ways to
perform each of the last four steps. Therefore, by the multiplication
principle, in all there are
$26\times26\times26\times10\times10\times10\times10=175{,}760{,}000$~ways to
perform the task of choosing a valid license plate. In other words,
Pennsylvania can issue 175,760,000 license plates. \qed

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

\solution Our task is to choose one of the diagonals of a regular $n$-gon. We
can divide this task into two steps, namely, choosing each of the two endpoints
of the diagonal. We begin by choosing one of the vertices of the $n$-gon to be
the first endpoint of the diagonal; there are $n$~ways to perform this step.
Next we choose another vertex of the $n$-gon to be the second endpoint.
However, we may not choose the vertex that has already been chosen, and we may
not choose either of the vertices immediately adjacent to it (because a side of
the $n$-gon is not a diagonal). So there are $n-3$~ways to perform the second
step. By the multiplication principle, there are $n(n-3)$~ways in which the two
steps may be performed together.

But we have counted every diagonal twice: if the endpoints of a diagonal are
the vertices $A$ and~$B$, then we counted the diagonal once when $A$~was the
``first'' endpoint and $B$~was the ``second'' endpoint, and again when $B$~was
the ``first'' endpoint and $A$~was the ``second'' endpoint. So we have
overcounted by a factor of~2. To correct for this overcounting, we must divide
our total by~2. We conclude that the number of diagonals of a regular $n$-gon
is $n(n-3)/2$. \qed

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

\solution There are two key observations to be made. The first is that a date
can be ambiguous only when the day is between 1 and~12, inclusive, since there
only 12~months in a year. The second observation is that dates such as
1/1/71,~2/2/71, 3/3/71,~etc.\ are not ambiguous.

Our task is to choose an ambiguous date. We can divide this task into two
steps: choosing a month from 1 to~12, and choosing a day from 1 to~12. By the
multiplication principle, there are $12\times12=144$~ways in which this task
can be performed. But we have included the 12~unambiguous dates 1/1/71,~2/2/71,
3/3/71, \dots,~12/12/71, so from this total we must subtract~12. Therefore we
conclude that there are 132~ambiguous dates in a year.

Alternatively, we can observe that in each month there are 11~ambiguous days
(each of the days from 1 to~12 except the day having the same number as the
month). Since there are 12~months in a year, there are
$12\times11=132$~ambiguous dates in a year. \qed

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

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

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

\solution

\firstpart{(a)} Since the artist is choosing $r$ of her $n$~landscapes without
replacement, and the order in which the landscapes are chosen is not important
(the only thing that is important is {\it which\/} landscapes are chosen), the
number of choices is~$n\choose r$.

\part{(b)} If the artist has made up her mind to include the painting with the
white barn, then she has already chosen one of the $r$~landscapes. To complete
her decision, she must choose $r-1$~landscapes out of the remaining~$n-1$. So
the number of ways in which she can choose $r$ of her $n$~landscapes, if one
of the chosen landscapes is the one with the white barn, is~$n-1\choose r-1$.

\part{(c)} If the artist has decided {\it not\/} to include the painting with
the white barn, then she must choose all~$r$ of the landscapes to be exhibited
out of the $n-1$~landscapes that do not include the white barn. Therefore, the
number of ways in which she can choose $r$ of her $n$~landscapes, if the one
with the white barn is not chosen, is~$n-1\choose r$.

\part{(d)} Let's count the number of ways the artist can choose $r$ of her
$n$~landscapes---but let's do it in two different ways.

First, we count directly, as we did in part~(a). We see that the number of
possible choices for the artist is~$n\choose r$.

Second, we observe that any choice of $r$~landscapes must either
{\it include\/} the one with the white barn, or {\it exclude\/} it. In
part~(b), we saw that the number of choices that include the landscape with the
white barn is~$n-1\choose r-1$; in part~(c), we saw that the number of choices
that exclude this landscape is~$n-1\choose r$. Therefore, by the addition
principle, the total number of choices for the artist is
${n-1\choose r-1}+{n-1\choose r}$.

Since both of these expressions count the same thing, they must be equal. This
proves that
$${n\choose r}={n-1\choose r-1}+{n-1\choose r}.\eqno\hbox{\qed}$$

\vfill\eject %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\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-sol-streets.mps}$$

\solution Any route from point~$A$ to point~$B$ must be exactly 10~blocks long
(if we always walk only north or east). Out of those 10~blocks, five blocks
must be northward and five must be eastward. Choosing which of the 10~blocks
are to be northward completely and uniquely determines a route from point~$A$
to point~$B$. For example, if we decide that the first, second, fifth, eighth,
and ninth blocks should be northward, we have chosen the route
``north--north--east--east--north--east--east--north--north--east.''

Therefore, to choose a route from point~$A$ to point~$B$, we simply choose
which five of the 10~blocks of our journey are to be northward. So we are
choosing 5~items out of~10, without replacement (since we cannot choose one of
the 10~blocks to be northward twice). Furthermore, the order in which the
5~items are chosen is not important, because choosing the first block to be
northward before choosing the second block to be northward results in the same
route as if we had chosen the second block to be northward before choosing the
first block to be northward---the only thing that matters is {\it which\/}
blocks we choose, not the order in which we choose them.

Hence there are $10\choose5$~ways to choose a route from point~$A$ to point~$B$.
This number is
$${10\choose5}={10!\over5!\times5!}=252.\eqno\hbox{\qed}$$

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

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

\solution Our task is to form a sequence of five letters, chosen from A,~B, C,
and~D, that contains exactly two~A's. We can divide this task into four steps.
In the first step, we decide which two of the five positions should be filled
with A's. In the remaining three steps we fill each of the other three
positions (from left to right, say) with either B,~C, or~D.

There are ${5\choose2}=10$~ways to perform the first step. Each of the other
three steps can be performed in three ways. So, by the multiplication
principle, the number of ways in which the task can be performed is
$10\times3\times3\times3=270$, which is to say that there are 270~such
five-letter ``words.'' \qed

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

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

\solution Let $A$ be the set of integers from 1 to~10,000 that are divisible
by~3, and let $B$ be the set of integers from 1 to~10,000 that are divisible
by~7. In symbols,
$$\eqalign{
	A&=\bigl\{\,x\in\N\bigm|\hbox{$x\le10{,}000$ and $3\mid x$}\,\bigr\},\cr
	B&=\bigl\{\,x\in\N\bigm|\hbox{$x\le10{,}000$ and $7\mid x$}\,\bigr\}.\cr
}$$
[Note that the second vertical bar in each line above is the symbol meaning
``divides,'' not the symbol meaning ``such~that.''] Then the set of integers
from 1 to~10,000 that are divisible by 3 or~7 or both is~$A\cup B$. So we aim
to find~$\abs{A\cup B}$.

First we note that every third integer is divisible by~3. Since
$10{,}000\div3=3{,}333.33\ldots\,$, there are 3,333~integers from 1 to~10,000
that are divisible by~3; that~is, $\abs A=3{,}333$. Similarly, every seventh
integer is divisible by~7. Since $10{,}000\div7=1{,}428.57\ldots\,$, there are
1,428~integers from 1 to~10,000 that are divisible by~7, which is to say
$\abs B=1{,}428$.

Some integers are divisible by {\it both\/} 3 and~7; the set of such integers
between 1 and~10,000 is~$A\cap B$. An integer is divisible by both 3 and~7
precisely when it is divisible by~21 (because the least common multiple of 3
and~7 is~21). Every 21st integer is divisible by~21. Since
$10{,}000\div21=476.19\ldots\,$, there are 476~integers from 1 to~10,000 that
are divisible by~21. Hence $\abs{A\cap B}=476$.

Now, by the principle of inclusion--exclusion, we have
$$\eqalign{
	\abs{A\cup B}&=\abs A+\abs B-\abs{A\cap B}\cr
	&=3{,}333+1{,}428-476\cr
	&=4{,}285.\cr
}$$
So there are 4,285~integers from 1 to~10,000 that are divisible by 3 or~7 or
both. \qed

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

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

\nobreak\smallskip

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

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

\solution

\firstpart{(a)} Each circle represents a coin, and the bars separate the
pirates' shares. The first pirate's share is illustrated by the three circles
to the left of the first bar, the second pirate's share is represented by the
five circles between the first and second bars, and so on; the fifth pirate's
share is shown as the three circles to the right of the last bar. Note that the
third and fourth bars are adjacent---in other words, there are no circles
between them---because according to this division of the treasure the fourth
pirate gets nothing.

\part{(b)} The division of the treasure described in part~(b) can be
represented by the following sequence of symbols.
$$\coin\coin\coin\coin\coin\join\coin\join\coin\coin\coin\join\coin\coin\coin\join$$
The fifth pirate gets nothing, so there are no circles following the last bar.

\part{(c)} Every sequence of symbols representing a possible way to divide the
gold must have 12~circles (for the 12~coins) and four bars (to divide the five
pirates' shares). Note that there will be one fewer bar than the number of
pirates, because the bars serve to {\it separate\/} the shares of the pirates.
So each such sequence will have 16~symbols in all.

As long as these conditions are met---12~circles and four bars---any sequence
of symbols will represent a possible way to divide the treasure. In fact, we
can read such a sequence of symbols as a description of the division of the
treasure; the first pirate gets as many coins as there are circles to the left
of the first bar, and so on.

\part{(d)} In part~(c) we saw that every sequence of 16 circles and bars having
12~circles and four bars represents one possible way for the pirates to divide
the gold. So we can count the number of ways to divide the gold by counting
instead the number of sequences of 16 circles and bars having 12~circles and
four bars.

To make such a sequence of symbols, we start with 16~empty positions for
symbols. We then choose four of the positions to be filled with bars; the
remaining 12~positions must be filled with circles. There are $16\choose4$~ways
to choose the four positions for the bars, and so there are $16\choose4$~such
sequences of symbols. Therefore there are also $16\choose4$~possible ways to
divide the treasure, because each such sequence of symbols corresponds to one
way to divide the treasure.

\part{(e)} We can abstract the reasoning we used in parts (a) through~(d) to
find the number of ways to distribute $r$~indistinguishable objects into
$n$~distinguishable boxes. The $r$~indistinguishable objects correspond to the
12~identical gold coins, and the $n$~distinguishable boxes correspond to the
five pirates (who are certainly distinguishable---a situation in which the
first pirate gets all of the coins is different from a situation in which the
second pirate gets all of the coins). In parts (a) through~(d), we were
examining the case in which $r=12$ and $n=5$.

When we write a sequence of circles and bars representing a possible way to
distribute the $r$~objects into the $n$~boxes, we will need $r$~circles to
represent the objects and $n-1$~bars to separate the contents of each box. We
interpret such a sequence of symbols as we did before: the number of circles to
the left of the first bar will represent the number of objects placed in the
first box, the number of circles between the first bar and the second bar will
represent the number of objects placed in the second box, and so on.

To make such a sequence of symbols, we start with $r+(n-1)$~empty positions for
symbols, and then we choose $n-1$~of the positions to fill with bars; the
remaining $r$~positions must be filled with circles. The number of ways to
choose the positions of the bars, and hence the number of such sequences of
symbols, is~$r+(n-1)\choose n-1$, which of course is the same
as~$n+r-1\choose n-1$, just by rearranging the top. Each such sequence of
symbols corresponds to one way to distribute the objects into the boxes, so
there are $n+r-1\choose n-1$~ways to do so.

\part{(f)} It is a little difficult to find an interpretation of the
distribution of $r$~indistinguishable objects into $n$~distinguishable boxes as
``choosing $r$~elements from a set of size~$n$ with replacement, when the order
in which the elements are chosen is not important,'' but here is one way to
look at it: Suppose the $n$~pirates each write their name on a slip of paper
and put the slips in a hat. Then a name is drawn from the hat to determine
which pirate gets the first coin. This name is replaced, and another name is
drawn to determine who gets the second coin; this continues until all $r$~coins
have been distributed.

In the end, the {\it order\/} in which the names are drawn from the hat is not
important, because the coins are identical---the only thing that matters is
{\it how many times\/} each name has been drawn. So this process of drawing
names from a hat is simply a way of choosing $r$~elements (the drawn names)
from a set of size~$n$ (the set of all names in the hat) with replacement
(because the names are replaced after having been drawn), and the order in
which the elements are chosen is not important. \qed

\nobreak\medskip

\noindent[\thinspace Note: The counting technique described in this problem
traditionally uses stars instead of circles so that it can be called ``stars
and bars,'' which is a catchier name.\thinspace]

\vfill\eject %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\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-sol-chords.mps}$$

\solution To draw two such chords, we can first select the four points that
will serve as the endpoints of the chords. We select these four points without
replacement, and the order in which we select them is not important (the only
important thing is {\it which\/} four points we select). No matter how we
choose these four points, there will be only one way to connect them so that
the chords intersect in the interior of the circle. (Why?) So the number of
ways to draw two chords that intersect in the interior equals the number of
ways to select four out of the $n$~points; this number is~$n\choose4$. \qed

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

\solution We divide the square into four congruent smaller squares, each of
side length 1~meter, as shown below.
$$\fig{homework-6-sol-square.mps}$$
By the Pythagorean theorem, the diagonal of each of the small squares is
$\sqrt2$~meters; this is the greatest possible separation of two points that
are in the same small square.

Consider any five points in the large square. Since there are four small
squares, the pigeonhole principle says that one of the small squares must
contain at least two of the five points, and therefore these two points must be
no more than $\sqrt2$~meters apart. \qed

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

\bye
