%  Homework assignment 3 solutions
%  21-110: Problem Solving in Recreational Mathematics, spring 2010
%  Assigned: Friday, February 5, 2010. Due: Wednesday, February 17, 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 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\frac#1#2{{\textstyle{{#1}\over{#2}}}}
\def\lcm{\mathop{\rm lcm}}  \def\gcd{\mathop{\rm gcd}}

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

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

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

\problem (``A Swimmer and a Hat,'' from {\it The Moscow Puzzles\/} by Boris~A.
Kordemsky, edited by Martin Gardner.)\enspace A boat is being carried away by a
current. A man jumps out and swims against the current for a while, then turns
around and catches up with the boat. Did he spend more time swimming against
the current or catching up with the boat? (We assume his muscular efforts never
change in strength.)

The answer is: Both times were the same. The current carries man and boat
downstream at the same speed. It does not affect the distance between the
swimmer and the boat.

Now imagine that a sportsman jumps off a bridge and begins to swim against the
current. The same moment a hat blows off a man's head on the bridge and begins
to float downstream. After 10~minutes the swimmer turns back, reaches the
bridge, and is asked to swim on until he catches up with the hat. He does,
under a second bridge 1,000~yards from the first.

The swimmer does not vary his effort. What is the speed of the current?

\solution The current carries the swimmer and the hat downstream at the same
rate and does not itself change the distance between them. The swimmer and the
hat begin together at the same point (the first bridge) and end at the same
point (the second bridge). Since the sportsman swam away from the hat for
10~minutes, he must have swum toward the hat for 10~minutes to meet it again.
(This is just like the situation with the swimmer and the boat.)

In this span of 20~minutes, the current has carried the hat 1,000~yards, from
the first bridge to the second. Therefore the speed of the current is
$${\hbox{1,000 yards}\over\hbox{20 minutes}}=\hbox{50 yards per minute}.\eqno\hbox{\qed}$$

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

\problem International paper sizes, standardized in ISO~216, are used in nearly
every country in the world except the United States and Canada. The largest
size in the so-called ``A~series'' is called~A0, and has an area of one square
meter. The next size is called~A1 and is formed by cutting a sheet of A0~paper
in half. Then A2~paper is formed by cutting a sheet of A1~paper in half, and so
on. This continues through the smallest size,~A10. Additionally, the various
sizes are defined so that all of the paper sizes are similar (that~is, they
have the same shape, but different sizes). This makes it easy to scale
documents from one size of paper to another. What size of paper corresponds
most closely to the ``letter'' size paper common in the United States
($8{1\over2}$~inches by 11~inches)? What are its dimensions, rounded to the
nearest millimeter? [There are 25.4~millimeters in one inch, and
1000~millimeters in one meter.]

\solution The dimensions of letter size paper in millimeters are
$$(\hbox{8.5 in.})\left(\hbox{25.4 mm}\over\hbox{1 in.}\right)=\hbox{215.9 mm}
	\qquad\hbox{by}\qquad
	(\hbox{11 in.})\left(\hbox{25.4 mm}\over\hbox{1 in.}\right)=\hbox{279.4 mm},$$
so the area of one sheet of letter size paper is
$$(\hbox{215.9 mm})(\hbox{279.4 mm})=\hbox{60,322.46 $\rm mm^2$}.$$
The area of one sheet of A0~paper is
$$(\hbox{1 $\rm m^2$})\left(\hbox{1000 mm}\over\hbox{1 m}\right)^2
	=\hbox{1,000,000 $\rm mm^2$}.$$
So A1~paper has half this area, A2~paper has $1/4$ this area,
A3~paper has $1/8$ this area, A4~paper has $1/16$ this area,
and so on. It turns out that the area of one sheet of A4~paper is
$${\hbox{1,000,000 $\rm mm^2$}\over16}=\hbox{62,500 $\rm mm^2$},$$
which is very close to the area of letter size paper. So A4~paper is the size
that corresponds most closely to letter size paper.

\goodbreak

Now we need to determine its dimensions. We are told that each size of paper in
the A~series can be obtained by cutting the next larger size in half, and that
all of the sizes are similar. This means that they have the same proportions,
that~is, the ratio between the long side and the short side is the same. Let's
draw a picture of a sheet of A4~paper and introduce some variables to represent
lengths of sides:
$$\fig{homework-3-sol-paper.mps}$$

The two halves of this sheet of A4~paper are sheets of A5~paper, and they must
have the same proportions as the sheet of A4~paper. So we have the equation
$${x\over y}={y\over x/2}.$$
Cross-multiplying, we get
$${x^2\over2}=y^2.$$
Now we multiply both sides by~2 to get
$$x^2=2y^2.$$
We can take the square root of both sides of this equation to solve for~$x$.
(Since $x$ and~$y$ represent lengths, they cannot be negative, so we do not
need to consider negative square roots.) We get
$$x=\sqrt{2y^2}=y\sqrt2.$$
This gives us an expression for~$x$ in terms of~$y$. Now we can use the fact
that the area of one sheet of A4~paper should be 62,500~$\rm mm^2$ to write the
equation
$$xy=62{,}500.$$
Plugging in $x=y\sqrt2$, we obtain
$$y^2\sqrt2=62{,}500,$$
so
$$y^2={62{,}500\over\sqrt2}.$$
Therefore
$$y=\sqrt{62{,}500\over\sqrt2}\approx210.2,$$
which means
$$x\approx(210.2)\sqrt2\approx297.3.$$
Thus, rounded to the nearest millimeter, a sheet of A4~paper is
210~mm by 297~mm. \qed


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

\problem (Exercise~3.27 from {\it Problem Solving Through Recreational
Mathematics}.)\enspace When Erica was two years old, Leroy was four times as
old as Miriam. When Miriam was twice as old as Erica, Leroy was three times as
old as Miriam. How old was Erica when Leroy was twice as old as Miriam?

