%  Project
%  21-110: Problem Solving in Recreational Mathematics, spring 2010
%  Assigned: Wednesday, March 17, 2010. Due: Friday, April 30, 2010.
%  Brian Kell <bkell@cmu.edu>

\pdfpagewidth=8.5truein \pdfpageheight=11truein
\hsize=5.7truein \vsize=8truein
\pdfhorigin=1.6truein \pdfvorigin=1.5truein

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

\headline={\hfil}
\footline={\hfil Page~\folio\hfil}

\def\hs{\nobreak\hskip 0pt plus 1pt minus 1pt\relax}

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

\centerline{\titlefont 21-110: Problem Solving in Recreational Mathematics}
\smallskip
\centerline{\bf Project}
\smallskip
\centerline{Assigned Wednesday, March~17, 2010. Due Friday, April~30, 2010.}

\bigskip

\noindent This assignment is a group project. You will work in a group of up to
four people (i.e., the maximum group size is four). The project is due on
Friday, April~30, 2010.

Your assignment is to address one of the projects outlined here, and write up
your report in a paper. All group members should sign the final report (one
report for the whole group). When you sign, you are certifying that you made a
fair and honest contribution to the group and that you understand what has been
written. I expect to be told of anyone trying to get a free ride. All group
members will receive the same grade.

You do not necessarily need to address every one of the questions in the
project you choose. Conversely, you are welcome to consider additional
questions besides the ones listed here. The most important thing is to think
critically, creatively, and mathematically about the topic of the project, and
to cover it in sufficient depth and detail. Have fun with it!

A paper of sufficient length will probably be 8 to~10 pages long (not counting
pictures, diagrams, tables, etc.), though longer papers are certainly fine.

Note that correct grammar, spelling, readability, and mathematical content all
count. Any graphs, diagrams, or other illustrations should be neat, accurate,
and appropriately labeled. Start with an introductory paragraph, organize your
report in a sensible way, walk your reader through what you are doing, and end
with a conclusion. You should not simply number your answers 1,~2, 3,~\dots;
you are writing a report, so the exposition of your ideas should flow smoothly
from the beginning to the end. Use transition sentences where appropriate. Your
paper should make sense to someone seeing it for the first time, without
reference to the project handout.

Part of the point of a group project like this is to work together as a team.
This includes dealing with the logistical problems of finding time in your
schedules, determining the division of labor, and dealing with personality
differences. I hope you can resolve any problems yourselves, but if you have
problems that you cannot resolve, please see me. Also, if you have a member who
is not contributing, the group has a right to ask that person to leave the
group. However, please keep me informed of any changes in your group
membership.

I'll be happy to meet with your group to discuss things, subject to the
following conditions:

\smallskip

\item{(a)} All of your group members must be present at the meeting, and

\item{(b)} You must come to the meeting prepared (this means, for example, that
you should spend time thinking about things before coming to talk to me).

\smallskip

\noindent Be prepared to explain your ideas and to ask specific questions. I'll
also be happy to meet with your group to review a draft of your report and make
comments and suggestions.

Remember the quality expectations for submitted work in the syllabus. These are
especially important for the project.

\smallskip

\item{$\bullet$} {\bf Be academically honest.} Never put your name on work that
is not yours or work you do not understand, and always give credit where credit
is due. Remember: Taking someone else's work or ideas and presenting them as
your own is plagiarism, even if you change the wording. Provide a list of
sources other than the textbook (if any) that you used to do the assignment,
and state clearly that you are copying or mimicking an example from the book
(if appropriate). If you worked with other students in the class to solve a
problem, be sure to write your results {\it in your own words}, and include a
list of your collaborators. Do~not ever copy text directly from another source,
even with attribution, unless it is a short quote properly marked as such.

