\documentstyle[11pt]{article}
\pagestyle{empty}

\textwidth=7.0in
\oddsidemargin=-0.2in
\textheight=9.5in
\topmargin=-0.5in

\newcounter{question}

\begin{document}
\begin{center} {\large \bf Mathcamp '99 Application Quiz} \end{center}

\begin{center}
{\bf Instructions}
\end{center}

There are a lot of problems here--something for everyone, we hope. You
should try as many of the questions in Sections A and B as you can, and
perhaps an optional project from the Projects following Section B below. 
We certainly don't expect every applicant to solve every problem, though
we do recommend that applicants submit solutions to at least five
problems.

Please begin each of your solutions on a separate sheet of paper; also,
please write on only one side of each page, and arrange your solutions in
the same order as the questions.  Make sure that your solutions are
legible and well-spaced, and don't forget to write your name on every
sheet of paper you submit. 

On all the sections of the quiz, you are welcome to use outside
resources, such as books or the Web, as long as you acknowledge and
reference them. Of course, all the actual work must be your own. 
Remember that your reasoning matters more to us than your final
answers, so don't hesitate to submit partial solutions.

Good luck, and have fun!

\begin{center}
{\bf Section A}
\end{center}

\begin{enumerate}

\item
Show that there are no positive integers $m$ and $n$ such that
$m(m+1)=n(n+2)$.

\item
Find the smallest positive integer $n$ such that ${n\over 2}$ is the
square of an integer, ${n\over 3}$ is the cube of an integer, ${n\over
5}$ is the fifth power of an integer, and ${n\over 7}$ is the seventh
power of an integer.

\item
A triangle has sides of length $a$, $b$ and $c$, which satisfy the
equation $1/(a+b) + 1/(a+c) = 3/(a+b+c)$. Determine the angle opposite
the side of length $a$.

\item
If $S_n$ denotes the sum of the decimal digits of the number $2^n$,
either show that $S_n \neq S_{n+1}$ for all positive integers $n$, or
find a counterexample.

\item
I want to make a square lawn in the middle of a desert. For
irrigation, I'll use two sprinklers, each of which can reach a
circular area of radius 5 yards. The water from the sprinklers must
cover the entire lawn.  How large can my lawn be?

\item
{\em (Extra Credit)} A polynomial $P(x)$ is said to be \emph{boring}
if it takes rational values for rational $x$ and irrational values for
irrational $x$.  Prove that all boring polynomials are linear.


\setcounter{question}{\value{enumi}}
\end{enumerate}

\begin{center}
{\bf Section B}
\end{center}

\begin{enumerate}
\setcounter{enumi}{\value{question}}

\item
Five mathematically gifted pirates, named Angry, Boorish, Crummy,
Dirty, and Evil, must divide a loot of 100 gold doubloons.  According
to pirate law, Angry, the leader, can distribute the coins as she sees
fit.  However, when she is done, all five pirates (including Angry
herself) take a vote: if more than half of them are unhappy with the
distribution, Angry has to walk the plank (leaving her share of gold
behind). The remaining four pirates, with Boorish as their new
leader, then repeat the process: Boorish divides the loot, they all
vote, and if more than half are unhappy then Boorish is done away with
and Crummy takes charge of the gang. This process continues until the
treasure is successfully distributed.

\begin{enumerate}

\item
How should Angry divide the money to ensure herself as large a share
of the loot as possible?  (You may assume that every pirate completely
understands the strategy behind this process, and will always vote in
such a way as to maximize his or her share.  Furthermore, each pirate
is bloodthirsty, and will vote to kill the current leader if it won't
decrease his or her ultimate share of the loot.)

\item
What happens when there are more than five pirates?

\end{enumerate}

\item
Three bugs are crawling on the coordinate plane. They move one at a
time, and each bug crawls in a direction parallel to the line
joining the other two.

\begin{enumerate}
\item 
If the bugs start out at (0,0), (3,0), and (0,3), is it possible that
after some time the first bug will end up back where it started, while the
other two switch places?

\item
Can the three bugs end up at (1,2), (2,5), and (-2,3)?
\end{enumerate}


\item
You are a secret agent assigned to carry out classified research on
the $C_n$-tower, an ultra-modern office block $n$ stories tall. Your
mission: to determine the highest floor of the building from which a
dropped egg will survive falling to the ground.  Your equipment: a
supply of exactly $k$ eggs.

\begin{enumerate}

\item
Suppose $k=1$: you have only one egg (and once it smashes, that's
it). How can you determine the highest floor that is safe? Are there
any other strategies?

\item
Suppose $k=2$. You need to complete your mission as quickly as
possible.  What strategy should you use to determine the safe height
efficiently?  (Here ``efficiently'' means that the {\em worst case
scenario} takes as few test drops as possible.)

\item
Can you find an answer for higher values of $k$?

\end{enumerate}

\item
It is a well-known fact that the number $\sqrt{5}$ is not rational
(i.e. cannot be written as a fraction $p/q$ for integers $p$ and $q$). 

\begin{enumerate}
\item
$\sqrt{5}$ does crop up very naturally in geometry. Draw a picture to 
illustrate this.

\item
We could try to write $\sqrt{5}$ as a ``continued fraction'':
$$
\sqrt 5 = 2 +
\frac{1}{4 +
\frac{1}{4 +
\frac{1}{4 + \raisebox{-.6ex}{\ldots} }}}
$$
What might we mean by this?

\item
Alternatively, we can look for rational numbers that are {\em
approximately} equal to $\sqrt{5}$.  Let $r_0$ be a positive rational
number close to $\sqrt{5}$.  Show that $r_1 = {2r_0+5\over r_0+2}$ is
even closer to $\sqrt{5}$.

\item
Suppose we let $r_0=2$, and repeat the procedure of (c) by setting
$r_{n+1} = {2r_n+5\over r_n+2}$.  Can you see a connection between the
sequence of numbers $r_n$ and the continued fraction in part~(b)? Can
you prove it?
\end{enumerate}


\item A polygon with $n$ sides is called an $n$-gon. Here $n$ is
assumed to be a positive integer, but we can also define {\em
fractional polygons}, or $\frac n k${\em-gons}. To draw a regular
$\frac n k$-gon, start with any vertex of a regular $n$-gon, and label
it 1. Count off $k$ vertices clockwise, and label the vertex you end
on 2. Count off $k$ more vertices and label that vertex 3. Continue in
this way until you get back to 1. Now draw an edge from 1 to 2, from 2
to 3, etc., and from the last vertex back to 1. (Notice that in
fractional polygons, edges are allowed to intersect.)  For example, a
$\frac 5 2$-gon is a five-pointed star; we still think of it as having
5 vertices and 5 edges.

\begin{enumerate} 

\item
Experiment with different values of $n$ and $k$. How many vertices
does an $\frac n k$-gon have? When do different values of $n$ and $k$
produce the same polygon?

\item
How many different regular $\frac n k$-gons with $n$ vertices are
there? (Try it first for $n$ = prime.)
\end {enumerate}

\end{enumerate}

\pagebreak

\begin{center}
{\bf Projects}
\end{center}

\begin{enumerate}
\setcounter{enumi}{\value{question}}


\item[P1]
Polyominoes (also called $n$-ominoes) are made by sticking $n$ square
tiles together by their edges, in flat configurations.  For example,
the blocks in the game Tetris form a complete set of $4$-ominoes. We
will consider mirror images to be the same, so there are exactly five
(different) $4$-ominoes.

\begin{enumerate}
\item
There are exactly two $3$-ominoes.  The T-shaped $4$-omino can be
placed on each of them, covering them completely.  Can you find a
$6$-omino that covers all the $4$-ominoes? Show that there is no
$5$-omino that can cover all the $4$-ominoes. 
\item
How many $5$-ominoes are there? Find a $k$-omino that can cover all
the $5$-ominoes. How small can $k$ be?
\item
Is it true that for all values of $n$, there is a $2n$-omino that
covers all $n$-ominoes?
\item
Let $f(n)$ be the size of the smallest polyomino that can cover all
$n$-ominoes. What can you say about $f(n)$?  For example, what are the
best upper and lower bounds for $f(n)$ that you can give?  [You are
NOT expected to look for an exact general formula.]
\end{enumerate}

\item[P2]
If you have Internet access, take a look at the website ``Clever Games
for Clever People'', at:
\begin{center}
\verb#http://www.cs.uidaho.edu/~casey931/conway/games.html#
\end{center}
See if you can find a winning strategy (or partial strategy) for one
or more of the games described there, and tell us about it.


\item[P3]
This problem is about even and odd numbers in Pascal's triangle and,
believe it or not, fractals!
\begin{enumerate}
\item
On a piece of graph paper, write down the first 5 or 6 rows of
Pascal's triangle, putting one number in each square. (You may want to
orient the paper diagonally.) Now color each square that contains an
even number black, and each square that contains an odd number
red. Extend this coloring to 10 or 15 more rows of the triangle. (Do
you have to compute the actual numbers to do this?) Describe the
pattern that you see, and try to predict how it continues.

\item
Assuming your pattern is correct, what fraction of the numbers in
Pascal's triangle are even? (Before you even try to answer this
question, think about what it could possibly mean. After all, the
triangle is infinite!)

\item
As you probably know, the $k^{th}$ entry in the $n^{th}$ row of
Pascal's triangle (if we start the numbering from 0) is the binomial
coefficient $n \choose k$. (Can you prove this?) Write $n$ and $k$ in
binary, and see if this helps you predict whether $n \choose k$ will
be even or odd. Is this the same pattern that you found before? Can
you prove it this time?

\item
In fact, there is a general formula for the divisibility of binomial
coefficients by prime numbers. It's tricky, but give it a try: draw
pictures, try different bases, formulate conjectures, and see if you
can prove them.

\end{enumerate}
\end{enumerate}

\end{document}

