\documentclass[11pt]{article}
\usepackage{url}
\urlstyle{tt}
\usepackage{amsmath,amsfonts,amssymb}
\usepackage{dialogue}
\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 Lotta is a consulting mathematician who specializes in very large numbers. She runs a business with 100 clients ranked 1 through 100 in order of importance. (The most important client is ranked 1.) Each day, Lotta has time to visit only one of her clients.
A client feels mistreated if Lotta has never visited them, or if Lotta has visited someone less important since the last time she visited them. Every day, Lotta visits the most important client that feels mistreated. On the first day, she visits client 1; on the second day, she visits client 2; on the third day, she goes back to client 1, and so on.
When none of Lotta's clients feel mistreated, she can finally retire.
\begin{enumerate}
\item Prove that Lotta will be able to retire someday.
\begin{solution}
* * * INSERT PROBLEM 1a SOLUTION HERE * * *
\end{solution}
\item Over the course of Lotta's career, how many days will the $N^{\text{th}}$ client wake up feeling mistreated?
\begin{solution}
* * * INSERT PROBLEM 1b SOLUTION HERE * * *
\end{solution}
\item Describe the set of people that wake up feeling mistreated on the $N^{\text{th}}$ day.
\begin{solution}
* * * INSERT PROBLEM 1c SOLUTION HERE * * *
\end{solution}
\end{enumerate}
\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% PROBLEM 2
\item (This problem is about some curious relations between the sums of certain entries of Pascal's triangle. You may find the following background reading useful: \url{http://www.mathcamp.org/2017/pascal.pdf}.)
\newcommand{\sss}[3]{\genfrac{\lgroup}{\rgroup}{0pt}{}{#1}{#2 \bmod #3}}
In this problem, we define
\[
\sss{n}{k}{m} = {n \choose k} + {n \choose k+m} + {n \choose k+2m} + \cdots
\]
where the sum includes every $m^{\text{th}}$ element between $0$ and $n$ inclusive, starting at $k$. For example,
\[
\sss{20}{2}{5} = {20 \choose 2} + {20 \choose 7} + {20 \choose 12} + {20 \choose 17}.
\]
\begin{enumerate}
\item Find, with proof, $\sss n02$ and $\sss n12$. (This is a well-known result that you may have seen before; in that case, consider it a warm-up.)
\begin{solution}
* * * INSERT PROBLEM 2a SOLUTION HERE * * *
\end{solution}
\item Show that $\sss n03$ is always one of the two integers closest to $\frac{2^n}{3}$. For which values of $n$ is it larger than $\frac{2^n}{3}$, and for which values of $n$ is it smaller?
\begin{solution}
* * * INSERT PROBLEM 2b SOLUTION HERE * * *
\end{solution}
\item Let $D_n$ be the difference between the largest and the smallest among the numbers
\[
\sss n05, \sss n15, \sss n25, \sss n35, \text{ and }\sss n45.
\]
Find $D_n$.
\begin{solution}
* * * INSERT PROBLEM 2c SOLUTION HERE * * *
\end{solution}
\end{enumerate}
\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% PROBLEM 3
\item It's the week before Mathcamp, and the $N$ mentors are frantically preparing their classes. The Mathcamp library is open around the clock, and each mentor visits it once in every 24 hour period. They follow a strict schedule: each mentor has a set time when they enter the library and a set time when they leave. (Some mentors work through the night, arriving in the evening and leaving in the morning.) No mentor arrives or departs at the exact same time as another: all $2N$ times are different.
It so happens that:
\begin{itemize}
\item There are 47 pairs of distinct mentors that sometimes see each other in the library. (All other pairs of mentors visit the library at non-overlapping times.)
\item One day, the mentors decide to estimate the typical number of mentors in the library. That day, each mentor writes down the number of other mentors in the library when they arrive and again when they leave (not counting themselves). The average of these $2N$ numbers is $4$.
\item Two of the mentors, Jane and Sam, are so dedicated that at any time of day or night, at least one of them is in the library. (They are the only pair of mentors with this property.)
\end{itemize}
\begin{enumerate}
\item What is $N$, the number of mentors at Mathcamp?
\begin{solution}
* * * INSERT PROBLEM 3a SOLUTION HERE * * *
\end{solution}
\item Suppose we vary $A=47$ (the number of pairs of mentors that see each other), $B=4$ (the average computed by the mentors), and $C=1$ (the number of mentor pairs like Jane and Sam). Find an equation for $N$ in terms of $A$, $B$, and $C$.
\begin{solution}
* * * INSERT PROBLEM 3b SOLUTION HERE * * *
\end{solution}
\end{enumerate}
\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% PROBLEM 4
\item Let $k$ be a positive integer, and let $\mathcal E_k$ be the equation
\[
m(m+1) = n(n+k).
\]
A solution to $\mathcal E_k$ is a pair of positive integers $m$ and $n$ that satisfy the equation. For example, solutions to $\mathcal E_{2017}$ include $m=3459, n=2595$ and $m=4484, n=3588$. (There are others as well.)
\begin{enumerate}
\item For what positive integers $k$ does $\mathcal E_k$ have no solutions? Be sure to prove your answer, including showing that $\mathcal E_k$ \emph{does} have a solution for all other values of $k$.
\begin{solution}
* * * INSERT PROBLEM 4a SOLUTION HERE * * *
\end{solution}
\item Find, with proof, the solutions to $\mathcal E_{2017}$ with the smallest and the largest possible values of $m$.
\begin{solution}
* * * INSERT PROBLEM 4b SOLUTION HERE * * *
\end{solution}
\item Show that, with a few exceptions, it is impossible for both $\mathcal E_k$ and $\mathcal E_{k+1}$ to have exactly one solution. What are the exceptions?
\begin{solution}
* * * INSERT PROBLEM 4c SOLUTION HERE * * *
\end{solution}
\end{enumerate}
\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% PROBLEM 5
\item Wizards live in towers that have infinitely many floors, numbered $1, 2, 3, \dots$. The floors are not connected by staircases or any other mundane means. Instead, for every positive integer $N$, there is a red magic portal connecting floor $N$ to floor $N+10$, and a blue magic portal connecting floor $N$ to floor $3N+1$. The portals go both ways; for example, starting at floor 26, you could descend to floor 16 by a red portal, descend to floor 5 by a blue portal, and ascend to floor 15 by a red portal.
Of course, an infinitely tall tower would have enough room for multiple wizards. But wizards refuse to share: two wizards refuse to both live in the tower if it's possible to get from one wizard's floor to the other wizard's floor using the magic portals.
\begin{enumerate}
\item How many wizards could live together in such a tower?
\begin{solution}
* * * INSERT PROBLEM 5a SOLUTION HERE * * *
\end{solution}
\item If the red portals instead connected floor $N$ to floor $2N+1$, and the blue portals instead connected floor $N$ to floor $8N+1$, how many wizards could live in the tower?
\begin{solution}
* * * INSERT PROBLEM 5b SOLUTION HERE * * *
\end{solution}
\item If the red portals instead connected floor $N$ to floor $2N+1$, and the blue portals instead connected floor $N$ to floor $3N+1$, how many wizards could live in the tower?
\begin{solution}
* * * INSERT PROBLEM 5c SOLUTION HERE * * *
\end{solution}
\end{enumerate}
\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% PROBLEM 6
\item
\emph{(This problem first appeared on Mathcamp 2015's weekly Team Problem Solving competition.)}
A \emph{triangle function} assigns a nonnegative real number to all nondegenerate triangles. We call a triangle function $f$ \emph{consistent} if any two congruent triangles are assigned the same value: $f(\triangle ABC) = f(\triangle DEF)$ whenever $\triangle ABC \cong \triangle DEF$.
Suppose that for some $\triangle ABC$, points $X$, $Y$, and $Z$ are chosen in the interior of sides $AB$, $AC$, and $BC$, respectively. If a triangle function $f$ satisfies \[f(\triangle AXY) + f(\triangle BXZ) + f(\triangle CYZ) = f(\triangle ABC)\] for all choices of $\triangle ABC$, $X$, $Y$, and $Z$, we say that $f$ has the \emph{triforce property}.
Is there a consistent triangle function with the triforce property, other than the trivial function assigning the value~0 to every triangle?
\begin{solution}
* * * INSERT PROBLEM 6 SOLUTION HERE * * *
\end{solution}
\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% PROBLEM 7
\item Waldo and Carmen play a guessing game played in $N$ cities located on a large ring around the earth. Two cities that are next to each other in the ring are chosen uniformly at random. Waldo is sent to one of them and Carmen is sent to the other. Neither player knows which of the adjacent cities the other is in (but each knows her or his own location).
Starting with Waldo, the players take turns guessing where the other is. More precisely:
\begin{itemize}
\item A player can choose to name any of the $N$ cities as their guess.
\item Each player hears the other's guesses and can use that information when making future guesses.
\item A player's guessing strategy can be probabilistic: they can decide to guess City 1 with probability $p$, City 2 with probability $q$, and so on.
\end{itemize}
The first player to guess correctly wins.
\begin{enumerate}
\item If $N=3$, find a strategy for Waldo that wins him the game with probability at least $\frac23$, no matter what strategy Carmen uses.
\begin{solution}
* * * INSERT PROBLEM 7a SOLUTION HERE * * *
\end{solution}
\item If $N=3$, find a strategy for Carmen that wins her the game with probability at least $\frac13$, no matter what strategy Waldo uses.
\begin{solution}
* * * INSERT PROBLEM 7b SOLUTION HERE * * *
\end{solution}
\item What are Waldo and Carmen's optimal strategies in the general case? (You might want to try $N=6$ and $N=8$ to begin with.)
\begin{solution}
* * * INSERT PROBLEM 7c SOLUTION HERE * * *
\end{solution}
\end{enumerate}
\end{enumerate}
\end{document}