\solution There are three points in time in this problem. At one point in time,
Erica is two years old, and Leroy is four times as old as Miriam. At a second
point in time, Miriam is twice as old as Erica, and Leroy is three times as old
as Miriam. At the third point in time, Leroy is twice as old as Miriam. We want
to find how old Erica is at this third point in time.

When I worked on this problem, I became stuck almost immediately. I couldn't
figure out how to represent this information in a coherent way. After I saw
that the problem refers to three points in time, I decided to draw a timeline
with three marked points, and then I tried to write down what was true at each
of these points in time. Using $E$,~$L$, and~$M$ for the ages of Erica, Leroy,
and Miriam, respectively, I drew the following picture.
$$\fig{homework-3-sol-timeline-1.mps}$$

The problem with this picture is that the variables $E$,~$L$, and~$M$ do not
consistently represent the same numbers, because they represent the ages of
Erica, Leroy, and Miriam at three different points in time.

To fix this problem, I needed to define more carefully what I wanted the
variables $E$,~$L$, and~$M$ to mean. I decided that they should represent the
ages (in years) of Erica, Leroy, and Miriam, respectively, at the {\it third\/}
point in time. (The unknown value we are trying to find is Erica's age at the
third point in time, so it seemed sensible to make the variables represent
these ages.)

Now, if $E$,~$L$, and~$M$ represent the ages at the third point in time, how
should we refer to the ages at the second point in time? If we knew that, say,
2~years had elapsed between the second and third points, we could use $E-2$,
$L-2$, and~$M-2$ to represent the ages at the second point in time. But we
don't know this elapsed time. So I decided to introduce another variable, which
I called~$t$, to represent the elapsed time (in years) between the second and
third points; then the ages at the second point in time are $E-t$, $L-t$, and
$M-t$.

Similarly, I introduced a variable~$s$ to represent the elapsed time (in years)
between the first and second points. Then I could write $E-t-s$, $L-t-s$, and
$M-t-s$ for the three ages at the first point in time. In picture form:
$$\fig{homework-3-sol-timeline-2.mps}$$

Using these expressions for the ages at the various points in time, we can
write the information given in the problem as shown below.
$$\fig{homework-3-sol-timeline-3.mps}$$

\goodbreak

Now we have five equations (in the five unknowns $E$,~$L$, $M$, $s$, and~$t$),
and each of these variables has a consistent meaning throughout all five
equations. Therefore we have the following system of equations:
$$\eqalignno{
	E-t-s&=2,\cr
	L-t-s&=4(M-t-s),\cr
	M-t&=2(E-t),\cr
	L-t&=3(M-t),\cr
	L&=2M.&(1)\cr
}$$
All that we have to do now is to solve it. (Actually, we don't have to solve it
completely; the question asks only for the value of~$E$.)

There are several ways to solve this system of equations. One strategy, which I
will follow here, is to systematically substitute or eliminate each variable
one at a time until only one is left. (In our case, we will aim to have $E$ be
the last variable left, since that is the one we are trying to solve for.)

Equation~(1), the last of the five equations above, gives us an expression
for~$L$ in terms of the variable~$M$. So we can substitute $2M$ for~$L$ in the
other equations. This reduces the system to one of four equations in four
unknowns.
$$\eqalign{
	E-t-s&=2,\cr
	2M-t-s&=4(M-t-s),\cr
	M-t&=2(E-t),\cr
	2M-t&=3(M-t).\cr
}$$

\noindent Let's multiply out the right-hand sides of these equations to get rid
of the parentheses.
$$\eqalign{
	E-t-s&=2,\cr
	2M-t-s&=4M-4t-4s,\cr
	M-t&=2E-2t,\cr
	2M-t&=3M-3t.\cr
}$$
And now let's move all of the variables to the left-hand sides and combine
like terms.
$$\eqalignno{
	E-t-s&=2,\cr
	-2M+3t+3s&=0,\cr
	-2E+M+t&=0,\cr
	-M+2t&=0.&(2)\cr
}$$

If we solve equation~(2), the last equation above, for the variable~$M$, we
get $M=2t$. This gives us another substitution to make, so that we can get rid
of another variable. After the substition of~$2t$ for~$M$ in the first three
equations, we are left with a system of three equations in three unknowns.
$$\eqalign{
	E-t-s&=2,\cr
	-2(2t)+3t+3s&=0,\cr
	-2E+2t+t&=0.\cr
}$$

\noindent We can combine like terms to get the following.
$$\eqalignno{
	E-t-s&=2,\cr
	-t+3s&=0,&(3)\cr
	-2E+3t&=0.\cr
}$$

Now equation~(3), the middle equation above, looks promising. We can solve it
for~$t$ to get $t=3s$. Substituting this into the other two equations, we get
a system of two equations in two unknowns.
$$\eqalign{
	E-3s-s&=2,\cr
	-2E+3(3s)&=0.\cr
}$$

\noindent Again we combine like terms.
$$\eqalignno{
	E-4s&=2,&(4)\cr
	-2E+9s&=0.&(5)\cr
}$$

We are down to just two variables, $E$~and~$s$. We would like to eliminate~$s$,
because $E$ is the variable we're trying to solve for. To accomplish this, we
can multiply equation~(4) by~9 and equation~(5) by~4, and then add them
together:
$$\eqalign{
	9E-36s&=18\cr
	-8E+36s&=0\cr
\noalign{\vskip2pt\hrule\vskip2pt}
	E\phantom{{}+00s}&=18.\cr
}$$

We got lucky---all we were trying to do was to eliminate~$s$, but it so
happened that we also solved for the value of~$E$ in the process. So we see
that Erica is 18~years old at the third point in time, that~is, Erica was
18~years old when Leroy was twice as old as Miriam.

