\documentclass{article}

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

\usepackage[left=1in,top=1in,right=1in,nohead,bottom=1in]{geometry}
  
\usepackage{parskip}

\begin{document}

\section*{Mathcamp 2012 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.

Each problem starts out easier and gets harder; there's a good chance that the first part of each problem will be accessible to you, so {\em do} try every problem! 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:quiz12@mathcamp.org}{\nolinkurl{quiz12@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}

%1 

\item A frog jumps along the number line. It starts at 0 and every second it jumps $n$ units to the right (the same positive integer $n$ each time).
After one second, you decide that you want to catch the frog. It's dark, you can't see the frog, and you don't know what $n$ is.  (For all you know, it might be a super-frog, so $n$ could be arbitrarily large.) However, at any given second, you are allowed to choose an integer and search there.  If the frog is on that integer, you'll catch it; if not, you'll have to try again.

\begin{enumerate}

    \item Devise a strategy that will eventually catch the frog. (You'll need to explain which integer you plan to check at each second.)

    \item Now suppose the frog is allowed to start by going either to the left or to the right; once it chooses a direction, it always jumps $n$ units in that direction. Can you devise a strategy for catching it if you don't know which way it's going, and don't know what $n$ is?

    \item What if the conditions in part (b) hold, and you also don't know which integer point the frog started at?  (After you have worked on this problem for a while, it may be useful to read the following article, particularly the section after the proof of Lemma 1:  \url{http://www.cut-the-knot.org/do_you_know/numbers.shtml}.)
    
    \end{enumerate}
    
% 2 
    
\item Each integer on the number line is colored with exactly one of three possible colors -- red, green or blue -- according to the following rules:

\begin{itemize}

\item the negative of a red number must be colored blue,

\item the sum of two blue numbers (not necessarily distinct) must be colored red.

\end{itemize}

\begin{enumerate}
\item Show that the negative of a blue number must be colored red and the sum of two red numbers must be colored blue.
\item Determine all possible colorings of the integers that satisfy these rules.
\end{enumerate}

% 3 

\item Let $p$ be an odd prime.  A group of $p$ campers sit around a circle, and are labeled with the integers $1,2,\ldots,p$ in clockwise order.  The camper with label $1$ yells out the number $1$.  The camper sitting next to this camper in clockwise order yells out $2$.  The camper two spots in clockwise order from the camper who yelled out $2$ yells out $3$.  This process continues:  the camper seated $n$ spots (in clockwise order) from the camper who yelled out $n$ must yell out $n+1$.  A camper gets a cookie anytime she or he yells out a number.

\begin{enumerate}

\item Show that there is a camper who never gets a cookie.

\item Of the campers who do get cookies, is there one who at some point has at least ten more cookies than the others?

\item Of the campers who do get cookies, is there one who at some point has at least ten fewer cookies than the others?

\end{enumerate}

% 4 

\item  Let $a$ be a rational number with $0 < a < 1$.  A \emph{lollipop} in the $xy$-plane with \emph{base} $(a,0)$ consists of a line segment from $(a,0)$ to some point $(a,b)$ with $b>0$, together with a filled in disc of radius less than $b$, centered at $(a,b)$.  Determine whether or not it is possible to have a set of lollipops in the $xy$-plane satisfying both of the following conditions:

\begin{itemize}

\item for every rational number $a$ with $0<a<1$, there is a lollipop whose base is the point $(a,0)$,

\item no two lollipops touch or overlap each other.

\end{itemize}

If such a set of lollipops exists, explain how to construct it.  If not, justify why not.

% 5 

\item  A convex body in the plane is a region with positive area such that for any two points in this region, the entire line segment between them also lies within the region. Let $P$ be the perimeter (i.e., boundary) of a convex body in the plane.  We will assume throughout this problem that $P$ is \emph{centrally symmetric}: that is, if $(a,b)$ is a point on $P$, then so is $(-a,-b)$.  

For any nonnegative real number $k$, we define $kP$ to be the subset of the plane obtained by multiplying all the points of $P$ by $k$ in each coordinate. In other words, for each point $(a,b)$ of $P$, the point $(ka,kb)$ is in $kP$.  

If $(x_1,y_1),(x_2,y_2)$ are two points in the plane, we define the \emph{$P$-distance} between them to be the smallest nonnegative real number $k$ such that when the set $kP$ is translated by $(x_1,y_1)$ (i.e., by $x_1$ units horizontally and by $y_1$ units vertically), the point $(x_2,y_2)$ lies on it.  For example, if $P$ is the square with vertices $(0,1),(1,0),(0,-1),(-1,0)$, then the $P$-distance between $(3,5)$ and $(4,10)$ is $6$.

\begin{enumerate}

\item Let $P$ be the perimeter of a disc of radius 1 centered at the origin. Find a formula for the $P$-distance between any two points $(a,b)$ and $(c,d)$ in the plane.

\item Let $P$ be the perimeter of a rhombus with vertices $(2,0),(-2,0),(0,3),(0,-3)$. Find a formula for the $P$-distance between any two points $(a,b)$ and $(c,d)$ in the plane.

\item In part (a), we took it for granted that a filled-in disc of radius $1$ is a convex body. Prove this rigorously, using the definition of convexity given above.

\item Suppose $P$ is a convex quadrilateral.  What are the possible $P$-distances between vertices of $P$?  What about when $P$ is a convex hexagon? (Remember:  $P$ must still be centrally symmetric!)

\item Let $P$ be the perimeter of some centrally symmetric convex body, and let $(a,b)$ be a point on $P$.  What is the largest possible $P$-distance from $(a,b)$ to another point on~$P$?  Will $(a,b)$ be at this $P$-distance from just one other point on $P$ or from multiple other points? (If any of your answers depend on the geometry of $P$ and/or on the choice of $(a,b)$, explain how.)

\item In principle, we could define $P$-distance even when $P$ doesn't come from a convex body and/or is not centrally symmetric. But it turns out that in both of these cases, the definition is problematic: the resulting quantity doesn't behave in the ways we expect a ``distance" to behave.  Can you determine what problematic issues arise?

\end{enumerate}

% 6 
\newpage
\item  An ocean has infinitely many islands. Every island is labeled by one of the integers $\{\ldots,-3,-2,-1,0,1,2,3,\ldots\}$, with no two islands having the same label and every integer being the label of some island.  Two islands are connected by a bridge if their labels differ by a power of two.  For instance, there is a bridge connecting island $7$ and island $-25$.  

We define the \emph{distance} between two islands $k_1$ and $k_2$ to be the minimum number of bridges needed to get from $k_1$ to $k_2$.  For instance, the distance between the islands $0$ and $7$ is $2$. (You can move from island $0$ to island $8$, then to island $7$; this is the minimum, since you can't go from $0$ to $7$ using just one bridge.)  

\begin{enumerate}

\item  Show that for any integer $r \geq 1$, you can find two islands in the ocean at distance $r$ from each other.

\item An \emph{infinite path} in our ocean consists of an infinite set of islands $\mathcal{I}$ and an infinite set of bridges $\mathcal{B}$, with each bridge in $\mathcal{B}$ joining two islands in the set $\mathcal{I}$, such that: 

\begin{itemize}
	\item every island in $\mathcal{I}$ is connected to exactly two bridges in $\mathcal{B}$,
	\item for any two islands in $\mathcal{I}$, you can get from one to the other using only bridges in $\mathcal{B}$.
\end{itemize}

Here is one example of an infinite path: let $\mathcal{I}$ be the set of all odd-numbered islands and let $\mathcal{B}$ be the set of bridges between islands in $\mathcal{I}$ whose  labels differ by 2. It is easy to see that $\mathcal{I}$ and $\mathcal{B}$ satisfy both conditions for an infinite path: 

\begin{itemize}
	\item Each island $k$ in $\mathcal{I}$ is connected to exactly two bridges in $\mathcal{B}$ -- namely, the bridges leading to islands $k-2$ and $k+2$;
	\item To get from any odd-numbered island to any other using bridges in $\mathcal{B}$, you start  at the smaller number and keep adding 2. 
\end{itemize}

As a warm-up, can you create an infinite path with the \emph{same} $\mathcal{I}$ as in the example above, but with a \emph{different} $\mathcal{B}$?

\item Is it possible to construct an infinite path in our ocean such that, for any two islands $k_1$, $k_2$ in $\mathcal{I}$,  the minimum number of bridges in $\mathcal{B}$ needed to get from $k_1$ to $k_2$ is exactly the distance between $k_1$ and $k_2$?  For instance, the infinite path in our example does \emph{not} have this property: it takes two bridges in $\mathcal{B}$ to go from  island 1 to island 5 (you have to go via island 3), even though the distance between these two islands is 1 (there is a single bridge not in $\mathcal{B}$ that connects them to each other).  If your answer is yes, give an example of sets $\mathcal{I}$ and $\mathcal{B}$ that work. If your answer is no, prove that it can't be done. 

\item Does there exist a set $\mathcal S$ of 9 islands such
that:

\begin{itemize}
	\item the configuration of bridges connecting
pairs of islands in $\mathcal S$ is exactly as in the picture below (with no additional bridges between any of the islands),
and
	\item the distance between any two islands in $\mathcal S$ equals the minimum number of bridges needed to get from one island to the other via
islands in $\mathcal S$?
\end{itemize}

\begin{center}
\includegraphics[scale=0.7]{qquiz-grid}
\end{center}

What if, instead of a 3 $\times$ 3 grid, we had an $n \times n$ grid: for which $n$ is such a configuration possible?

\item Suppose, in a sea far away, we have islands labeled in the same way, with two islands connected by a bridge if their labels differ by a power of $3$.  Is there a one-to-one correspondence between islands in the ocean and islands in the far-away sea, such that two islands in the ocean are connected by a bridge precisely when the corresponding two islands in the sea are connected by a bridge?
\end{enumerate}

% 7 
\newpage
\item   Last summer, the graduate students teaching at Mathcamp (we call them ``mentors") arranged themselves into a pyramid with four layers:

\begin{center}
\includegraphics[scale=0.5]{qquiz-mentorpyramid}
\end{center}

Now suppose we generalize this to a pyramid with $n$ layers ($n$ mentors in the bottom row, $n - 1$ mentors in the row above, etc.). Assume that all mentors have weight 1 and that each mentor supports his/her own weight plus half the weight supported by the one or two mentors leaning on him/her. For instance, in our four-layer mentor pyramid, the weights supported by the mentors are
\[
\begin{tabular}{rccccccccc}
    layer 1:&    &    &    &  1\\\noalign{\smallskip\smallskip}
    layer 2:&    &    &  3/2 &    &  3/2\\\noalign{\smallskip\smallskip}
    layer 3:&    &  7/4 &    &  5/2 &    &  7/4\\\noalign{\smallskip\smallskip}
    layer 4:&  15/8 &    &  25/8 &    &  25/8 &    &  15/8\\\noalign{\smallskip\smallskip}
\end{tabular}
\]

\begin{enumerate}

\item Find the weight supported by the mentor at the bottom left corner of a pyramid with $n$ layers.

\item Now suppose the pyramid has infinitely many layers.  Let $W(k,m)$ be the weight supported by the $(k+1)$-th mentor from the left in the $(m+1)$-th layer.  For instance, $W(0,0)=1, W(0,1)=W(1,1)=3/2,$ etc.  Determine a recursive formula satisfied by the function $W(k,m)$, for $k,m \geq 0$.

\item Find an explicit formula for $W(k,2k)$ in terms of $k$, for $k \geq 0$. If you can't find a fully explicit formula, can you find one that uses summation notation?

\item {\bf Extra credit:} What can you say about $W(k,m)$ in general?
\end{enumerate}



\noindent Note: If you're not sure what we mean by ``explicit" and ``recursive" formulas, take a look at \url{http://www.regentsprep.org/Regents/math/algtrig/ATP3/Recursive.htm} . 

\end{enumerate}

\end{document}