\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}
\begin{document}
\centerline{\Large \bf Mathcamp 2019 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:quiz19@mathcamp.org}{\texttt{quiz19@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{All problems were written by the Mathcamp staff.}}
\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.
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.)
\end{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 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?
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 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.
\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)?
\end{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 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. Below is an example of some pieces fitting together
to form a full disk when $N=5$.
\begin{center}
\includegraphics[width=5.5in]{qquiz-2019-25-puzzle.png}
\end{center}
\begin{enumerate}
\item Show that the puzzle can be solved when $N=5$.
\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$.
\end{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 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.
\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.
\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.
\end{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 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{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}
\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.
\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!
\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).
\end{enumerate}
\end{enumerate}
\end{document}