Even though we have the answer to the question, let's go back and solve for the
other variables, just to make sure we didn't make a mistake in our algebra
somewhere. We can retrace our steps in reverse order, substituting the values
of the variables we know. From equation~(4), using $E=18$, we have $18-4s=2$,
so $4s=16$, which means $s=4$. Using this in equation~(3), we have $-t+3(4)=0$,
so $t=12$. Now equation~(2) becomes $-M+2(12)=0$, so $M=24$; and so
equation~(1) is $L=2(24)$, so $L=48$. This information allows us to fill out
the timeline with actual ages and elapsed times:
$$\fig{homework-3-sol-timeline-4.mps}$$
Everything here matches up with the information given in the original problem,
so our solution checks out. \qed

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

\problem (Exercise~3.19 from {\it Problem Solving Through Recreational
Mathematics}.)\enspace The silver currency of the Kingdom of Bonoria consists
of glomeks, nindars, and morms. Four glomeks are equal in value to seven
nindars; and one glomek and one nindar together are worth thirty-three morms.

On my last visit to Bonoria, I entered a bank, handed the teller some glomeks
and nindars, and asked him to change them into morms.

``Do you think that I am a magician?'' he replied. (Bonorians are noted for
their warped sense of humor.) ``Well, let's see,'' he continued. ``If you had
twice as many glomeks, I could give you 120~morms; and if you had twice as many
nindars I could give you 114~morms.''

How many morms did he give me?

\solution This problem can be confusing because there are three different units
of currency in use. We should choose one unit of currency and do all of our
calculations in terms of that unit. Let's choose to do everything in terms of
morms.

I found it helpful to first figure out how many morms a glomek is worth, and
how many morms a nindar is worth. Let's use $g$ to represent the number of
morms in one glomek, and $n$~to represent the number of morms in one nindar. We
are told that four glomeks are equal to seven nindars. In other words, the
number of morms in four glomeks (that~is,~$4g$) is equal to the number of morms
in seven nindars (that~is,~$7n$); so
$$4g=7n.$$
If we solve this equation for~$n$, we get
$$n=\frac47g.$$
We are also told that one glomek and one nindar together are worth thirty-three
morms, so
$$g+n=33.$$
(We are working in morms; both sides of this equation are numbers that count
morms. The 33 on the right-hand side means 33~morms. There is no need to
multiply this~33 by a variable~$m$.) Substituting $n=\frac47g$, we have
$$g+\frac47g=33.$$
We add like terms on the left-hand side to get
$$\frac{11}7g=33.$$
Now we multiply both sides by~7 to obtain
$$11g=231;$$
so, dividing both sides of this by~11, we see that
$$g=21,$$
and thus
$$n=\frac47(21)=12.$$
So a glomek is worth 21~morms, and a nindar is worth 12~morms.

Now that we understand the currency system, let's figure out how much money the
narrator of the story had. We'll use $G$ and~$N$ to represent the number of
glomeks and nindars she had. (Note that these do not mean the same thing that
$g$ and~$n$ did previously, which is why we're using capital letters now.) We
will continue to do all our money calculations in terms of morms. The amount of
money the narrator had (in morms) was $21G+12N$, because each glomek is worth
21~morms and each nindar is worth 12~morms. This is the value we are trying to
find.

We are told that if the narrator had had twice as many glomeks, she would have
had 120~morms, so
$$21(2G)+12N=120.$$
Also, if the narrator had had twice as many nindars, she would have had
114~morms, so
$$21G+12(2N)=114.$$
So we have a system of two equations in two unknowns:
$$\eqalignno{
	42G+12N&=120,&(6)\cr
	21G+24N&=114.&(7)\cr
}$$
We can eliminate~$G$ by multiplying equation~(7) by~$-2$ and adding it to
equation~(6):
$$\eqalign{
	42G+12N&=\phantom+120\cr
	-42G-48N&=-228\cr
\noalign{\vskip2pt\hrule\vskip2pt}
	-36N&=-108.\cr
}$$
Therefore $N=3$. Substituting this value of~$N$ into equation~(6), we get
$42G+12(3)=120$, so $42G=84$, which means $G=2$. Hence the narrator had three
nindars and two glomeks. This means that the number of morms the teller gave
the narrator was
$$21(2)+12(3)=42+36=78.\eqno\hbox{\qed}$$

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

\problem (Exercise~3.63 from {\it Problem Solving Through Recreational
Mathematics\/}; originally from the {\it Greek Anthology}, compiled about
{\smfont A.D.}~500 by Metrodorus.)\enspace I am a brazen lion, a fountain; my
spouts are my two eyes, my mouth, and the flat of my right foot. My right eye
fills a jar in two days [$\hbox{1~day}=\hbox{12~hours}$], my left eye in three,
and my foot in four; my mouth is capable of filling it in six hours. Tell me
how long all four together will take to fill it.

\solution This problem is similar to Sample Problem~3.5 on page~72 of
{\it Problem Solving Through Recreational Mathematics}, the solution of which
is presented on pages 81--83.

The idea is to work with the {\it rate of flow\/} of the four spouts (measured
in, say, ``jars per hour'') rather than the times required for each of the
spouts to fill a jar. The reason this idea works is that the rates of flow from
the four spouts can be added together to give a total rate of flow from the
fountain, whereas it does not make sense to add the four times together (it
should take {\it less\/} time for a jar to be filled by all four spouts
together than by one spout alone, not more time).

We must decide on the units to use to measure the flow rates. ``Jars per hour''
seems to be a sensible choice, so let's go with that. (``Jars per day'' would
also have been reasonable.)

The right eye fills a jar in two days. A day was divided into 12~hours in the
ancient world (as is explained in the problem), so the flow of the right eye
is one jar every 24~hours, or $\frac1{24}$~jar per hour. The left eye requires
three days, or 36~hours, to fill a jar, so its flow rate is $\frac1{36}$~jar
per hour. The foot can fill a jar in four days, or 48~hours, so its flow rate
is $\frac1{48}$~jar per hour. Finally, the mouth can fill a jar in just six
hours, so it has a flow of $\frac16$~jar per hour.

