\documentclass[11pt]{article}
\usepackage{epsfig}
\pagestyle{empty}

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

\newcounter{question}

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

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

We call it a quiz, but it's really a challenge: a way for you to show us
how you approach new problems and new topics in mathematics. What matters
to us are not only your final results, but your reasoning. In every
problem, be sure to justify your assertions, explain how you got your
answer, and convince us that your solution is correct!

We certainly don't expect every applicant to solve every problem. In the
past, we have often admitted applicants who could do only five, sometimes
even fewer. However, you should definitely try all the problems, and send
us the results of your efforts: partial solutions, conjectures, methods --
everything counts. Sometimes it may take a while to find the right way of
approaching a problem. Be patient -- there is no time limit on this quiz.

You are welcome to consult books or the Web, as long as you acknowledge 
and provide references for your sources. If you need clarification on a 
problem, you can send email
to {\sf quiz@mathcamp.org}, but you may not consult or get hints from 
anyone
else. 
None of the problems require a computer.
You are welcome to use a computer if you like, but first read
{\sf http://www.mathcamp.org/computers.html} for a word of warning.
 
Good luck, and have fun!

\begin{center}
{\bf Problems}
\end{center}

\begin{enumerate}

\item Every day at Mathcamp, Frank and Lilian competed to see who could
solve more problems in problem-solving class. Each day at least one of
them was able to do more than half the problems. Of the days when Frank
solved more than half the problems, he won twice as often as he lost. Of
the days when Lilian solved more than half the problems, she won five
times as often as she lost. There were $25$ class days total.  On how many
days did Lilian win? (You can assume there were no ties.)

\item Fifteen plates are placed evenly around a circular table, with name
cards for fifteen guests. The guests fail to notice the cards until after
they've sat down, at which point they discover that no one is in the
correct seat. Show that the table can be rotated so that at least two of
the guests are simultaneously correctly seated.

\item An infinite sequence of ``$1$''s and ``$2$''s is determined by the 
following
properties:
\begin{enumerate}
\item[(i)] The sequence is built up by stringing together pieces of the 
form
 ``$12$'' and ``$112$''.
\item[(ii)] If we replace each ``$12$'' piece with a ``$1$'' and each 
``$112$'' 
piece 
with
a ``$2$'' then we get back the same sequence.
\end{enumerate}

\begin{enumerate}
\item Write down the first $30$ digits in the sequence.

\item Without explicitly writing down any more digits, can you predict 
what
the $409$th digit in the sequence will be?
\end{enumerate}

\item  Ten pirates, ranging in rank from captain (\#$1$) to cabin boy 
(\#$10$)
have dug up a chest of gold coins. They start by splitting the
treasure evenly, but the captain is not satisfied. He orders a vote to
be taken on whether the cabin boy should be allowed to keep his part of
the treasure. If more than half the pirates vote ``no'', the cabin boy's
portion will be divided among the rest of the crew. Next, \#$9$'s portion
will be put to a vote in the same way, then \#$8$'s, etc. In each round,
the pirate whose fate is being decided gets a vote, but pirates who have
already been dispossessed do not vote in successive rounds, and do not
get a share of the redistributed treasure. Once one pirate is allowed to
keep his share, the process stops.

\begin{enumerate}
\item Assuming each pirate acts totally rationally according to these
rules, how many pirates will end up with a share of the gold?

\item Suppose there are $100$ pirates to start with. How many will get a
share of the gold?
\end{enumerate}

\item  When Mark climbs a staircase, he ascends either $1$, $2$, or $3$ 
stairsteps
with each step of the foot, but in no particular pattern from one foot to
the next.  How many ways can Mark climb a staircase of $10$ steps?  (Note
that he must finish on the top step.)  Suppose that a spill has occurred
on the $6$th step and Mark wants to avoid it.  How many ways 
can 
he climb
the staircase without stepping on the $6$th step?

\item Three non-overlapping circles are drawn on the ground. Inside one of
the circles are n pebbles, and there are no pebbles in the other two
circles. Your goal is to transfer all of the pebbles from one circle to
another, subject to the following rule: you may move exactly $2^k$ pebbles
from one circle (call it circle A) to another (call it circle B) provided
that circle B begins with fewer than $2^k$ pebbles, and that after the 
move
circle A ends up with fewer than $2^k$ pebbles.  Further, you wish to
complete this task in as few moves as possible.  For what values of $n \le
100$ would the most moves be required?

\item  There are several cities in a certain kingdom. An obnoxious citizen 
is exiled from city A to city B, which is the furthest city in the kingdom
from A. After a while, he is exiled from city B to the furthest city from
it, which happens to be different from A. Prove that, if his exiles
continue in the same way, he will never return to city A.  You may assume
that the distances between cities are all different.

\item A king decides to build a large square plaza in front of his palace. 
He
will position three of his trusted sentries at optimal points on the
plaza, so that, in case of trouble, no point on the plaza is more
than $50$ feet from the nearest sentry. How large can the king make the
plaza, and how should he position the sentries? (Kings are big on grandeur
and mistrustful of mathematicians, so you need to explain carefully why
your proposed arrangement of sentries is optimal. How do you know that
there isn't an alternative arrangement that would enable the king to make
his plaza even larger?)

\item  The \emph{repeat} of a positive integer is the number obtained by
writing the original number twice, so for example, the repeat of $364$ is
$364364$. (All numbers are written in decimal with no leading zeros.)  Is
there a number whose repeat is a perfect square?

\item

\begin{enumerate}  
\item Begin with a string of $10$ A's, B's, and C's.  For 
example:
\begin{verbatim}
   A B C C B A B C B A
\end{verbatim}

Underneath, form a new row, of length one letter shorter, as follows: 
between
two letters that are different, write the third letter, and between
two letters that are the same, write that same letter again.
Continue this process, until you have only one letter in the
new row.  For example:

\begin{verbatim}
   A B C C B A B C B A
    C A C A C C A A C
     B B B B C B A B
      B B B A A C C
       B B C A B C
        B A B C A
         C C A B
          C B C
           A A
            A 
\end{verbatim}

Prove that, no matter what string you start with, the 
letters at the
corners of the resulting triangle are either all the same or all
different.

\item To what other numbers could you change the $10$ in part (a), and 
still
have the assertion be true?
\end{enumerate}

\item[(Bonus)] In problem \#$3$, let $A_n$ denote the number of 
``1''s amongst
the first $n$ characters, and let $B_n$ denote the number of ``2''s 
amongst the
first $n$ characters, so that $A_n + B_n = n$.  What happens to the ratio
$A_n/B_n$ as $n$ grows large?

\end{enumerate}

\end{document}

