\documentclass{article}

\usepackage{amsmath,amsfonts,amssymb}

\usepackage[colorlinks]{hyperref}

\usepackage{graphicx,caption,subcaption}

\usepackage{tikz}

\usepackage{url}
\urlstyle{tt}

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

\begin{document}

\centerline{\Large \bf Mathcamp 2018 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 \href{http://www.mathcamp.org/proofs}{\texttt{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 \href{http://www.mathcamp.org/computers}{\texttt{www.mathcamp.org/computers}}.

If you need clarification on any problem, please email \href{mailto:quiz18@mathcamp.org}{\texttt{quiz18@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 \#1 is due to Stephen Newman, MC '16--'17. The author of problem \#4 wishes to remain anonymous. Problem \#6 is due to Max Jiang, MC '16. Problem \#7 is due to Drake Thomas, MC '14--'17. Problems \#2, \#3, and \#5 were written by the Mathcamp staff.}}

\begin{enumerate}
\item 

Jo\~ao and Kinga play a game with a fair $n$-sided die whose faces are numbered $1, 2, 3, \dots, n$. In this game, Jo\~ao is assigned a value $j$ and Kinga is assigned a value $k$, both also in the range $1, 2, 3, \dots, n$. Jo\~ao and Kinga take turns rolling the die; Jo\~ao goes first.

If Jo\~ao rolls a number less than or equal to $j$, the game ends and he wins. If Kinga rolls a number less than or equal to $k$, the game ends and she wins. The game continues until one player wins.

\begin{enumerate}
\item[(a)] Show that if $j=k$, then Jo\~ao always has an advantage.
\item[(b)] If $n=6$, find all possible values of $j$ and $k$ which make the game fair. (That is, Jo\~ao and Kinga have equal 50\% chances of winning.)
\item[(c)] If $n=101$, show that no values of $j$ and $k$ will make the game fair.
\end{enumerate}

\item The pirates of the Cartesian sail an infinite flat sea, with a small island at coordinates $(x,y)$ for every integer $x$~and~$y$.
\begin{enumerate}
\item A pirate's ship has two sails. Every day, the pirate raises one of the sails and travels for the whole day without stopping. With the first sail raised, a pirate at $(x,y)$ can travel to $(x+3,y+5)$ in a single day, or in the reverse direction to $(x-3,y-5)$. With the second sail raised, a pirate at $(x,y)$ can travel to $(x+4,y+6)$ in a single day, or in the reverse direction to $(x-4,y-6)$.

Which islands can a pirate reach from the island at $(0,0)$, after traveling for any number of days?

\item The Dread Pirate Riemann replaces the second sail on his ship by a sail that lets him travel from $(x,y)$ to either $(x+a,y+b)$ or $(x-a,y-b)$ in a single day, where $a$ and $b$ are integers. (The first sail stays the same as in part (a).) For which values of $a$ and $b$ will the Dread Pirate Riemann be able to reach any island in the Cartesian sea?

\item Can you generalize the result in (b) to two arbitrary sails?
\end{enumerate}

\pagebreak % to avoid splitting #3 and #6 between two pages

\item For any positive integer $n$, its list of divisors contains all integers between 1 and $n$, including 1 and $n$ itself, that divide $n$ with no remainder; they are always listed in increasing order. For example, if $n = 20$, its list of divisors is $1, 2, 4, 5, 10, 20$.

In a fill-in-the-blank puzzle, we take the list of divisors, erase some of them and replace them with blanks, and ask what the original number was.
\begin{enumerate}
\item For example, suppose we have the list
\[
	1,\;2,\; \underline{\phantom{num}},\; \underline{\phantom{num}},\; \underline{\phantom{num}},\; 8,\; \underline{\phantom{num}},\; \underline{\phantom{num}}.
\]
Prove that there is only one way to fill in the blanks to get the list of divisors of a number $n$, and find $n$.
\item Does there exist a fill-in-the-blank puzzle that has exactly 2018 solutions? 
\item For each value of $n$, the \emph{very hard puzzle for $n$} is the one that leaves only the next-to-last divisor, replacing all the others with blanks. For example, the very hard puzzle for $10$ is $\underline{\phantom{num}},\; \underline{\phantom{num}},\;5,\; \underline{\phantom{num}}$. It has two solutions: $10$ and $15$.

For which values of $n$ does the very hard puzzle for $n$ have no solutions other than $n$?
\end{enumerate}

\item A flock of $3^k$ crows hold a speed-flying competition. All crows have different speeds, and each crow's speed remains the same throughout the competition. Because crows love secrecy, they don't want to be distinctive and recognizable, so instead of trying to find the fastest or slowest crow, they want to be as medium as possible.

\begin{enumerate}
\item The crows split into groups of $3$ at random and then race. In each group of $3$, the crow that finishes \emph{second} wins, so there are $3^{k-1}$ winners. 

The $3^{k-1}$ winners repeat this process. In each round, a third of the crows win, and move on to the next round. The crow left after $k$ rounds is declared the most medium crow.

How many of the crows have a chance (depending on which groups of $3$ compete together) of being declared the most medium?

\item If there are $n$ crows, where $n$ is not a power of $3$, this process has to be modified. In a round where the crows cannot be evenly divided into groups of $3$, one or two crows are randomly chosen to sit out: they automatically move on to the next round. After the last round, there will either be one crow left, in which case it is declared the most medium, or two crows, in which case there is a tie. (If there are more than two crows, they can continue with another round.)

For which values of $n$ will a single crow be declared the most medium? When this happens, which of the crows can it be?
\end{enumerate}
\item Take a unit tetrahedron: a 3-dimensional solid with four vertices $A, B, C, D$ all at distance one from each other. We can cut the tetrahedron along a plane that's equidistant from and parallel to edge $AB$ and edge $CD$. If we do, the cross-section is a square with side length 1/2, as shown in the diagram below.

\begin{center}
\begin{tikzpicture}[scale=2]
	\draw [fill] (-0.5,0) circle [radius = 0.05];
	\node [left] at (-0.5,0) {$A$};
	\draw [fill] (1,-0.5) circle [radius = 0.05];
	\node [below] at (1,-0.5) {$D$};
	\draw [fill] (1.5,0.5) circle [radius = 0.05];
	\node [right] at (1.5,0.5) {$B$};
	\draw [fill] (0.5,1.5) circle [radius=0.05];
	\node [above] at (0.5,1.5) {$C$};
	\draw [fill,blue!30] (0,0.75) -- (0.25,-0.25) -- (1.25,0) -- (1,1) -- (0,0.75);
	\draw (1,-0.5) -- (0.5,1.5) -- (-0.5,0) -- (1,-0.5) -- (1.5,0.5) -- (0.5,1.5);
	\draw [dashed] (-0.5,0) -- (1.5,0.5);
\end{tikzpicture}
\end{center}

Now take a unit $5$-cell, which is the $4$-dimensional analog of the tetrahedron: a $4$-dimensional solid with five vertices $A, B, C, D, E$ all at distance one from each other. We can cut the $5$-cell along a $3$-dimensional surface (a hyperplane) that's equidistant from and parallel to edge $AB$ and plane $CDE$. If we do, what (3-dimensional) cross-section do we get?


\item Max finds a large sphere with 2018 rubber bands wrapped around it. Each rubber band is stretched in the shape of a circle. Max notices that any two rubber bands cross each other in two points, and that no three rubber bands cross at the same point.

By the nature of rubber bands, whenever two cross, one is on top of the other. Max has a magic wand that, when tapped on a crossing, switches which rubber band is on top at that crossing. He may use the magic wand any number of times.

Prove that Max can make it so that if he follows each rubber band around the sphere, no rubber band is ever the top band at two consecutive crossings.

\item A tribble is a creature with unusual powers of reproduction. Tribbles come in positive integer sizes. Every night, a tribble grows in size by 1, and every day, any tribble of even size can split into two tribbles of half its size (possibly multiple times), if it wants to. For example, if we started with a tribble of size $6$ on Tuesday, here is one possible way it could grow:
\begin{itemize}
\item Tuesday: Two tribbles of size $3$ (the tribble decides to split).
\item Tuesday night: Two tribbles of size $4$ (both tribbles grow).
\item Wednesday: One tribble of size $4$, one tribble of size $2$, and two tribbles of size $1$ (one of the tribbles of size $4$ splits, and one of the tribbles it produced also splits).
\item Wednesday night: One tribble of size $5$, one tribble of size $3$, and two tribbles of size $2$.
\item Thursday: One tribble of size $5$, one tribble of size $3$, and two tribbles of size $2$ (the tribbles choose not to split).
\item \dots
\end{itemize}

\begin{enumerate}
\item Suppose that we start with a single tribble of size $n$. (We start in the morning, so if $n$ is even, the tribble has a chance to split before it grows.) What is the fastest way in which it could split fully into tribbles of size $1$? How many tribbles of size $1$ would there be?

\item Suppose that we start with a single tribble of size $1$. Let $T(k)$ be the number of different possibilities for what we could see after $k$ days (in the evening, after the tribbles have had a chance to split). For example, $T(1) = 2$, because after 1 day we could see either a tribble of size $2$, or two tribbles of size $1$.

What are the best upper and lower bounds you can give on $T(k)$, in terms of $k$? (In particular, how does it compare to simple functions like $k^2$ or $2^k$ or $2^{2^k}$? We're less interested in the difference between $k^2$ and $10k^2$, or $2^k$ and $2^k + k$.)

\item (EXTRA CREDIT) Given a tribble population such as ``Ten tribbles of size 3", it can be difficult to tell whether it can ever be reached, if we start from a single tribble of size $1$. Can you come up with any simple conditions that tell us that a population can definitely be reached, or that it definitely cannot be reached?

The question probably does not have a general answer, so partial results are welcome. You might, for example, consider populations with only a small number of tribbles, or only a small number of distinct sizes.
\end{enumerate}

\end{enumerate}

\end{document}