The total flow of the fountain, then, is the sum of these four individual
flows. To add these fractions, we need a common denominator; the least common
denominator of 24,~36, 48, and~16 is~144, so we have
$${1\over24}+{1\over36}+{1\over48}+{1\over6}
	={6\over144}+{4\over144}+{3\over144}+{24\over144}={37\over144}.$$
Therefore, the total flow of the fountain is $\frac{37}{144}$~jar per hour.

We have a description of the flow of the fountain in jars per hour, but we
would like a description in hours per jar (because we are interested in knowing
how long it will take to fill one jar). Hours per jar is simply the reciprocal
of jars per hour; so an equivalent description of the flow of the fountain is
that it can fill jars at the rate of $\frac{144}{37}$~hours per jar. In other
words, all four spouts together can fill one jar in
$\frac{144}{37}=3\frac{33}{37}\approx3.89$~hours, or about 3~hours 54~minutes
(assuming that an hour in the ancient world was divided into 60~minutes). \qed

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

\problem There is a unique real number~$x$ that can be expressed in the
following form:
$$x=1+{1\over\displaystyle1+{\strut1\over\displaystyle1+
	{\strut1\over\strut1+\cdots\rlap{\thinspace,}}}}$$
where the dots~``$\,\cdots\,$'' mean ``and so on, forever.'' What is this
number~$x$? (This strange-looking kind of infinite fraction is called a
``continued fraction.'')

\solution It is difficult to see where to begin in this problem; the algebraic
expression appears to make no sense. For example, if we attempt to evaluate the
expression, what operation should we do first? It seems as though every step of
the evaluation has infinitely many steps that must be done before it.

Let's take on faith that this expression has a meaning (the first sentence
tells us that there is a real number that can be expressed this way) and
attempt to determine what that meaning must be. Suppose we look at the value
of $1+1/x$:
$$1+{1\over x}=1+{1\over\displaystyle1+{\strut1\over\displaystyle1+
	{\strut1\over\strut1+\cdots}}}=x.$$

Since the expression for~$x$ is infinite, adding one more ``layer'' like this
does not change it! So we have the equation
$$1+{1\over x}=x.$$
Multiplying this equation by~$x$ to get rid of the fraction, we have
$$x+1=x^2.$$
We can move everything to the right-hand side to get
$$0=x^2-x-1,$$
which is a quadratic equation of the form $ax^2+bx+c=0$ (with $a=1$, $b=-1$,
and $c=-1$). We can use the quadratic formula to solve this equation for~$x$:
$$x={-b\pm\sqrt{b^2-4ac}\over2a}={-(-1)\pm\sqrt{(-1)^2-4(1)(-1)}\over2(1)}
	={1\pm\sqrt5\over2}.$$
This gives us two solutions for~$x$, one positive and one negative
(since $\sqrt5>1$). From the expression given for~$x$ in the original problem,
we see that $x$~must be positive, because all of the numbers being added are
positive. So we reject the negative solution and conclude that
$$x={1+\sqrt5\over2}.\eqno\hbox{\qed}$$

\noindent[\thinspace This number, which is approximately equal to~1.618, is
often called the {\it golden ratio\/} because of its surprising occurrence in
many places in nature, the aesthetically pleasing form of rectangles whose side
lengths are in this ratio, and its many beautiful mathematical properties (such
as this one).\thinspace]

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

\problem In the figures below, there are $n$~points on the circumference of a
circle, and a chord is drawn between every pair of points. This divides the
circle into a number of regions. The points are chosen in such a way that no
three of the chords intersect in a single point, so that the number of regions
is maximized. How many regions would be formed if 20~points were chosen around
the circumference in this way? ({\it Be careful\/}---the ``obvious'' pattern
in the number of regions in the examples below does {\it not\/} hold in
general! You will need to count the number of regions for $n=6$, and probably
$n=7$, in order to find the general pattern.)
$$\vbox{\halign{&\quad\strut\hfil#\hfil\quad\cr
	\midfig{homework-3-sol-one-point.mps}&
	\midfig{homework-3-sol-two-points.mps}&
	\midfig{homework-3-sol-three-points.mps}&
	\midfig{homework-3-sol-four-points.mps}&
	\midfig{homework-3-sol-five-points.mps}\cr
	$n=1$&$n=2$&$n=3$&$n=4$&$n=5$\cr
	1~region&2~regions&4~regions&8~regions&16~regions\cr
}}$$

\solution Let's use $r(n)$ to denote the number of regions into which the
circle is divided when we draw lines between $n$~points on the circumference as
in this problem. For example, $r(4)=8$.

From the first five examples shown above, it appears that the number of regions
doubles each time we add another point, meaning that the sequence of the
numbers of regions is the sequence of powers of~2. This suggests the formula
$r(n)=2^{n-1}$ [the exponent is $n-1$ rather than~$n$ because $r(1)$ should
be~1, not~2]. But this is a red herring! This pattern does not continue past
$n=5$. (This shows the importance of proving that a conjecture must always be
true rather than relying on evidence gathered from a few examples.)

If we draw the pictures for $n=6$ and $n=7$, being careful to arrange the
points around the circumference so that no three chords intersect in a single
point, we discover the following.
$$\vbox{\halign{&\quad\strut\hfil#\hfil\quad\cr
	\midfig{homework-3-sol-six-points.mps}&
	\midfig{homework-3-sol-seven-points.mps}\cr
	$n=6$&$n=7$\cr
	31~regions&57~regions\cr
}}$$

\noindent This gives us the following table.
$$\vbox{\offinterlineskip
\halign{\enspace\hfil\strut$#$\hfil\enspace&\vrule#&&\enspace\hfil\strut#\hfil\enspace\cr
	n&&1&2&3&4&5&6&7\cr
	\omit&height2pt\cr\noalign{\hrule}\omit&height2pt\cr
	r(n)&&1&2&4&8&16&31&57\cr
}}$$

