\documentclass[11pt]{article}
\usepackage{url}
\urlstyle{tt}
\usepackage{amsmath,amsfonts,amssymb}
\usepackage{tikz}
\usepackage{graphicx,caption,subcaption}
\usepackage{geometry}
\geometry{%
letterpaper,
lmargin=2cm,
rmargin=2cm,
tmargin=2cm,
bmargin=2cm,
footskip=12pt,
headheight=12pt}
\usepackage{parskip}
\usepackage{lastpage}
\usepackage{fancyhdr}
\pagestyle{fancy}
\headheight 35pt
\rhead{Applicant ID: * * INSERT YOUR APPLICANT ID HERE * *}
\lhead{Mathcamp 2017 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}}
\def\a{{\alpha}}
\def\b{{\beta}}
\def\g{{\gamma}}
\begin{document}
\thispagestyle{empty}
\begin{center}\section*{Mathcamp 2017 Qualifying Quiz Solutions}
Applicant ID: * * APPLICATION ID HERE (You can find this in your online application.) * *\end{center}
\subsection*{References} * * * LIST ANY REFERENCES USED HERE. CITE AS APPROPRIATE IN THE SOLUTIONS. * * *
\subsection*{Solutions}
\begin{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% PROBLEM 1
\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.
\begin{solution}
* * * INSERT PROBLEM 1a SOLUTION HERE * * *
\end{solution}
\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.)
\begin{solution}
* * * INSERT PROBLEM 1b SOLUTION HERE * * *
\end{solution}
\item[(c)] If $n=101$, show that no values of $j$ and $k$ will make the game fair.
\begin{solution}
* * * INSERT PROBLEM 1c SOLUTION HERE * * *
\end{solution}
\end{enumerate}
\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% PROBLEM 2
\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?
\begin{solution}
* * * INSERT PROBLEM 2a SOLUTION HERE * * *
\end{solution}
\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?
\begin{solution}
* * * INSERT PROBLEM 2b SOLUTION HERE * * *
\end{solution}
\item Can you generalize the result in (b) to two arbitrary sails?
\begin{solution}
* * * INSERT PROBLEM 2c SOLUTION HERE * * *
\end{solution}
\end{enumerate}
\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% PROBLEM 3
\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$.
\begin{solution}
* * * INSERT PROBLEM 3a SOLUTION HERE * * *
\end{solution}
\item Does there exist a fill-in-the-blank puzzle that has exactly 2018 solutions?
\begin{solution}
* * * INSERT PROBLEM 3b SOLUTION HERE * * *
\end{solution}
\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$?
\begin{solution}
* * * INSERT PROBLEM 3c SOLUTION HERE * * *
\end{solution}
\end{enumerate}
\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% PROBLEM 4
\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?
\begin{solution}
* * * INSERT PROBLEM 4a SOLUTION HERE * * *
\end{solution}
\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?
\begin{solution}
* * * INSERT PROBLEM 4b SOLUTION HERE * * *
\end{solution}
\end{enumerate}
\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% PROBLEM 5
\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?
\begin{solution}
* * * INSERT PROBLEM 5 SOLUTION HERE * * *
\end{solution}
\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% PROBLEM 6
\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.
\begin{solution}
* * * INSERT PROBLEM 6 SOLUTION HERE * * *
\end{solution}
\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% PROBLEM 7
\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?
\begin{solution}
* * * INSERT PROBLEM 7a SOLUTION HERE * * *
\end{solution}
\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$.)
\begin{solution}
* * * INSERT PROBLEM 7b SOLUTION HERE * * *
\end{solution}
\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.
\begin{solution}
* * * INSERT PROBLEM 7c SOLUTION HERE * * *
\end{solution}
\end{enumerate}
\end{enumerate}
\end{document}