\documentclass{article}
\usepackage{amsmath,amsfonts,amssymb}
\usepackage{diagbox}
\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}
\newcommand{\ATAN}{\operatorname{TAN}^{-1}}
\DeclareMathOperator{\COS}{COS}
\usepackage{lastpage}
\usepackage{fancyhdr}
\pagestyle{fancy}
\headheight 35pt
\rhead{Applicant ID: * * INSERT YOUR APPLICANT ID HERE * *}
\lhead{Mathcamp 2019 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 2019 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
If you take a scientific calculator, type in any number, and then alternate applying the operations $\ATAN$ and $\COS$, then eventually you will reach a point where you run into a cycle: after every $\COS$ step, you will see a result of approximately $0.786$ (and after every $\ATAN$ step, a result of approximately $0.666$ radians, or $38.2$ degrees).
\begin{enumerate}
\item \label{cosarctan-formula} Find a formula for the number you get by starting with $0$ and then
applying the procedure ``apply $\ATAN$ and then $\COS$'' $n$ times. (You may give either an explicit formula or a recursive formula.
\begin{solution}
* * * INSERT PROBLEM 1a SOLUTION HERE * * *
\end{solution}
In either case, you should try to make the formula as simple as possible.)
\item Find an exact formula for the 0.786 number. (You do not need to prove that the formula that you found in
part (a) converges to this number.)
\begin{solution}
* * * INSERT PROBLEM 1b SOLUTION HERE * * *
\end{solution}
\end{enumerate}
\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% PROBLEM 2
\item
Susan and Eric are playing a dice game, with standard six-sided dice which have an equal probability of rolling each integer from $1$ through $6$. Each player takes turns scoring points as follows.
On Susan's turn, she rolls a die. If it's a $1$, she rolls two dice in its place, continuing to replace any $1$s by two new dice. When finally no $1$s are showing, Susan scores points equal to the sum of the remaining dice, and then her turn ends. (For example, suppose she rolls a $1$. Then it gets replaced by two dice; if these are a $3$ and a $1$, the $3$ remains and the $1$ gets replaced by two more; if these are a $2$ and a $4$, then Susan stops and scores $3+2+4=9$ points.)
On Eric's turn, he rolls a die. If it's even, he replaces it with a roll of two dice; if the new total is even, he replaces it with a roll of three dice, etc. He continues to roll one more die than previously as long as his total is even. When he finally rolls an odd total, Eric scores that many points, and then his turn ends.
On average, how many points do Susan and Eric each score on a turn?
\begin{solution}
* * * INSERT PROBLEM 2 SOLUTION HERE * * *
\end{solution}
\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% PROBLEM 3
\item
In the game of Flip Flop, players stand in a circle and take turns saying the numbers $1$, $2$, $3$, etc., going clockwise.
When they get to a multiple of $7$, the player whose turn it is says FLIP instead, and the direction switches: if they were going clockwise before, they now go counterclockwise, or vice versa.
When they get to a multiple if $8$, the player whose turn it is says FLOP instead. The direction stays the same, but the next person is skipped over.
For a number $n$ that is a multiple of both $7$ and $8$, the player says FLIP FLOP. Direction reverses and you skip over the next person. This means $n+1$ is said by the person who said $n-2$.
\begin{enumerate}
\item Show that no matter how many people are in the circle, eventually each person will get a turn to speak.
\begin{solution}
* * * INSERT PROBLEM 3a SOLUTION HERE * * *
\end{solution}
\item Suppose we replace $7$ and $8$ by arbitrary integers $K$ and $M$ respectively. For what values of $K$, $M$ is every player eventually guaranteed get a turn to speak (regardless of the number of players)?
\begin{solution}
* * * INSERT PROBLEM 3b SOLUTION HERE * * *
\end{solution}
\end{enumerate}
\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% PROBLEM 4
\item There is a puzzle with $N^2$ pieces, each one shaped like a wedge that is $1/N$ of a disk. On the front of each piece, each of the two sides of the wedge is labeled with an integer between $1$ and $N$, so that each of the $N^2$ possible ordered pairs occurs exactly once. The goal of the puzzle is to form $N$ full disks in such a way
that the edges come together to have the same label.
\begin{enumerate}
\item Show that the puzzle can be solved when $N=5$.
\begin{solution}
* * * INSERT PROBLEM 4a SOLUTION HERE * * *
\end{solution}
\item Show that the puzzle can be solved for any integer $N \ge 3$. Partial credit will be awarded for a proof that the puzzle can be
solved for infinitely many $N$.
\begin{solution}
* * * INSERT PROBLEM 4b SOLUTION HERE * * *
\end{solution}
\end{enumerate}
\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% PROBLEM 5
\item Every day at noon exactly, people submit orders of positive integer numbers of paninis at your panini store. It takes you $1$ minute to make $1$ panini.
When Alice orders $2$ paninis and Bob orders $100$ paninis, you decide to make Alice's paninis first, because it results in less total customer wait time ($104$ vs.\ $202$ minutes).
\begin{itemize}
\item[(*)] [Warm-up exercise: do not submit an answer] Show that for any set of orders, you achieve the smallest total wait time by processing the smaller orders first.
\end{itemize}
When the town gets wind of your scheme, they hatch devious plans. Instead of ordering $100$ paninis, Bob decides to submit $100$ orders of $1$ panini each under different names, so he gets processed first. Oh no.
Call a panini-making scheme \emph{strategy-free} if no customer, in any scenario, can strictly decrease their average wait time just by splitting their order up into several smaller (integer-size) orders.
Assume your customers are aware of your scheme and will not split up their
orders if the scheme is strategy-free.
\begin{enumerate}
\item Show that the scheme ``choose the sequence of orders uniformly at random'' is strategy-free.
\begin{solution}
* * * INSERT PROBLEM 5a SOLUTION HERE * * *
\end{solution}
\item Give an example of a strategy-free scheme that has a lower average wait time than the above scheme whenever the orders are not all the same size.
\begin{solution}
* * * INSERT PROBLEM 5b SOLUTION HERE * * *
\end{solution}
\item Suppose you know that, on any given day, you will either receive (1) three orders for one panini each, or (2) one order for one panini and one order for two paninis.
Give a strategy-free panini-making scheme such that in either scenario (1) or (2), the average total wait time is at most $25/24$ the optimal total wait time.
\begin{solution}
* * * INSERT PROBLEM 5c SOLUTION HERE * * *
\end{solution}
\end{enumerate}
\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% PROBLEM 6
\item
Jennifer and Serena are playing a game called Candy Split. They start with two piles of candy, one of size $M$ and one of size $K$. On a player's turn, she eats one of the piles and splits the other pile into two (non-empty) piles any way she wants. Whoever can't make a legal move (i.e.~is presented with two piles of one candy each) loses. Note that eating as much candy as possible is not the object of the game, though it may be a pleasant side effect.
\begin{itemize}
\item[(*)] [Warm-up exercise: do not submit an answer] Serena gets to decide whether to go first or second. What should she do when $M = 2018$ and $K = 2019$? What about for general values of $M$ and $K$? (Hint: it's all about the parity of $M$ and $K$.)
\end{itemize}
The reason we're not asking you to submit an answer for the warm-up exercise is that it's a famous problem that can be found in many places on the internet. (Feel free to look it up if you can't figure out the answer.) What we are really interested is a harder problem:
Suppose Jennifer and Serena have three different types of candy. The game is now played with six piles of candy -- two piles of each type. On a player's turn, she chooses a type of candy, eats one of the piles of that type, and splits the other. Whoever can't move loses. If the numbers are $(M_1, K_1), (M_2, K_2)$ and $(M_3, K_3)$, is it better to go first or second, and what is the winning strategy?
In order to solve this problem, you will need to learn a little bit of combinatorial game theory at this link: \href{http://www.mathcamp.org/2019/cgt.pdf}{\texttt{www.mathcamp.org/2019/cgt.pdf}}.
\begin{enumerate}
\item Fill out the following table of nimvalues for Candy Split. The $(M,K)$ entry of your table should show the nimvalue of the game with piles of size $M$ and $K$.
\begin{solution}
* * * INSERT PROBLEM 6a SOLUTION by filling in between the \&s in the tex code below * * *
\begin{center}
\begin{tabular}{c|c|c|c|c|c|c|c|c}
\diagbox[width=3.5em]{$M$}{$K$} & $1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ & $8$ \\ \hline
$1$ & & & & & & & & \\ \hline
$2$ & & & & & & & & \\ \hline
$3$ & & & & & & & & \\ \hline
$4$ & & & & & & & & \\ \hline
$5$ & & & & & & & & \\ \hline
$6$ & & & & & & & & \\ \hline
$7$ & & & & & & & & \\ \hline
$8$ & & & & & & & &
\end{tabular}
\end{center}
\end{solution}
\item The game is $(2,4)$, $(1,8)$, and $(3,5)$. It is Serena's turn. What should she do? Explain how to derive the answer from your table.
\begin{solution}
* * * INSERT PROBLEM 6b SOLUTION HERE * * *
\end{solution}
\item Can you see a pattern in the table? If not, try enlarging the table some more until you see it. (Feel free to use a computer if you'd like, but you can certainly solve the problem without it.)
Based on your conjectured pattern, write down a formula (or algorithm) for computing the nimvalue of $(M, K)$ for all $M$ and $K$. If you can, prove your formula!
\begin{solution}
* * * INSERT PROBLEM 6c SOLUTION HERE * * *
\end{solution}
\item The game is $(2,4)$, $(1,8)$, and $(2019, 2030)$. It is Serena's turn. What should she do? Explain how to derive the answer from your formula or pattern (even if you haven't proved it).
\begin{solution}
* * * INSERT PROBLEM 6d SOLUTION HERE * * *
\end{solution}
\end{enumerate}
\end{enumerate}
\end{document}