Let's try the technique described in class to guess a polynomial formula for
this sequence of numbers. We will take differences between successive numbers
of the sequence, and then differences between the differences, and so on, until
we reach a constant row. We write the successive differences of one row as a
new row below it and make the following table.
$$\newbox\oobox  \setbox\oobox=\hbox{00}
\def\oo#1{\hfil\strut\hbox to\wd\oobox{\hss#1\hss}\hfil}
\vbox{\offinterlineskip
\halign{\enspace\hfil\strut$#$\hfil\enspace&\vrule#&\enspace\oo{#}\ &&\oo{#}\ \cr
	n&&1&&2&&3&&4&&5&&6&&7\cr
	\omit&height2pt\cr\noalign{\hrule}\omit&height2pt\cr
	r(n)&&1&&2&&4&&8&&16&&31&&\omit\oo{57}\enspace\cr
	\noalign{\smallskip}
	&\omit&&1&&2&&4&&8&&15&&26\cr
	\noalign{\smallskip}
	&\omit&&&1&&2&&4&&7&&11\cr
	\noalign{\smallskip}
	&\omit&&&&1&&2&&3&&4\cr
	\noalign{\smallskip}
	&\omit&&&&&1&&1&&1\cr
}}$$

We seem to have reached a constant row, after taking differences four times.
This suggests that the formula for~$r(n)$ is a quartic polynomial, that~is, a
polynomial of degree~4. The general form of a quartic polynomial (in the
variable~$n$) is
$$r(n)=an^4+bn^3+cn^2+dn+e,\eqno(8)$$
where $a$,~$b$, $c$, $d$, and~$e$ are constants. We can find the values of
these constants by plugging into equation~(8) some values of $n$ and~$r(n)$
that we know. For example, we know that when $n=1$ the value of~$r(n)$ is~1.
Using these values in equation~(8) gives us
$$1=a\cdot1^4+b\cdot1^3+c\cdot1^2+d\cdot1+e,$$
which is to say
$$a+b+c+d+e=1.$$
Since we have five unknowns, we are going to need to get five equations, so we
will do this with four more pairs of values for $n$ and~$r(n)$. Using $n=2$ and
$r(n)=2$, we get
$$2=a\cdot2^4+b\cdot2^3+c\cdot2^2+d\cdot2+e,$$
so
$$16a+8b+4c+2d+e=2.$$
Using $n=3$ and $r(n)=4$, we have
$$4=a\cdot3^4+b\cdot3^3+c\cdot3^2+d\cdot3+e,$$
or
$$81a+27b+9c+3d+e=4.$$
Similarly, with $n=4$ and $r(n)=8$ we obtain
$$256a+64b+16c+4d+e=8,$$
and with $n=5$ and $r(n)=16$ we find
$$625a+125b+25c+5d+e=16.$$
Together, this gives us a system of five linear equations in five unknowns:
$$\eqalignno{
	a+\phantom{000}b+\phantom{00}c+\phantom0d+e&=\phantom01,&(9)\cr
	16a+\phantom{00}8b+\phantom04c+2d+e&=\phantom02,\cr
	81a+\phantom027b+\phantom09c+3d+e&=\phantom04,\cr
	256a+\phantom064b+16c+4d+e&=\phantom08,\cr
	625a+125b+25c+5d+e&=16.\cr
}$$
We shall solve this system by substitution. (Other methods can be used too.)

We begin by solving equation~(9), the first equation above, for the
variable~$e$, and we get
$$e=1-a-b-c-d.\eqno(10)$$
We substitute this expression for~$e$ in each of the other four equations:
$$\eqalign{
	16a+\phantom{00}8b+\phantom04c+2d+(1-a-b-c-d)&=\phantom02,\cr
	81a+\phantom027b+\phantom09c+3d+(1-a-b-c-d)&=\phantom04,\cr
	256a+\phantom064b+16c+4d+(1-a-b-c-d)&=\phantom08,\cr
	625a+125b+25c+5d+(1-a-b-c-d)&=16.\cr
}$$
We should now combine like terms on the left-hand sides and move the constants
to the right-hand sides to obtain the following system of four equations in
four unknowns.
$$\eqalignno{
	15a+\phantom{00}7b+\phantom03c+\phantom1d&=\phantom01,&(11)\cr
	80a+\phantom026b+\phantom08c+2d&=\phantom03,\cr
	255a+\phantom063b+15c+3d&=\phantom07,\cr
	624a+124b+24c+4d&=15.\cr
}$$

\noindent Now we can solve equation~(11), the first equation above, for the
variable~$d$; we get
$$d=1-15a-7b-3c.\eqno(12)$$
Substituting this expression for~$d$ in each of the other three equations, we
have
$$\eqalign{
	80a+\phantom026b+\phantom08c+2(1-15a-7b-3c)&=\phantom03,\cr
	255a+\phantom063b+15c+3(1-15a-7b-3c)&=\phantom07,\cr
	624a+124b+24c+4d&=15.\cr
}$$
We multiply out the left-hand sides to remove the parentheses and then combine
like terms on the left-hand sides and move the constants to the right-hand
sides. This gives us a system of three equations in three unknowns.
$$\eqalignno{
	50a+12b+\phantom02c&=\phantom01,&(13)\cr
	210a+42b+\phantom06c&=\phantom04,\cr
	564a+96b+12c&=11.\cr
}$$

\noindent Next we solve equation~(13), the first equation above, for the
variable~$c$. We have
$$2c=1-50a-12b,$$
which means
$$c=\frac12-25a-6b.\eqno(14)$$
If we substitute this expression for~$c$ in the other two equations, we get
$$\eqalign{
	210a+42b+\phantom06(\frac12-25a-6b)&=\phantom04,\cr
	564a+96b+12(\frac12-25a-6b)&=11.\cr
}$$
Again multiplying out the left-hand sides, combining like terms, and moving
the constants to the right-hand sides, we obtain
$$\eqalignno{
	60a+\phantom06b&=1,&(15)\cr
	264a+24b&=5.&(16)\cr
}$$

