\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 2014 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 just your final results, but your reasoning. Correct answers on their own will count for very little: you need to justify all your assertions and {\em prove} to us that your solution is correct. (For some general tips on writing proofs, see {\sf www.mathcamp.org/proofs}.) 

The problems are roughly in increasing order of difficulty, though the later problems often have some easier parts. 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, so we strongly recommend that you try all of them. If you are unable to solve a problem completely, 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.

Most of the quiz problems require only high-school algebra and geometry (no calculus). This year, you also need to know a tiny bit of elementary number theory. If you have never heard of number theory, never fear: all the background you need can be found at {\sf www.mathcamp.org/background}.

None of the quiz problems require a computer; you are welcome to use one if you'd like, but first read a word of warning at {\sf www.mathcamp.org/computers}. If you need clarification on a problem, please email your question to {\sf quiz14@mathcamp.org}. {\em You may not consult or get help from anyone else!} You may use books or the Web to look up mathematical definitions, formulas, or standard techniques; just be sure to cite all these sources in your solution. Please do not try to look up the problems themselves: we want to see how well you can do math, not how well you can use Google. {\bf Any deviation from these rules will be considered plagiarism and may permanently disqualify you from attending Mathcamp.}

\subsection*{The Problems \footnote{Problem \#6 is due to Bill Kuszmaul, MC '12-'13; all other problems were written by the Mathcamp staff.}}

\begin{enumerate}

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

\item Imagine a chessboard that extends infinitely far in all directions. In the center of every square is a grasshopper. 
\begin{enumerate} 
\item  Show that it is possible for all the grasshoppers to jump simultaneously, so that after the jump there are exactly two grasshoppers in the center of every square. (A grasshopper can jump arbitrarily far; it can also jump straight up and land on the same spot it started on.)
\item Now suppose the squares are 1 inch $\times$ 1 inch, and a grasshopper can jump at most 100 inches. Is it still possible to end up with two grasshoppers in the center of every square after one jump? If yes, show how it can be done. If no, prove your answer. (Note: Saying that your strategy from part (a) won't work is not a proof that it can't be done, because there might be a different strategy that does work.) 
\end{enumerate}

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

\item Stephanie is an evil genius; she is building an army of robots and cyborgs. Every day, each of Stephanie's robots builds a copy of itself, while each of her cyborgs builds three new cyborgs and a robot. Once built, the cyborgs and robots never break or die.
\begin{enumerate}
\item If Stephanie wants to double her army each successive day (i.e. to have exactly twice as many robots and twice as many cyborgs as the day before), what ratio of robots and cyborgs should she start with? What if she wants to quadruple her army each day?
\item More generally, if Stephanie starts with $R$ robots and $C$ cyborgs on day 0, what will be the composition of her army after $n$ days? Prove your answer. (One way to approach this problem is to use part (a), but you're welcome to do it any way you like.)
\end{enumerate}

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

\item Let $P_n$ be a regular $n$-sided polygon inscribed in a circle of radius 1. What is the minimum number of circles of radius $1/2$ required to cover $P_n$ completely? (Both $P_n$ and the circles in this problem include the boundary as well as the interior.) Note: in order to prove that something is the minimum, you need to prove both that it works and that nothing smaller works.

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

\item Hannah is about to get into a swimming pool in which every lane already has one swimmer in it. Hannah wants to choose a lane in which she would have to encounter the other swimmer as infrequently as possible. All swimmers, including Hannah, swim back and forth at constant speeds, never pausing at the ends of the pool. Hannah swims at speed 1 (one pool length per minute).
\begin{enumerate}
\item Say Hannah chooses a lane with a swimmer who swims at speed $0 < s < 1$. Prove that, if they keep swimming long enough, eventually Hannah and the other swimmer will settle into a pattern where they pass each other (either in the same or in opposite directions, or at the edge of the pool) exactly $N$ times every $M$ minutes, where $M$ and $N$ are relatively prime integers. Find $M$ and $N$. Do they depend on the other swimmer's speed and/or initial position when Hannah enters the pool?
\item What if Hannah chooses a lane with a swimmer whose speed is $s>1$?
\item From Hannah's point of view, what is the ideal nonzero speed that another swimmer can have? (Assume Hannah can time her entry into the pool with perfect precision, so she can make the other swimmer's initial position be whatever she wants.)
\end{enumerate}

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

\item Let $p$ be a prime. For which integers $n$ is it possible to split the set $\{1,2,\dots,n\}$ into $p$ disjoint subsets such that the sum of the integers in each of the subsets is the same? Prove your answer. 

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

\item A path from the bottom left to the upper right corner of an $m \times n$ grid is called {\em monotonic} if on each step it goes either up (U) or to the right (R). Such a path has $m+n$ steps, of which $m$ are U's and $n$ are R's. Thus the total number of monotonic paths is ${m+n \choose m} = {m+n \choose n}$. If you are not familiar with this kind of argument, you can find more details at

\begin{verse}
{\sf http://www.artofproblemsolving.com/Videos/video.php?video\_id=29}  or \\
{\sf http://mathforum.org/library/drmath/view/70459.html}
\end{verse}

We define the {\em area} of a monotonic path to be the number of squares underneath it. The area can be anywhere between 0 and $mn$. We are interested in areas of monotonic paths modulo a prime $q$. (If you don't have much experience with modular arithmetic, be sure to read our number theory primer at {\sf www.mathcamp.org/background}.)

\begin{enumerate}
\item The {\em forward shift} of a monotonic path $P$ is the path that results when we take the first step of $P$ (either U or R) and move it to the end. For instance, the forward shift of URRURU would be RRURUU. Of course, once we perform $m+n$ forward shifts, we get our original path back. Now suppose $m+n= q$, where $q$ is prime. Let $P_0$ be a monotonic path on an $m\times n$ grid, and let $P_1, P_2, \dots, P_{q-1}$ be successive forward shifts of $P_0$. Show that for each integer $k = 0, 1,\dots , q-1$, exactly one of $P_0, P_1,\dots, P_{q-1}$ has area congruent to $k$ modulo $q$.

\item Consider all monotonic paths on a $q\times q$ grid, where $q$ is prime. For each integer $k = 0, 1,\dots , q-1$, how many of these ${2q \choose q}$ paths have area congruent to $k$ modulo $q$? (Hint: use part (a). It may not seem relevant, but it is.)

\item More generally, consider all monotonic paths on an $mq \times nq$ grid, where $q$ is prime and $m$ and $n$ are arbitrary positive integers. For each integer $k = 0, 1,\dots , q-1$, how many of these paths have area congruent to $k$ modulo $q$?
\end{enumerate}

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

\item A {\em voting system} is a way of combining the disparate preferences of many individual voters to arrive at a single decision for the group as a whole.  When there are two candidates, there is only one reasonable voting system: the candidate who is preferred by the majority of voters wins. But with more than two candidates, things become much trickier. For instance, with three candidates A, B, and C, it is possible that a majority of voters prefers A to B, a majority prefers B to C, and a majority prefers C to A. (See ``Voting Paradox" on Wikipedia.) So how should we decide on the winner? There are no easy answers to this question; in fact, you can even prove that, if voter preferences are allowed to be completely arbitrary, there are no good voting systems at all. (If you'd like to learn more about this, search under ``voting theory" in Wikipedia - or come to Mathcamp and take a class on voting theory.) 

This problem is not about finding good voting systems; it's about how strange and inconsistent voter preferences in a group can be. An individual voter's preferences are given by ``$C_1 > C_2 > \dots > C_n$", which means that candidate $C_1$ is the voter's top choice, candidate $C_2$ is her second choice, etc. We assume that each individual's preferences are {\em transitive}: if a voter prefers $C_1$ to $C_2$ and $C_2$ to $C_3$, then he will prefer $C_1$ to $C_3$. But, as the voting paradox shows, the preferences of the group as a whole might not have this property.
\begin{enumerate}
\item If there are four candidates A, B, C, and D, show that it is possible to have a set of voter preferences such that a majority of voters prefers A to B, a majority prefers B to C, a majority prefers C to D, yet {\em every single voter} prefers D to A. (The simplest way to show such a thing is simply to write down a set of preferences satisfying these conditions.)
\item Suppose there are $n$ candidates $C_1, C_2,\dots, C_n$, and for every pair $C_i, C_j$ (with $i\neq j$), I tell you which one should get a majority in a two-way election. Show that it is always possible to construct a set of voter preferences that satisfy these pairwise conditions.
\item Extra credit: How many voters did you need in your proof in part (b)? Can you find a proof that uses fewer? For a given number $n$ of candidates, what is the smallest number of voters that is guaranteed to work? (Note: We don't know the solution to this problem. We can get the number to be pretty small, but we can't prove that our solution is the smallest. Kudos to you if you can prove it -- or if you can prove us wrong by coming up with something even smaller!)
\end{enumerate}
\end{enumerate}

\end{document}