\item{$\bullet$} Put your names (first and last) on the top of every page you
turn in. Do not include your student~ID numbers or your Social Security
numbers. On the first page, include a short description of the project (a few
words as a title would be fine---just so I know what it is I'm looking at).

\item{$\bullet$} Type your project (except perhaps for figures).

\item{$\bullet$} Double-space your paper, and leave wide margins (1.5~inches
all around is nice), so that I have enough blank space on each page to write
comments.

\item{$\bullet$} Use a standard font, and print text in black.

\item{$\bullet$} Use good quality paper, print on only one side, and staple or
bind the pages together.

\item{$\bullet$} Include page numbers, in case the pages are accidentally bound
in the wrong order.

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

\noindent{\bf Project~1: Unsolved problems in number theory}

\nobreak\medskip

\noindent There are many problems in number theory that are easy to understand
but remain unsolved. We mentioned some of these unsolved problems in class:
whether there is an odd perfect number, whether there are infinitely many
Mersenne primes, and whether there are any more Fermat primes other than the
ones Fermat knew. Other unsolved problems include:

\nobreak\smallskip

\item{$\bullet$} Goldbach's conjecture;

\item{$\bullet$} the twin primes conjecture;

\item{$\bullet$} Gilbreath's conjecture;

\item{$\bullet$} the Collatz conjecture (this goes by many names, including
``the hailstone conjecture,'' ``the Ulam conjecture,'' and ``the $3n+1$
conjecture'');

\item{$\bullet$} finding the smallest Sierpinski number;

\item{$\bullet$} whether there are infinitely many palindromic primes; and

\item{$\bullet$} the Riemann hypothesis (this is perhaps the most important
unsolved problem in all of mathematics, but it is more difficult to understand
than the previous problems).

\nobreak\smallskip

\noindent Research some of these unsolved problems. You may consider the
following:

\medskip

\item{1.} Explain the problem. Give some illustrative examples. If the problem
is a conjecture, does it seem plausible? Why?

\medskip

\item{2.} Describe the history of the problem. Who first posed the problem,
and when? What developments or breakthroughs have been made since then? Have
simpler forms of the problem been solved?

\medskip

\item{3.} Does the problem have connections to other areas of mathematics? What
possible implications would a solution have?

\medskip

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

\noindent{\bf Project~2: Music and math}

\nobreak\medskip

\noindent Research some of the relationships between music and mathematics.
Summarize your findings, and explain them on a level that your classmates would
understand. Here are some suggestions:

\nobreak\medskip

\item{1.} Explain the ideas of frequency and pitch. How are they related? How
does the concept of an octave relate to frequency? What is a semitone (half
step), in terms of frequency? Give some examples.

\medskip

\item{2.} Explain the concept of a musical scale. Explain what diatonic and
chromatic scales are.

\medskip

\item{3.} Explain tuning systems, and the differences between Pythagorean
tuning, just intonation, and equal temperament.

\medskip

\item{4.} Explain intervals, chords, and key signatures. How do these compare
in various tuning systems? What makes a chord sound harmonious or dissonant?
Why are musical works written in different keys?

\medskip

\item{5.} Describe the concept of time signatures. In what ways are time
signatures similar to fractions? In what ways are they different?

\medskip

\item{6.} Research ways in which mathematical tools or ideas have been used in
the composition of music, or ways in which computer programs have been written
to automatically generate music. (Some composers who have experimented with
such ideas include Raymond Scott, Iannis Xenakis, Lejaren Hiller, and David
Cope; you might also try looking for information on {\it stochastic music},
{\it computer music}, and {\it algorithmic composition}.)

\medskip

\item{7.} Explain how music is recorded on a compact disc and then played again
by a CD player.

\medskip

\item{8.} Find other connections between mathematics and music. Report on your
findings.

\medskip

\item{9.} Include diagrams or musical excerpts to help illustrate the concepts
that you are explaining.

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

\noindent{\bf Project~3: Data compression}

\nobreak\medskip

\noindent In this project, you will research some of the ideas behind data
compression, which is used to shrink the size of computer files. Data
compression is used in ZIP~files, MP3s, JPEG~images, DVDs, and streaming video
(such as YouTube), for example.

\medskip

\item{1.} Give an overview of what data compression is and summarize some of
its history. Describe examples of its applications (and why it is important in
these applications).

\medskip

\item{2.} Is it possible to have a process for data compression that will
always reduce the size of a file? Why or why not?

\medskip

\item{3.} Explain the difference between {\it lossless compression\/} and
{\it lossy compression}. Give examples of situations in which one of these is
better than the other, and explain why.

\medskip

\item{4.} Research the data compression scheme called {\it run-length
encoding}. Describe how it works, and explain why run-length encoding is able
to reduce the number of characters needed to encode a message.

\medskip

\item{5.} Work through an example of using run-length encoding to encode a
message. Work through an example of decoding a different message that has been
encoded with run-length encoding. Explain what you are doing, and why.

\medskip

\item{6.} Research the data compression scheme called {\it Huffman coding}.
Describe how it works, and explain why Huffman coding is able to reduce the
number of bits needed to encode a message. (If you need help understanding
Huffman coding, please come talk to me.)

\medskip

\item{7.} Work through an example of using Huffman coding to encode a message.
Work through an example of decoding a different message that has been encoded
with Huffman coding. Explain what you are doing, and why.

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

\noindent{\bf Project~4: Literature and math}

\nobreak\medskip

\noindent Investigate some of the relationships between literature and
mathematics. Here are some suggestions:

\medskip

\item{1.} Describe some of the mathematical features in the structure of
poetry. What kinds of mathematical patterns appear in the meter, rhyme schemes,
and stanza forms of poetry? Are there poets that have made specific attempts to
incorporate mathematical concepts into their poetic structure?

\medskip

\item{2.} Research the idea of constrained writing. Give some examples. Explain
the patterns that are used (or avoided) in these examples.

\medskip

\item{3.} Research the concepts of {\it stylometry\/} and {\it authorship
analysis}. What are these used for? What are some of the techniques used? Give
some concrete examples.

\medskip

\item{4.} Research the idea of Markov chains and their application to the
automatic generation of text by computers. Explain the main ideas behind Markov
chains in a way your classmates could understand. Find a Markov-chain text
generator online, generate some text, and explain what is happening. Does the
generated text make sense? Why or why not? (If you need help understanding
Markov chains, please come talk to me.)

\medskip

\item{5.} Read a short story based upon a mathematical theme and comment on it.
Explain the mathematics in the story and how it is used in the plot. (Three
good collections of mathematically-oriented short stories are {\it Fantasia
Mathematica}, by Clifton Fadiman, and its sequel {\it The Mathematical Magpie};
and {\it Imaginary Numbers}, by William Frucht. I have copies of these books if
you would like to borrow them.)

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

\noindent{\bf Project~5: Geometry and topology}

\nobreak\medskip

\noindent In class we discussed symmetry and tilings from a two-dimensional
point of view. We also investigated polyominoes, which are two-dimensional
objects. In this project, you will investigate such concepts as
three-dimensional shapes, geometry in four or more dimensions, non-Euclidean
geometry, strange surfaces, and the shapes of knots. Here are some suggestions:

\medskip

\item{1.} Research polyhedra, which are the three-dimensional equivalents of
polygons. Explain what Platonic solids, Archimedean solids, and Kepler--Poinsot
solids are. How many of each of these types are there? Explain what Euler's
formula says, and give some examples. (There are several different formulas
called ``Euler's formula,'' because Euler was a prolific mathematician, but
there is a particular one that has to do with polyhedra.)

\medskip

\item{2.} Read {\it Flatland}, by Edwin~A. Abbott. Alternatively, or in
addition, read ``---And He Built a Crooked House---,'' by Robert~A. Heinlein,
which can be found in the anthology {\it Fantasia Mathematica}, by Clifton
Fadiman. (I have a copy of {\it Fantasia Mathematica\/} if you would like to
borrow it.) These works explore the idea of a geometrical fourth dimension.
Explain what fourth-dimensional geometry is like. What is the equivalent of a
cube in four-dimensional space? In what ways is four-dimensional geometry
different from two- or three-dimensional geometry, and in what ways are they
similar? Is there any way to visualize four-dimensional space?

\medskip

\item{3.} The ancient Greek mathematician Euclid wrote the most famous
mathematics textbook of all time, called the {\it Elements}, around
300~{\smfont B.C\null.} He based all of his geometrical theorems on five basic
assumptions, called postulates. Find out what Euclid's fifth postulate says.
Describe the long history of mathematicians trying (and failing) to prove the
fifth postulate from the other four. In the 19th century, the mathematicians
J\'anos Bolyai, Nikolai Ivanovich Lobachevsky, and Carl Friedrich Gauss
independently discovered the ideas of {\it non-Euclidean geometry}. Explain the
relationship between non-Euclidean geometry and Euclid's fifth postulate.
Compare non-Euclidean geometry to traditional Euclidean geometry---what things
are true in one that are not true in the other? Does non-Euclidean geometry
have any practical applications?

\medskip

\item{4.} Investigate the area of mathematics called {\it topology}. Explain
the mathematical joke that says a topologist is a person who cannot tell the
difference between a donut and a coffee cup. How is a torus topologically
different from a sphere? Research the M\"obius strip and the Klein bottle, and
explain the strange properties these shapes have.

\medskip

\item{5.} Explore {\it knot theory}, the mathematical study of knots. What is
the ``unknot''? What is the trefoil knot? When are two knots considered to be
the same? How can it be recognized when one knot is the same as another?
Explain knot diagrams and Reidemeister moves. What is a knot invariant, and how
are knot invariants useful in telling two different knots apart? What practical
applications does knot theory have?

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

\noindent{\bf Project~6: ???}

\nobreak\medskip

\noindent You are welcome to propose a different project for your group to
tackle. Come talk to me about it before you begin serious research. In your
project proposal, explain the topic you want to research, the questions you
will attempt to answer, and some of the ways in which your project relates to
ideas we have discussed in class. (Your project proposal does not have to be a
written document, but spend some time thinking about these things before coming
to talk to me. If you have an idea for a general topic but are having
difficulty finding ways in which it relates to mathematics, feel free to ask me
about it.)

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

\bye