\noindent Continuing in this pattern, we solve equation~(15) for~$b$. We find
$$6b=1-60a,$$
so
$$b=\frac16-10a.\eqno(17)$$
We substitute this into equation~(16) to get
$$264a+24(\frac16-10a)=5,$$
which, after simplification, becomes $24a=1$. Therefore we have $a=\frac1{24}$.

Now we can begin the process of back-substituting known values of variables
into previous equations in order to determine the values of the other
variables. We begin by substituting $a=\frac1{24}$ into equation~(17), which
gives us
$$b=\frac16-10(\frac1{24})=-\frac14.$$
We can substitute the known values of $a$ and~$b$ into equation~(14) to get
$$c=\frac12-25(\frac1{24})-6(-\frac14)=\frac{23}{24},$$
which we can then use in equation~(12) to find
$$d=1-15(\frac1{24})-7(-\frac14)-3(\frac{23}{24})=-\frac34.$$
Finally, using the known values of $a$,~$b$, $c$, and~$d$ in equation~(10), we
see that
$$e=1-\frac1{24}-(-\frac14)-\frac{23}{24}-(-\frac34)=1.$$
So we have found the values of the coefficients $a$,~$b$, $c$, $d$, and~$e$. We
substitute these values into the quartic polynomial function~(8) to get a
guess for a formula for~$r(n)$:
$$r(n)=\frac1{24}n^4-\frac14n^3+\frac{23}{24}n^2-\frac34n+1.$$

\goodbreak

We can check our algebra by plugging in some values for~$n$ (say, $n=5$) and
making sure that our formula gives us the correct known value of~$r(n)$. In
class I gave the value $r(10)=256$ as a hint; let's verify that this is the
value predicted by our formula. We have
$$r(10)=\frac1{24}(10^4)-\frac14(10^3)+\frac{23}{24}(10^2)-\frac34(10)+1=256,$$
so the formula seems to check out.

Thus, based on this formula, we can predict that if 20~points are placed around
the circumference of a circle and chords are drawn as described in the problem,
the number of regions produced will be
$$r(20)=\frac1{24}(20^4)-\frac14(20^3)+\frac{23}{24}(20^2)-\frac34(20)+1=5{,}036.\eqno\hbox{\qed}$$

\noindent[\thinspace In the first paragraph of this solution I pointed out the
importance of proving mathematical conjectures rather than relying on evidence
based on a few examples. Strictly speaking, we have not proved that our formula
for~$r(n)$ is correct, so we must regard our answer as merely a conjecture,
though it is certainly a well-reasoned, educated guess based on substantial
evidence. In fact, this formula {\it is\/} correct, though the proof of this
fact requires some concepts we have not seen yet. A more interesting way to
write the formula for~$r(n)$ is
$$r(n)={n-1\choose4}+{n-1\choose3}+{n-1\choose2}+{n-1\choose1}+{n-1\choose0}.$$
These symbols are {\it binomial coefficients}, which we will discuss at some
point in this course.\thinspace]

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

\problem (From {\it Challenging Problems in Algebra\/} by Alfred~S. Posamentier
and Charles~T. Salkind.)\enspace A shopkeeper orders 19~large and 3~small
packets of marbles, all alike. When they arrive at the shop, he finds the
packets broken open with all the marbles loose in the container. Can you help
the shopkeeper make new packets with the proper number of marbles in each, if
the total number of marbles is~224?

\solution Let's introduce the variables $L$ and~$S$ to represent the number of
marbles in one large packet and one small packet, respectively. Since there are
19~large and 3~small packets of marbles, the total number of marbles is
$19L+3S$. We are told that this number is~224, so we have the equation
$$19L+3S=224.$$

Since the number of marbles in a packet should be a whole number, and hence the
values of $L$ and~$S$ must be integers, we see that this is a (linear)
Diophantine equation. Furthermore, the values of $L$ and~$S$ should be
{\it positive\/} integers.

The most straightforward method of solving this problem, without the use of
special techniques for solving linear Diophantine equations, is probably simply
to guess. In order to put some bounds on the values we should guess, let's
consider how many marbles might be in a large packet. Certainly there should be
at least one, so $L\ge1$. On the other hand, $224\div19\approx11.789$, so there
cannot be more than 11~marbles in a large packet (if there were~12, then the
total number of marbles in the large packets alone would be $19\times12=228$).
Therefore we can restrict our search to values of~$L$ in the range
$1\le L\le11$.

In addition, since the number of marbles in a large packet should be more than
the number of marbles in a small packet, we should have $L>S$. Since $L\le11$,
we must have $S\le10$. So the total number of marbles in the 3~small packets
can be no more than~30.

If there are $L$~marbles in one large packet, then the total number of marbles
in the large packets is~$19L$, so the small packets must contain a total of
$224-19L$~marbles. Since there are 3~small packets, the value $224-19L$ should
be divisible by~3 (and it should be no more than~30, as noted above). Let's
make a table of the possible values of~$L$ and the corresponding values of
$224-19L$.
$$\vbox{\offinterlineskip
\halign{\enspace\hfil\strut$#$\hfil\enspace&\vrule#&&\enspace\hfil\strut#\hfil\enspace\cr
	L&&1&2&3&4&5&6&7&8&9&10&11\cr
	\omit&height2pt\cr\noalign{\hrule}\omit&height2pt\cr
	224-19L&&205&186&167&148&129&110&91&72&53&34&15\cr
}}$$

