\documentclass{article}

%\usepackage[varg]{txfonts}
%\usepackage{hyperref}
\usepackage{amsmath}
\usepackage{graphicx,caption,subcaption}
\usepackage{url}
\urlstyle{tt}

\usepackage{dialogue} 

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

\begin{document}

\centerline{\Large \bf Mathcamp 2016 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 have to justify all your assertions and prove to us that your solution is correct. (For some tips on writing proofs, see \url{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 are roughly in increasing order of difficulty, but even 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 three or four 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 investigations: partial solutions, conjectures, methods -- everything counts. Also, if you come up with a solution that is messy and ugly, see if you can find a better way of thinking about the problem: elegance and clarity count too! 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 \url{www.mathcamp.org/computers}.

If you need clarification on any problem, please email \url{quiz16@mathcamp.org}. 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! {\em Any deviation from these rules will be considered plagiarism and may disqualify you from attending Mathcamp.}

\subsection*{The Problems\footnote{Problem \#2 is due to Palmer Mebane, MC '07--'08; problem \#3 is due to Waley Zhang, MC '14--'15; problems \#4 and \#6 are due to Drake Thomas, MC '14--'15; problems \#1 and \#5 were written by the Mathcamp staff.}}

\begin{enumerate}

\item It is the future, and you are working as an alchemist in the depths of the Earth's core. You work in the business of turning silver into gold and back. Each silver piece is worth $1$ dollar; each gold piece is worth $\Phi = \frac{1 + \sqrt{5}}{2}$ dollars.

You start with a single piece of silver. On your first day of the job, you turn the silver piece into a gold piece. On each successive day, you turn each silver piece from the previous day into a gold piece, and each gold piece from the previous day into two pieces, one silver and one gold. So at the end of day 1, you have 1 gold piece; at the end of day 2, you have 1 gold piece and 1 silver piece; at the end of day 3, you have 2 gold pieces and 1 silver piece.Prove that at the end of day $n$, your treasure is worth $\Phi^n$ dollars for all positive integers $n$.

\item Francisco and Savannah are playing a game with two tokens, which are placed on the squares of a rectangular grid of arbitrary size, as shown in either part of Figure~\ref{fig:token-game}. The two tokens must be in different rows and columns. The players take turns moving a token of their choice to any different square (not necessarily just an adjacent one) satisfying the following constraints:
\begin{itemize}
\item Tokens can never be moved upward or to the right. 
\item The row ordering must be preserved: if one token is above the other, it must stay above the other.  
\item The column ordering must be preserved: if one token is to the right of the other, it must stay to the right of the other.
\end{itemize}
Francisco goes first. Whichever player has no legal moves (with either token) loses. 

\begin{enumerate}
\item Suppose one token begins above and to the right of the other, as in Figure~\ref{fig:first-game}. (The constraints require that the two tokens stay in that order.) For which starting positions does Francisco win and for which does Savannah win? What is the winning strategy in each case?

\item Do the same analysis assuming one token begins below and to the right of the other, as in Figure~\ref{fig:second-game}. (The constraints require that the two tokens stay in that order.) 

\end{enumerate}
\pagebreak

\begin{figure}[h]
	\centering
	\begin{subfigure}[b]{0.3\textwidth}
		\includegraphics[width=\textwidth]{quiz-palmer-1.png}
		\caption{One token is above and to the right of the other.}
		\label{fig:first-game}
	\end{subfigure}
	\qquad
	\begin{subfigure}[b]{0.3\textwidth}
		\includegraphics[width=\textwidth]{quiz-palmer-2.png}
		\caption{One token is below and to the right of the other.}
		\label{fig:second-game}
	\end{subfigure}
	\caption{The token game.}
	\label{fig:token-game}
\end{figure}

\item Given an arbitrary triangle cut out from paper, we can fold one of its sides in half, so that one corner overlaps with another. This makes a crease through the midpoint of that side, as in Figure~\ref{fig:first-crease}.

\begin{figure}[h]
	\centering
	\begin{subfigure}[b]{0.3\textwidth}
		\includegraphics[width=\textwidth]{quiz-folding-1.png}
		\caption{Folding a triangle in half.}
		\label{fig:first-crease}
	\end{subfigure}
	\qquad
	\begin{subfigure}[b]{0.3\textwidth}
		\includegraphics[width=\textwidth]{quiz-folding-2.png}
		\caption{A triangle with all three creases.}
		\label{fig:three-creases}
	\end{subfigure}
	\caption{Making creases in a triangle.}
	\label{fig:creases}
\end{figure}

Unfolding and repeating with the other two sides, we get two more creases, as in Figure~\ref{fig:three-creases}.

\begin{figure}
  \centering
\end{figure}

\begin{enumerate}
\item If two of the three creases have the same length, must the triangle be isosceles?
\item If all three creases have the same length, must the triangle be equilateral?
\end{enumerate}

\item Drake is thinking of a positive integer $x$. He tells Misha the number of digits $x$ has in base 2. He tells Ivy the number of digits $x$ has in base 3. For example, if Drake thinks of $x = 11 = 1011_2 = 102_3$, he'll tell Misha ``$x$ has 4 digits in base 2'' and he'll tell Ivy ``$x$ has 3 digits in base 3''.

\begin{enumerate}
\item[(a)] Drake alternates asking Misha and Ivy if they know $x$. They have the following conversation:

\begin{dialogue}
	\speak{Misha} No, I don't know $x$.
	\speak{Ivy} No, I don't know $x$.
	\speak{Misha} Yes, now I know $x$.
	\speak{Ivy} Yes, now I know $x$.
\end{dialogue}

What was $x$?

\item[(b)] Suppose Drake instead chooses some other functions $f$ and $g$, tells Misha $f(x)$, and tells Ivy $g(x)$. Drake then alternates asking them if they know $x$ until they both say ``Yes''. The functions $f$ and $g$ are common knowledge: you, Misha, and Ivy all know what they are. But of course, you don't know the particular numbers $f(x)$ and $g(x)$ that Drake tells Misha and Ivy.

Can Drake choose functions $f$ and $g$ such that you can always deduce $x$ just by listening to Misha and Ivy's conversation? 
\end{enumerate}

\newpage



\item We call some positive integers \emph{oddly nice} according to the following rules:
\begin{itemize}
\item 1 is oddly nice.
\item An integer $n>1$ is oddly nice if and only if an odd number of its proper divisors are oddly nice.
\end{itemize}
Which numbers are oddly nice? If $s(n)$ is the number of oddly nice proper divisors of an integer $n$, what are all the possible values of $s(n)$? Prove your answer.

You might find the following background reading useful: \url{www.cut-the-knot.org/blue/NumberOfFactors.shtml}.


\item Waley starts with a list of all the positive integers in order. He can perform the following operations on it:
\begin{itemize}
\item A $2$-flip, which reverses pairs of elements, turning $1, 2, 3, 4, 5, 6, \dots$ into $2, 1, 4, 3, 6, 5, \dots$.

\item A $3$-flip, which reverses triples of elements, turning $1, 2, 3, 4, 5, 6, \dots$ into $3, 2, 1, 6, 5, 4, \dots$.

\item More generally, an $n$-flip, for any integer $n>1$: the list is split into groups of $n$ consecutive terms, and then each group is reversed.
\end{itemize}

Waley can perform any number of these operations, in any order. For instance, he can perform a $2$-flip and then a $3$-flip, which will first turn $1, 2, 3, 4, 5, 6, 7, 8, \dots$ into $2, 1, 4, 3, 6, 5, 8, 7, \dots$ and then into $4, 1, 2, 5, 6, 3, 10, 7, 8, \dots$.

If you give Waley a finite sequence of distinct positive integers, when can he put that sequence at the beginning of his list (in order)? You should find a strategy for Waley to follow whenever this can be done, and prove that all other sequences are not attainable.

\end{enumerate}

\end{document}
