\documentclass{article}

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

\usepackage{geometry}
\geometry{%
  letterpaper,
  lmargin=2cm,
  rmargin=2cm,
  tmargin=2cm,
  bmargin=2cm,
  footskip=12pt,
  headheight=12pt}
  
\usepackage{parskip}

\begin{document}

\section*{Mathcamp 2011 Qualifying Quiz}

\subsection*{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} {\nolinkurl{www.mathcamp.org/proofs}}.)  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 require 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}{\nolinkurl{www.mathcamp.org/computers}}.

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:quiz11@mathcamp.org}{\nolinkurl{quiz11@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 use 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  %PROBLEM 1
A betting company offers the possibility to bet on any of the $n$ contestants in a race, with odds $a_1,\ldots,a_n$, respectively.  This means that if you bet $X$ dollars on contestant $j$ (where $X$ is any positive real number), then:
\begin{itemize}
\item If contestant $j$ loses, you lose your $X$ dollars.
\item If contestant $j$ wins, you get your $X$ dollars back, together with a profit of $a_j X$ dollars.
\end{itemize}

If the company does not choose the odds wisely, it may be possible to bet on all of the contestants in a manner that guarantees a profit no matter what. For instance, if there are 3 contestants with odds 2, 2, and 10, you could bet \$1 on each of the first two and \$0.50 on the the third one, guaranteeing a profit no matter who wins the race.

\begin{enumerate}
\item What relation must the real numbers $a_1,\ldots,a_n$ satisfy so that it is impossible to guarantee a profit in this way? 
\item What is the largest profit that you can guarantee on a total bet of \$1 if the relation is NOT satisfied?
\end{enumerate}

\item  %PROBLEM 2
The function $f$ is defined on the positive integers by the formulas
\begin{eqnarray*}
f(1) &=& 1, \\
f(2n) &=& 2f(n)+2n, \\
nf(2n+1) &=& (2n+1)f(n)
\end{eqnarray*}
for all $n\geq 1$.

\begin{enumerate}
\item Prove that $f(n)$ is always an integer.
\item For what values of $n$ does the equality $f(n) = n$ hold? (Be sure to prove that no other value works.)
\end{enumerate}

\item  %PROBLEM 3
(Proposed by Michael Wu, a student at Mathcamp 2009 \& 2010.)  
There are $n$ children equally spaced around a merry-go-round with $n$ seats, waiting to get on.  The children climb onto the merry-go-round one by one (but not necessarily going in order around the circle), always using the seat in front of them and only taking a seat if it is empty.  After one child climbs on and takes a seat, the merry-go-round rotates $360/n$ degrees counterclockwise so that each remaining child is again lined up with a seat.  For what values of $n$ is it possible for the children to climb on, in some order, so that everyone gets a seat?  (Do remember to prove both that it's possible for the values you claim and that it's impossible for all other values.)

\item  %PROBLEM 4
A country has $n$ airports served by $k$ airlines. Not every pair of airports is connected by a direct flight, but if you don't mind stopovers, you can get from any airport to any other.  Also, if a direct flight between a pair of cities exists, you can travel on it in either direction.

\begin{enumerate}
\item To connect $n$ airports, you need to have at least $n-1$ direct flights. (You may assume this without proof.) Unfortunately, airlines in this country often go bankrupt. The airlines are required to coordinate their routes so that if any one of the airlines goes bankrupt, a traveler can still get from any airport to any other.  What is the smallest number of direct flights that could be offered by all the airlines together? (Note: whenever you are asked to find the smallest number with a certain property, you need to prove both that your number has the required property and that no smaller number works.)

\item Suppose $n=7$, $k=5$, and you want to be able to get from any airport to any other even if any {\it two} airlines go bankrupt.  What is the smallest number of direct flights needed in this scenario?

\end{enumerate}

\item  %PROBLEM 5
Bianca and Yuval are playing a game. Yuval thinks of an integer greater than or equal to 1000, but does not reveal it to Bianca. Then Bianca names an integer greater than 1. If Yuval's number is divisible by Bianca's, Bianca wins. Otherwise, Yuval subtracts Bianca's number from his own; the resulting difference is his new number. The game continues, with Bianca naming a different integer each time (no repeats allowed!) and Yuval subtracting each integer she names, until either Yuval's number is divisible by Bianca's (in which case Bianca wins) or Yuval's number becomes negative (in which case Yuval wins).

\begin{enumerate}
\item Obviously, Yuval does not have a winning strategy in this game. (Whatever number he picks, Bianca might get lucky.) Does Bianca have one?

\item Suppose we replace the number 1000 in the problem by a different positive integer $N$.  For which values of $N$, if any, does Bianca have a winning strategy?
\end{enumerate}

\item  %PROBLEM 6
Three numbers are arranged around a circle; at time $t=0$, the numbers are 0, 1, 2, reading counterclockwise.  Thereafter, the numbers are adjusted each unit of time, as follows:  If the two neighbors of a number $m$ are {\it equal}, then that number $m$ will stay the same for the next unit of time.  If the counterclockwise neighbor of a number $m$ is {\it less} than its clockwise neighbor, then the number $m$ will be raised by 1.  If the counterclockwise neighbor of a number $m$ is {\it greater} than its clockwise neighbor, then the number $m$ will be reduced by 1.  The first few steps of this process yield the following:

\[
\setlength{\arraycolsep}{0.3cm}
\begin{array}{ll}
\hline\hline
t=0           & 0, 1, 2  \\
\hline
t=1           & 1, 0, 3  \\
\hline
t=2           &  2, -1, 2 \\
\hline
t=3           & 3, -1, 1 \\
\hline
t=4           & 4, 0, 0  \\
\hline
t=5           & 4, 1, -1 \\
\hline\hline
\end{array}
\]

Including $t=0$, what is the 2011th time that at least one of the three numbers is zero?

\item  %PROBLEM 7
(Proposed by Josh Frisch, a student at Mathcamp 2010.)  Consider the interval  $(0,1]$, which is the set of real numbers $x$ with $0 < x \le 1$. A subset $S$ of the interval $(0,1]$ is called \emph{evil} if, for each positive integer $n$: 

\begin{itemize}
\item Its reciprocal $1/n$ is in $S$.
\item If $x$ is in $S$ then so is the average of $x$ and $1/n$.
\end{itemize}

Must an evil set contain every rational number in the interval $(0,1]$?

\item  %PROBLEM 8
There are $N$ cyclists riding counterclockwise around a circular track, each one at a different constant speed. The track is very narrow: there is only one point on it where passing is possible (but at this point, the track is wide enough that any number of bicycles can pass there simultaneously). Somehow the cyclists have arranged it so that they can keep going as long as they want, always passing each other at exactly this point. 

\begin{enumerate}
\item (Warm-up) For $N=2$, what condition must the speeds of the two cyclists satisfy?
\item For what values of $N$ is this situation possible?
\end{enumerate}

%%%%%

\end{enumerate}

\vspace{10mm}

Problem 6 copyright Mark Krusemeyer. 

\end{document}