Out of the values in the bottom row, the only ones which are divisible by~3 are
186,~129, 72, and~15, corresponding to $L=2$,~$L=5$, $L=8$, and~$L=11$,
respectively. But three of these values are greater than~30, so the only
possibility is $L=11$, which means that $S=(224-19\times11)/3=5$. So a large
packet contains 11~marbles and a small packet contains 5~marbles. \qed

\nobreak\medskip

\noindent[\thinspace The solution given by Posamentier and Salkind is somewhat
more clever than this, although it uses essentially the same ideas. I have
quoted it below.\thinspace]

{\nobreak\medskip\narrower

\noindent Represent the number of marbles in a large packet by~$L$ and the
number in a small packet by~$S$. Then $19L+3S=224$, $S=74-6L+{2-L\over3}$.
Since $S$ and~$L$ are positive integers, $2-L\over3$~must be an integer. If
$L=2$, not a likely value, ${2-L\over3}=0$; otherwise $2-L\over3$ is negative.
Let us put ${2-L\over3}=-k$ so that $L=2+3k$. Since $74-6L+{2-L\over3}>0$,
$74>6(2+3k)+k$ so that $k\le3$. Also, $S=74-6(2+3k)-k=62-19k$. Since $L>S$,
$2+3k>62-19k$ so that $k>2$. Since $2<k\le3$, $k=3$. Therefore, $L=2+3k=11$ and
$S=62-19k=5$.

The values $L=11$, $S=5$ satisfy the conditions of the problem uniquely.

\par}

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

\problem (From a short story, ``Coconuts,'' by Ben Ames Williams.)\enspace
$\ldots$~So at last Wadlin told him. ``Well,'' he explained, ``according to the
way the thing was given to me, five men and a monkey were shipwrecked on a
desert island, and they spent the first day gathering coconuts for food. Piled
them all up together and then went to sleep for the night.

``But when they were all asleep one man woke up, and he thought there might be
a row about dividing the coconuts in the morning, so he decided to take his
share. So he divided the coconuts into five piles. He had one coconut left
over, and he gave that to the monkey, and he hid his pile and put the rest all
back together.''

He looked at Marr; the man was listening attentively.

``So by and by the next man woke up and did the same thing,'' Wadlin continued.
``And he had one left over, and he gave it to the monkey. And all five of the
men did the same thing, one after the other, each one taking a fifth of the
coconuts in the pile when he woke up, and each one having one left over for the
monkey. And in the morning they divided what coconuts were left, and they came
out in five equal shares.''

He added morosely, ``Of course each one must have known there were coconuts
missing; but each one was guilty as the others, so they didn't say anything.''

Marr asked sharply, ``But what's the question?''

``How many coconuts were there in the beginning?'' Wadlin meekly explained.

\solution This is a hard puzzle. In Mr.~Williams' tale, Wadlin is an accountant
who works for a building contractor named Dean Story, whose competitor is Marr.
Both Story and Marr intend to place bids on a building contract. The night
before the bids are due, Wadlin, knowing Marr's love of puzzles, gives this
problem to him. Marr stays up till dawn trying to solve it and thus misses the
deadline, allowing Story to win the bid at a comfortable profit.

Williams' story was first published in {\it The Saturday Evening Post\/}
in~1926. The answer to the puzzle was not given in the story. In the first week
after it was published the {\it Post\/} received over 2,000~letters from
readers asking for the answer or offering solutions. The editor-in-chief,
George Horace Lorimer, sent a desperate telegram to Williams that read,
``{\smfont FOR THE LOVE OF MIKE}, {\smfont HOW MANY COCONUTS}? {\smfont HELL
POPPING AROUND HERE}.''

It is tempting to begin to write equations, so let's do that. Suppose we let
$n$ represent the number of coconuts in the beginning, $a$~through~$e$
represent the numbers of coconuts that the first man through the fifth man hid
in the middle of the night, and $f$ represent the number of coconuts taken by
each man in the morning. Note that these variables all represent positive
integers, so the equations that we write will be Diophantine equations.

We are told that the first man divided the $n$~coconuts into five piles (each
of size~$a$) and found there was one left over. So $n$ is one more than a
multiple of~5; in particular, $n=5a+1$. The first man gave one coconut to the
monkey, hid one of the five piles, and put the other four piles back together.
So when the second man woke up there were $4a$~coconuts left.

Now the second man did the same thing, so $4a=5b+1$. Similarly, we have
$4b=5c+1$, $4c=5d+1$, and $4d=5e+1$. The fifth man put the remaining
$4e$~coconuts back together in a pile, and these were split evenly among the
five men in the morning, so $4e=5f$. So we have the following system of six
linear Diophantine equations in seven unknowns:
$$\eqalignno{
	n&=5a+1,&(18)\cr
	4a&=5b+1,&(19)\cr
	4b&=5c+1,&(20)\cr
	4c&=5d+1,&(21)\cr
	4d&=5e+1,&(22)\cr
	4e&=5f.&(23)\cr
}$$

One reason this is a challenging puzzle is that there are more unknowns than
there are equations, so standard algebraic techniques cannot be used to solve
it. Let's attempt to reduce the number of variables by substitution. We can
solve equations (19) through~(23) for the variables $a$ through~$e$ by dividing
by~4, giving us
$$\eqalign{
	a&=\frac54b+\frac14,\cr
	b&=\frac54c+\frac14,\cr
	c&=\frac54d+\frac14,\cr
	d&=\frac54e+\frac14,\cr
	e&=\frac54f.\cr
}$$
Repeatedly substituting variables into equation~(18), and then simplifying, we
get
$$\eqalign{
	n&=5a+1\cr
	&=5(\frac54b+\frac14)+1\cr
	&=5[\frac54(\frac54c+\frac14)+\frac14]+1\cr
	&=5\bigl(\frac54[\frac54(\frac54d+\frac14)+\frac14]+\frac14\bigr)+1\cr
	&=5\bigl[\frac54\bigl(\frac54[\frac54(\frac54e+\frac14)+\frac14]+\frac14\bigr)+\frac14\bigr]+1\cr
	&=5\Bigl(\frac54\bigl[\frac54\bigl(\frac54[\frac54(\frac54f)+\frac14]+\frac14\bigr)+\frac14\bigr]+\frac14\Bigr)+1\cr
	&=\frac{15{,}625}{1{,}024}f+\frac{2{,}101}{256}.\cr
}$$
We multiply both sides of this equation by~1,024 to clear the fractions and get
the linear Diophantine equation
$$1{,}024n=15{,}625f+8{,}404.\eqno(24)$$

