\documentclass[11pt]{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{lastpage}
\usepackage{fancyhdr}
\pagestyle{fancy}
\headheight 35pt

\rhead{ * * * INSERT YOUR NAME HERE  * * *}
\lhead{Mathcamp 2012 Qualifying Quiz}
\cfoot{Page \thepage\ of \pageref{LastPage}}

\def\squarebox#1{\hbox to #1{\hfill\vbox to #1{\vfill}}}
\def\qed{\hspace*{\fill}
        \vbox{\hrule\hbox{\vrule\squarebox{.667em}\vrule}\hrule}}
\newenvironment{solution}{\begin{trivlist}\item[]{\bf Solution:}}
                      {\qed \end{trivlist}}
                      
\begin{document}

\thispagestyle{empty}

\begin{center}\section*{Mathcamp 2012 Qualifying Quiz Solutions}

Name:   * * * INSERT YOUR NAME HERE  * * *\end{center}

\subsection*{References}   * * * LIST ANY REFERENCE TEXTS USED HERE.   CITE AS APPROPRIATE IN THE SOLUTIONS. * * *

\subsection*{Solutions}

\begin{enumerate}

\item  %PROBLEM 1
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.)

\begin{solution}
* * *  INSERT PROBLEM 1a SOLUTION HERE * * *
\end{solution}

    \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?

\begin{solution}
* * *  INSERT PROBLEM 1b SOLUTION HERE * * *
\end{solution}


    \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}.)

\begin{solution}
* * *  INSERT PROBLEM 1c SOLUTION HERE * * *
\end{solution}

    
    \end{enumerate}

\newpage
\item  %PROBLEM 2
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.
\begin{solution}
* * *  INSERT PROBLEM 2a SOLUTION HERE * * *
\end{solution}


\item Determine all possible colorings of the integers that satisfy these rules.
\begin{solution}
* * *  INSERT PROBLEM 2b SOLUTION HERE * * *
\end{solution}


\end{enumerate}


\newpage
\item  %PROBLEM 3
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.
\begin{solution}
* * *  INSERT PROBLEM 3a SOLUTION HERE * * *
\end{solution}

\item Of the campers who do get cookies, is there one who at some point has at least ten more cookies than the others?
\begin{solution}
* * *  INSERT PROBLEM 3b SOLUTION HERE * * *
\end{solution}

\item Of the campers who do get cookies, is there one who at some point has at least ten fewer cookies than the others?
\begin{solution}
* * *  INSERT PROBLEM 3c SOLUTION HERE * * *
\end{solution}


\end{enumerate}

\newpage
\item  %PROBLEM 4
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.
\begin{solution}
* * *  INSERT PROBLEM 4 SOLUTION HERE * * *
\end{solution}


\newpage
\item  %PROBLEM 5
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.
\begin{solution}
* * *  INSERT PROBLEM 5a SOLUTION HERE * * *
\end{solution}

\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.
\begin{solution}
* * *  INSERT PROBLEM 5b SOLUTION HERE * * *
\end{solution}

\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.
\begin{solution}
* * *  INSERT PROBLEM 5c SOLUTION HERE * * *
\end{solution}

\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!)
\begin{solution}
* * *  INSERT PROBLEM 5d SOLUTION HERE * * *
\end{solution}

\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.)
\begin{solution}
* * *  INSERT PROBLEM 5e SOLUTION HERE * * *
\end{solution}

\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?
\begin{solution}
* * *  INSERT PROBLEM 5f SOLUTION HERE * * *
\end{solution}

\end{enumerate}


\newpage
\item  %PROBLEM 6
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.
\begin{solution}
* * *  INSERT PROBLEM 6a SOLUTION HERE * * *
\end{solution}


\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}$?
\begin{solution}
* * *  INSERT PROBLEM 6b SOLUTION HERE * * *
\end{solution}

\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. 
\begin{solution}
* * *  INSERT PROBLEM 6c SOLUTION HERE * * *
\end{solution}

\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 a $3\times3$ lattice (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}

What if, instead of a 3 $\times$ 3 grid, we had an $n \times n$ grid: for which $n$ is such a configuration possible?
\begin{solution}
* * *  INSERT PROBLEM 6d SOLUTION HERE * * *
\end{solution}


\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?
\begin{solution}
* * *  INSERT PROBLEM 6e SOLUTION HERE * * *
\end{solution}


\end{enumerate}


\newpage
\item  %PROBLEM 7
Last summer, the graduate students teaching at Mathcamp (we call them ``mentors") arranged themselves into a pyramid with four layers. 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.
\begin{solution}
* * *  INSERT PROBLEM 7a SOLUTION HERE * * *
\end{solution}

\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$. 
\begin{solution}
* * *  INSERT PROBLEM 7b SOLUTION HERE * * *
\end{solution}

\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?
\begin{solution}
* * *  INSERT PROBLEM 7c SOLUTION HERE * * *
\end{solution}

\item {\bf Extra credit:} What can you say about $W(k,m)$ in general?
\begin{solution}
* * *  INSERT PROBLEM 7 EXTRA CREDIT SOLUTION HERE * * *
\end{solution}


\end{enumerate}


%%%%%

\end{enumerate}

\end{document}