\documentclass[11pt]{article}


\usepackage[varg]{txfonts}
\usepackage{hyperref}
\urlstyle{tt}

\usepackage{geometry}
\geometry{%
  letterpaper,
  lmargin=3cm,
  rmargin=3cm,
  tmargin=3cm,
  bmargin=3.5cm,
  footskip=36pt,
  headheight=36pt}

\begin{document}

\section*{Mathcamp 2009 Qualifying Quiz}

\textbf{Instructions.} We call it a quiz, but it's really a challenge:
a chance for you to show us how you approach new problems and new
concepts in mathematics. What matters to us are not only your final
results, but your reasoning. Correct answers on their own will count
for very little: you have to justify all your assertions and
\emph{prove} to us that your solution is correct. (For some tips on
writing proofs, see 
\href{http://www.mathcamp.org/proofs.php}{\nolinkurl{www.mathcamp.org/proofs.php}}.)  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.

The problems start out easier and get harder. (At least we think so ---
but you may disagree.) None of the problems requires a computer; you
are welcome to use one if you'd like, but first read a word of warning
at \href{http://www.mathcamp.org/computers.php}{\nolinkurl{www.mathcamp.org/computers.php}}.

We don't expect every applicant to solve every problem: in the past,
we have sometimes admitted people who could do only half of them,
occasionally even fewer. However, don't just solve four or five
problems and declare yourself done! The more problems you attempt, the
better your chances. We strongly recommend that you try all the
problems and send us the results of your efforts: partial solutions,
conjectures, methods --- everything counts.

If you need clarification on a problem, please email
\href{mailto:quiz09@mathcamp.org}{\nolinkurl{quiz09@mathcamp.org}}. 
\emph{You may not consult or get help from
  anyone else.} You can use books or the Web to look up definitions,
formulas, or standard techniques, but any information obtained in this
way must be clearly referenced in your solution. Please do not try to
look for the problems themselves: we want to see how well you can do
math, not how well you can Google! Any deviation from these rules will
be considered plagiarism and may disqualify you from attending
Mathcamp.

\textbf{Good luck and have fun!}


\subsection*{The problems:}

\begin{enumerate}
\item %%Long Walk -- Problem 1
A group of Mathcampers went on a 3.5-hour hike on Mt.~Rainier. In any
consecutive one-hour period during their hike, they covered exactly 2
miles. Does it follow that they hiked exactly 7 miles total? If not,
what are the minimum and maximum distances they could have walked?
\emph{Prove your answer.}

\item %%Colored integers -- Problem 2
\begin{enumerate}
\item
You wish to color each of the integers 0,~1, 2, \dots,~$n$ red or blue, in
such a way that
\begin{itemize}
\item
both colors are used, and
\item
integers that differ by 7 or 11 have the same color.
\end{itemize}
Can you do this for all $n$? If not, what is the largest value of $n$ for
which it is possible? \emph{Prove your answer.}
\item
How does the answer in (a) change if we replace the numbers 7 and 11 with
arbitrary integers $m$ and~$k$? If you can't figure out the solution
for the most general case, try it for some special cases --- e.g., for
a fixed value of $k$ or for some specific relationship between $m$ and
$k$. Include your most interesting/general proofs in your solution.
\end{enumerate}

\item %% Autonomous sets -- Problem 3
Let $S$ be a set of numbers. We'll call $S$ \emph{autonomous} if the
number of elements in $S$ is itself an element of $S$. For example, the set
$\{2,5\}$ is autonomous, as is the set $\{2,3,7\}$, but the set
$\{3,4\}$ is not. Find, with proof, the number of
autonomous subsets of $\{1,2,3,\ldots,n\}$.

\item  %%Add divisor -- Problem 4
Suppose you start with the number 1 and go through a series of steps,
where at each step you add a (positive integer) divisor of your
current number to the number itself, to get a new number. For
instance, the first step is forced: you have to take $1+1$, so your
new number is 2. Now you have two choices; the next number could be
$2+1=3$ or $2+2=4$. If you choose 4, the next step after that can take
you to 5, 6, or 8.
\begin{enumerate}
\item
Show that if $N \leq 2^{n+1}$, then you can always reach $N$ using $2n$
steps or fewer.
\item
Show that if $N > 2^n$ and you can reach $N$ in $n+1$ steps, then $N$ is a
sum of two powers of two.
\end{enumerate}


\item  %%Random triangle -- Problem 5
Three real numbers are chosen at random between 0 and 1.  What is
the probability that they form the side lengths of a triangle?  \emph{Prove your answer.}

\item  %% Subtract one or halve game -- Problem 6
Nathan and Abi are playing a game. Abi always goes first. The players
take turns changing a positive integer to a smaller one and then
passing the smaller number back to their opponent. On each move, a
player may either subtract one from the integer or halve it, rounding
down if necessary.  Thus, from 28 the legal moves are to 27 or to 14;
from 27, the legal moves are to 26 or to 13. The game ends when the
integer reaches 0. The player who makes the last move wins. For
example, if the starting integer is 15, Abi might move to 7, Nathan to
6, Abi to 3, Nathan to 2, Abi to 1, and now Nathan moves to 0 and
wins. (However, in this sample game Abi could have played better!)
\begin{enumerate}
\item
Assuming both Nathan and Abi play according to the best possible
strategy, who will win if the starting integer is~1000? 2000?  \emph{Prove your answer.}
\item
As you might expect, for some starting integers Abi will win and for
others Nathan will win. If we pick a starting integer at random from
all the integers from 1 to $n$ inclusive, we can consider the
probability of Nathan winning. This probability will fluctuate as $n$
increases, but what is its limit as $n$ tends to infinity?  \emph{Prove your answer.}
\end{enumerate}

\item %%Oscillating products -- Problem 7
Consider the sequence of positive real numbers
\[
 4,\; 1/3,\; 4/3,\; 4/9,\; 16/27,\; 64/243,\;\ldots,
\]
in which each term (after the first two) is the product of the two previous
terms. Note that for this particular sequence, the first and third terms are
greater than one while the second and fourth terms are less than one.
However, after that the ``alternating" pattern fails: the fifth and all
subsequent terms are less than one. Do there exist sequences of positive
real numbers in which each term is the product of the two previous ones and
for which \emph{all} odd-numbered terms are greater than one, while all even
numbered terms are less than one? If so, find, with proof, all such sequences.  If not,
prove that no such sequences exist.


\item  %%Line segments -- Problem 8
On the $x,y$ coordinate plane, there is a finite set of line segments.
Each line segment lies completely in the square bounded by $(0,0)$,
$(0,1)$, $(1,0)$, and $(1,1)$, and the sum of the lengths of all the line
segments is 18.  Prove that there exists a straight line in the plane
that crosses at least 10 of the segments.
\end{enumerate}


Problems 6 and 7 copyright Mark Krusemeyer.


\end{document}