This equation tells us a few things. Observe that if $n$ increases by~1 the
left-hand side will increase by~1,024, and in general two possible values of
the left-hand side (corresponding to two possible values of~$n$) must differ by
a multiple of~1,024. Likewise, if $f$ increases by~1 the right-hand side will
increase by~15,625, and in general two possible values of the right-hand side
must differ by a multiple of~15,625. Since $1{,}024=2^{10}$ and $15{,}625=5^6$,
these two numbers are relatively prime, so
$\lcm(1{,}024,\,15{,}625)=1{,}024\times15{,}625$; this is the smallest amount
by which both sides of the equation can increase while remaining in balance.

Hence, if we have some numbers $n$ and~$f$ that are a solution to
equation~(24), we can add 15,625 to~$n$ (and 1,024~to~$f$) to obtain another
solution. Of course, this means that we could add any multiple of~15,625 to~$n$
to get another solution. We could also subtract any multiple of~15,625 from~$n$
for the same reason. So, if there are any solutions at all to the Diophantine
equation~(24), there are infinitely many of them, and we can go from one of
them to any other by increasing or decreasing~$n$ by a multiple of~15,625.

This equation can be solved by standard methods for solving linear Diophantine
equations, but this is rather tedious. There is an extraordinarily brilliant
and creative solution that uses {\it blue coconuts}, which was first given by
Norman Anning in~1912 (though the problem he considered used apples instead of
coconuts). The key insight that led to this solution is that the monkey is the
complicating element in the puzzle---if the division into five parts came out
even every time, the puzzle would be much simpler.

Let's imagine that, in addition to the pile of coconuts, there are four
imaginary blue coconuts. Since the original pile of coconuts gave a remainder
of~1 when it was divided into five parts, these four blue coconuts will allow
the pile to be divided into five parts evenly. When the first man wakes up and
divides the pile, four of the smaller piles will have a blue coconut on top,
while the fifth pile will contain only regular coconuts (and so it has one more
regular coconut than the other piles do---this is the coconut that was
originally given to the monkey). Let's say the man hides this fifth pile, and
puts all the rest of the coconuts, including the four blue coconuts, back
together. Then the first man takes away the same number of coconuts as he did
in the original puzzle; the ``extra'' coconut is in his own hoard this time,
instead of having been given to the monkey. So, when the first man goes to
sleep, the pile of coconuts looks just as it did at this point in the original
puzzle, except that it also contains the four imaginary blue coconuts.

In turn, the other men each wake up and do the same thing. The big pile of
coconuts is always divided into five parts with no remainder, because of the
four blue coconuts. Each man removes from the pile the same number of coconuts
as he did in the original puzzle, but instead of giving the ``extra'' coconut
to the monkey he keeps it for himself. The four blue coconuts remain in the big
pile.

Every time one of the men wakes up and takes his share, the number of coconuts
in the big pile is reduced by one-fifth, that~is, the number of coconuts is
multiplied by~$\frac45$. So, after all five men have taken their shares, the
number of coconuts in the big pile is $(\frac45)^5$, or~$\frac{4^5}{5^5}$, of
the original number. This must be an integer, so the original number of
coconuts (including the blue ones) must be divisible by~$5^5$, which is~3,125.

This means that the smallest possible number of regular coconuts in the
original pile is~3,121 (after taking out the four blue coconuts). So far we
haven't verified that this number will work, because we haven't checked to see
whether the pile of coconuts that remains in the morning can be divided evenly
into five piles, but we can check that now:

There are 3,121~coconuts in the original pile. The first man wakes up, divides
the pile into five equal parts having 624~coconuts in each, and throws one
coconut to the monkey. He hides one pile and puts the other four back together,
so there are now $624\times4=2{,}496$~coconuts in the pile. The second man
divides the pile into five equal parts having 499~coconuts in each, throws one
coconut to the monkey, hides one pile, and puts the remaining
$499\times4=1{,}996$~coconuts back together. The third man divides these into
five parts of 399~coconuts each, throws a coconut away, hides a pile, and puts
the remaining $399\times4=1{,}596$~coconuts back together. The fourth man makes
five piles of 319~coconuts, throws a coconut to the monkey, hides a pile, and
puts the other $319\times4=1{,}276$~coconuts back together. Finally, the fifth
man divides the pile into five parts of 255~coconuts each, throws one last
coconut to the monkey, hides his pile, and puts back
$255\times4=1{,}020$~coconuts. This is the number of coconuts that are divided
in the morning, and it is divisible by~5, so this solution works.

Thus there were 3,121~coconuts in the original pile. As previously noted, we
can add or subtract any multiple of~15,625 to this number to get another
solution. (Some of these solutions will have ``negative coconuts'' in the
original pile, which is meaningless in a physical sense; but thinking about
solutions using negative coconuts and then adjusting the answer at the end by
adding~15,625 is another creative approach to solving this puzzle. In fact, the
blue coconuts used in the solution presented here can be thought of as
manifestations of negative coconuts.) \qed

\nobreak\medskip

\noindent[\thinspace For more about this problem, including an explanation of
the solution using negative coconuts, see the chapter called ``The Monkey and
the Coconuts'' in {\it The Colossal Book of Mathematics\/} by Martin
Gardner.\thinspace]

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

\bye
