\documentclass[12pt]{article}
\usepackage{latexsym,amsmath,epsfig}
\newcommand{\ds}{\displaystyle}
\newcommand{\vp}{$\vphantom{\big|}$}

\newcommand{\R}{\textbf{R}}
\newcommand{\Item}{\item{$\Box$}\quad}

\newcommand{\Answer}[1]{$\phantom{.}$\hfill
        #1\quad\fboxsep 20pt \fbox{$\phantom{\Big|Answer}$}} 

\newcommand{\MyTallAnswer}[2]{$\phantom{.}$\hfill
        #1\quad\fboxsep 20pt\fbox{$\vphantom{\Big|}#2$}}

\newcommand{\MyAnswer}[2]{$\phantom{.}$\hfill
        #1\quad\fboxsep 5pt\fbox{$\vphantom{\Big|}#2$}}

\newcommand{\soln}{\paragraph{Solution}}
\newcommand{\sep}{{\medskip\hrule\bigskip}}
\newcommand{\blank}{\underline{$\phantom{A blank}$}}

\setlength{\textwidth}{6.5in}
\setlength{\topmargin}{-0.5in}
\setlength{\oddsidemargin}{0in}
\setlength{\textheight}{9.0in}
\begin{document}
\begin{center}

\textbf{College of the Holy Cross} \\
\textbf{MONT 104Q -- Mathematical Journeys}\\
\textbf{Solutions for Final Exam -- December 18, 2015}
\end{center}
\vskip 10pt
\noindent
I.  G. H. Hardy included two proofs from Euclid's {\it Elements} as
prime examples of beautiful, serious mathematics in his book 
{\it A Mathematician's Apology}.  The first was the proof that there are infinitely many
prime numbers.  
\begin{enumerate}
\item[A)]  (5) Prove this result using Euclid's method.
\item[]  Assume that the list of all primes is finite, and that this 
list contains just the primes $2,3,\ldots, P$.  Then form the integer 
$$Q = 2\cdot 3 \cdot \cdots \cdot P + 1.$$
Since $Q$ is an integer, it must be divisible by some prime number. 
But each of the primes in the list $2,3,\ldots, P$ leaves a remainder
of $1$ when it divides $Q$.  Therefore none of the primes in the list
can divide $Q$ and this is a contradiction.  Hence the claim 
that there are infinitely many primes is proved.  
\item[B)]  (5) What is the name of the method of proof that Euclid (and you)
used here?  Describe briefly how that method works.  Hardy say this is ``a 
far finer gambit than any chess gambit:  a chess player may offer 
the sacrifice of a pawn or even a piece, but a mathematician 
offers {\it the game}?''  What does he mean by that?
\item[]  The name of this proof technique is \emph{proof by contradiction}, 
or \emph{reductio ad absurdum}.  It works like this: To prove a statement, you 
begin by assuming the negation of that statement (that is by assuming that the 
statement you want to show is \emph{false}).  Then you reason from the negation
and try to produce a contradiction.  This shows that the negation must be 
false and the statement we were trying to prove must be true.  Hardy is referring
to the fact that when a mathematician structures a proof this way, it can 
seem as though he or she is offering the whole ``game'' (the whole statement
to be proved) by assuming that is false to begin with.  He compares this 
to a gambit in chess, where one might offer a pawn or a piece for the opponent
to capture while gaining an advantage in the process.  The chess analog of the 
mathematical maneuver, Hardy says, would be to offer \emph{all one's pieces} or to 
offer to \emph{resign the whole game}, and then seize the advantage.   
\end{enumerate}
\vskip 10pt 
\noindent
II.  
\begin{enumerate}
\item[(A)] (10)  Give the statement and proof of Proposition 29 in Book I of 
Euclid's {\it Elements}. 
\item[]  The statement is that if a transversal $GH$ falls on two parallel lines $AB$ and $CD$,
then the alternate interior angles are equal, the corresponding angles are
equal, and the interior angles on one side of the transversal add to two
right angles.  
\begin{figure}
\begin{center}
\includegraphics[width=.5\linewidth]{EuclidI28.png}
\caption{Figure for Proposition 29, Book I}
\end{center}
\end{figure}

\item[]  Here's the way the proof works:  Using a proof by contradiction, 
Assume that the first part does not hold, say that $\angle BEF \ne \angle CFE$.
If this is true, one must be strictly smaller, say $\angle BEF < \angle CFE$.
But then if we add $\angle DFE$ to both sides of that inequality we get 
(by what we called ``Common Notion 6'' when we discussed it -- that's my 
name, not Euclid's by the way)
$$\angle BEF + \angle DFE < \angle CFE + \angle DFE = {\rm 2\ right\ angles}$$
(using Proposition 13).  By Postulate 5, this implies that if we extend 
lines $AB$ and $CD$, they must meet on the side of the transversal containing
$B,D$.  But that contradicts the assumption that $AB$ and $CD$ are parallel lines.  
The remaining parts now follow from other facts proved previously.  The corresponding
angles $\angle BEF$ and $\angle DFH$ are equal because $\angle BEF = \angle CEB$
from the first part, but then also $\angle BEF = \angle DFG$ since vertical 
angles at the intersection of two lines are equal (Prop. 15).  The desired statement
then follows from Common Notion 1.  This also implies the final part of the proposition. 
\item[(B)] (5) How does this proposition relate to Proposition 27?  
What is special about the place of Proposition 29 in Book I?  Explain briefly. 
\item[]  The parts of this statement are the \emph{converses} of parts of Proposition 
27.  For instance, part of Prop. 27 says that if opposite interior angles at the
transversal are equal, then the two lines are parallel.   Proposition 29 is special
in the logical development of Book I of the {\it Elements} because it is the first
time Euclid uses Postulate 5.  Everything up to this point is true even in 
geometries where Postulates 1 - 4 are true, but Postulate 5 does not hold.
\end{enumerate}
\vskip 10pt
\noindent
III. (10)  What does it mean to say that a polyhedron is \emph{convex}?  What is
true about the number of vertices $V$, the number of edges $E$, and the number
of faces $F$ in that case?  
\vskip 10pt
\noindent
A polynohedron $X$ is convex if for all points $P,Q$ contained in $X$, the straight line
segment from $P$ to $Q$ is completely contained in $X$.  

The relation between $V,E,F$ is, of course the one discussed in \emph{Proofs and 
Refutations}, the Euler relation: 
$$V - E + F = 2.$$
\vskip 10pt
\noindent
IV.  In our proof of the ``power theorem'' about the remainders $r^{m-1}\ R\ m$, where
$m$ is prime and $1 \le r \le m - 1$,
\begin{enumerate}
\item[(A)] (5)  The first step was to show that for each fixed $r$ as above, the remainders
$r\ R\ m$, $(2\cdot r)\ R\ m$, ... , $((m - 1)\cdot r)\ R\ m$ were all distinct.  Show this 
is true.  You may assume the statement of Euclid's lemma about primes: if a prime
$m$ divides a product of integers $c \cdot d$, then $m$ divides $c$ or $m$ divides $d$.    
\item[] Arguing again by contradiction, suppose that $(a\cdot r)\ R\ m = (b \cdot r)\ R\ m$
for some $1 \le a < b \le m - 1$.  By general properties of remainders, this says
$m$ must divide the integer $b r - a r = (b - a) r$.  Since $m$ is prime, Euclid's Lemma
implies that $m$ must divide either $b - a$ or $r$.  But the largest $b - a$ could be 
is $m - 2$ and $b - a > 0$, so $m$ cannot divide $b - a$.  Similarly, $m$ cannot divide
$r$ since $1 \le r \le m - 1$.  This gives a contradiction.  Hence the $(t\cdot r)\ R\ m$
must all be distinct (i.e. different) as $t$ ranges from $1$ to $m - 1$.
\item[(B)] (5)  What does the fact from part A show about the remainders $r^{m-1}\ R\ m$?
Explain.
\item[]  It implies that these are all equal to 1:  $r^{m-1}\ R\ m = 1$ for all $r$
with $1 \le r \le m - 1$.  The reason is that we can multiply together all the numbers
$(t \cdot r)\ R\ m$ and take the remainder on division by $m$.  On the one hand, the 
fact that those remainders are all distinct implies that the product is equal to $(m-1)!\ R\ m$.
But then we also have that 
$$(m-1)!\ R\ m = r^{m-1} (m-1)!\ R\ m$$
which implies that $m$ divides $(m-1)! (1 - r^{m-1})$.  As in the first part of the problem,
since $m$ is prime, we can apply Euclid's lemma to see that $m$ must divide either
$(m-1)!$ or $1 - r^{m-1}$.  The first is impossible because all of the factors in 
$(m - 1)!$ are strictly less than $m$.  So $m$ must divide $1 - r^{m-1}$.  But that 
shows that $r^{m-1}\ R\ m = 1$ as claimed.
\end{enumerate}
\vfil\eject
\noindent
V.  Proposition 47 in Book I of the {\it Elements} is a form of the Pythagorean theorem,
illustrated by the figure above.  Use the labeling here in your answers to all parts.
\begin{figure}
\begin{center}
\includegraphics[width=.5\linewidth]{EuclidI47.jpg}
\caption{Figure for Proposition 47, Book I}
\end{center}
\end{figure}
Euclid's form of the statement is that the area of the square on the hypotenuse of the 
right triangle $\Delta ABC$ is equal to the sum of the areas of the squares on the sides.
\begin{enumerate}
\item[(A)] (5)  How is the dotted line $AM$ in the figure constructed?
\item[] {\it Solution:}  It's constructed to pass through $A$ and be {\it parallel} to 
the line containing $BD$.  The construction for that is given in a previous proposition
(Proposition 31, to be exact).
\item[(B)] (5)  In the first part of the proof, Euclid shows that $\Delta GBF$ has the same
area as what other triangle in the figure?  Why does that follow?
\item[] {\it Solution:}  $\Delta GBF$ has the same area as $\Delta CBF$. This follows
because those two triangles have the same base and are in the same parallels (Proposition 37).
Euclid establishes that $CG$ and $FB$ lie on parallel lines by considering the alternate
interior angles for the transversal line containing $AB$.
\item[(C)] (5)  The second part of the proof consists of showing that $\Delta FBC$ and 
$\Delta ABD$ are congruent.  How does that follow?  (Show that is true using one of the 
triangle congruence results proved before in Book I.)  
\item[] {\it Solution:}  
We have $FB = AB$ since they are two sides of the same square.  Similarly $BC = BD$ since
they are two sides of the same square.  Finally, $\angle FBC = \angle FBA + \angle ABC =
\angle ABC + \angle CBD = \angle ABD$, where the middle equality uses the facts
that $\angle FBA$ and $\angle CBD$ are both right angles and Postulate 4. Then
$\Delta FBC$ and $\Delta ABD$ are congruent by the SAS congruence criterion (Proposition 4).
\item[(D)] (5)  How does Euclid conclude that $ABFG$ and $BLMD$ have the same area?  And
how does he conclude the proof?
\item[] {\it Solution:}  First he shows that $\Delta ABD$ and $\Delta BDM$ have
the same area using Proposition 37 again.  Then Common Notion 1 says $\Delta GBF$ and
$\Delta BDM$ have the same area.  But $\Delta GBF$ has half the area of the square
$ABFG$ and $\Delta BDM$ has half the area of the rectangle $BLMD$.  So $ABFG$ and 
$BLMD$ also have the same area (Common Notion 2).  Euclid concludes the proof by 
saying that a similar argument shows the area of the other square $ACKH$ is 
equal to the area of the rectangle $LMEC$.  Then adding we get that the area of the
square $BDEC$ is equal to the sum of the areas of the squares $ABFG$ and $ACKH$.  
\end{enumerate}
\vskip 10pt
\noindent
VI.  Essay.  (35)
\begin{enumerate}
\item[] {\bf Option A:} Oliver Heaviside, 1850-1925, an English engineer, applied mathematician, 
and physicist, once wrote the following about the role of Euclid in mathematical education in 
his time in England:  ``As to the need of improvement there can be no question whilst the reign 
of Euclid continues.  My own idea of a useful course is to begin with arithmetic, 
and then not Euclid but algebra.  Next, not Euclid, but practical geometry, solid 
as well as plane; not demonstration, but to make acquaintance. Then not Euclid, 
but elementary vectors, conjoined with algebra, and applied to geometry ... Elementary 
calculus should go on simultaneously ... . Euclid might be an extra course for 
learned men, like Homer.  But Euclid for children is barbarous.''  On the other hand, 
about 5 years ago, Peter Rudman, a contemporary physicist, wrote this: ``High school 
mathematics education today, ... , 
all too often neglects the derivations where mathematics is learned and emphasizes 
memorizing the equations that provide quick solutions in the standardized tests but 
that are then rapidly forgotten ... .''  What aspects of mathematics does each of 
these authors seem to value most highly and think students should learn?  How does 
what each of them says relate to the ideas of G. H. Hardy in {\it A Mathematician's 
Apology}?  Why might Heaviside say that teaching Euclid to children is ``barbarous?''  
Was your high school mathematics more or less like what Heaviside is recommending?  
Was your experience like that Rudman describes?  Do you think that emphasizing proofs 
more would make mathematics more interesting for more people?  Or is that too much 
to hope for?
\item[] {\it Model response:}  Heaviside seems to be stressing the parts of mathematics
that are valuable for practical applications:  arithmetic, ``practical geometry,''
vectors, algebra, calculus.  He specifically says that in geometry he wants 
students to ``make acquaintance,'' i.e. to learn the basic language, probably
formulas for areas, volumes, etc. but \emph{not to focus on ``demonstration''}
(i.e. proofs).  He says the study of Euclid might come later for those who 
will go on to specialize in mathematics, but that Euclid is inappropriate for
beginning students.  Rudman, on the other hand, thinks that just learning 
facts and memorizing formulas is not worthwhile because it does not promote
real learning about logical reasoning and problem solving.  He sees the 
derivations (the proofs) as the place where
real mathematics happens and real learning takes place.  Rudman's point of 
view is much closer to Hardy's than Heaviside's is.  In fact it's probably
just the parts of mathematics that Heaviside is really committed to that
Hardy would find ``ugly'' and utilitarian.  I think the most likely reason 
for Heaviside's idea that teaching Euclid to children is ``barbarous''
is probably a combination of several things.  First, if Euclid is taught
poorly, it can end up being more about arcane and meaningless definitions
of not very useful terms, about following particular formats for
writing down proofs, about learning hard-seeming proofs for ``obvious''
facts, and so forth.  If that's the way students are taught, it can 
be just as dull and stifling as the worst of ``teaching to the test'' 
(what Rudman is concerned about).  [For the last section, I'll just
be looking for whether you can articulate reasonable ideas about the best way
of teaching mathematics and  
about your own experience in previous courses and --no ``right'' or ``wrong''
answers there.]
\item[] {\bf Option B:}  (If you are choosing this option, ask Prof. Little for
a copy of the poem to consult while you are writing.) 
The poem {\it Ithaka} by C. Cavafy clearly draws on themes from the {\it Odyssey}, but 
does it just retell parts of Homer's story, or does it end up making something quite 
different of them?  In particular, is the return of Odysseus the main point here?  If not, 
what is the main point?
Why doesn't Cavafy mention Telemachus or Penelope? Finally, how do you think what 
Cavafy is saying here relates to the CHQ theme (especially the ``how then shall we
live?'' part)?
\item[] {\it Model response:}  In his poem {\it Ithaka}, Cavafy is drawing on
episodes and situations from the {\it Odyssey} (the Laistrygonians, the Cyclops, 
angry Poseidon, etc.)  But Cavafy is definitely making his own use of those characters and 
images and {\it not} just retelling the story Homer told.  For Homer, in a sense,
Odysseus' return to Ithaca from the Trojan War is the whole point of the story 
(especially the way his ancient Greek listeners and readers would have understood it). 
Odysseus' journey is full of obstacles and perils (including the Laistrygonians, the Cyclops, 
angry Poseidon, etc.)  The story of Telemachus' parallel journey to manhood
is important too, as is Penelope's strength and cleverness in keeping the suitors
at bay to make it possible for Odysseus' to regain his kingdom.  
But Cavafy is using those themes in a much more metaphorical and psychological 
sense.  He is essentially offering the reader his advice on how to live a good and meaningful
life.  He says, in effect:  
First and foremost, value the journey of life itself over any ultimate destination.
Hope the journey lasts long and that you find great pleasure in all the wonderful
things life on earth has to offer: ``sensual perfumes," ``fine things," ``stores of knowledge."
Keep the destination in mind but don't let it hurry you.  Don't be too afraid of the perils 
(the Laistrygonians, the Cyclops, angry Poseidon, etc.) because, in some ways, the 
worst perils in life can be the ones we make for ourselves (``you won't encounter
them unless you bring them along inside your soul, unless your soul sets them up 
in front of you'').  And when you come to your final destination, hope that you 
have become so wise and full of experience through your journey that, even if the 
destination ends up seeming disappointing, you will understand what the purpose of your
journey has been and you will arrive at that destination satisfied with what 
you have done in your life.

\item[] This ties in very closely with the ``how then shall we live?'' aspect
of our CHQ theme, of course.  The poem is essentially one person's answer to 
that question.  One might argue that this answer is somewhat hedonistic (focused
on pleasure) and selfish.  It doesn't say much about what we might think
of as our responsibility to others, about how we might try to do good in the world
or to make a difference.  But it's one sort of answer, or maybe one part of an 
answer.

\item[] Finally, as I have been hinting above, it is very plausible to read Cavafy's poem
as saying that the \emph{ultimate destination}, the metaphorical {\it Ithaka}, is 
actually {\it death} and that that's why savoring the journey (life itself) is so important for
human beings.  But there are other possibilities too -- one could also read Cavafy's
{\it Ithaka} as being any one of the big destinations we might set up for ourselves in
our lives -- graduating from college, marriage, children, retirement at the end
of a career, etc.  As is true for all really good poetry, there are multiple layers and
meanings here.    
\end{enumerate}

\end{document}
