\documentclass[12pt]{article} % setsfont size and layout
%% required packages %%
\usepackage[margin=2.5cm]{geometry} % margins
\usepackage{amsfonts,latexsym,amsthm,amssymb,amsmath,amscd,euscript} % math formulas
\usepackage{graphicx} % graphics
\usepackage{fancyhdr} % header and footer on every page
\usepackage{setspace} % line space (e.g. \singlespacing, \onehalfspacing or \doublespacing)
\usepackage{xcolor} % allows us to grey out the problem statement
%% Some more settings %%
\setlength{\parindent}{0pt} % first line in paragraph will not be indented
\AtBeginDocument{\setstretch{1.125}} % uncompactify
\usepackage[parfill]{parskip}
\usepackage{lastpage}
\usepackage{fancyhdr}
\pagestyle{fancy}
\headheight 35pt
\newcommand{\statement}[1]{\textcolor[rgb]{0.27,0.51,0.70}{#1}} %change the color of problem statements to distinguish from solutions
%% Header on top of each page with applicant ID etc. %%
%%%%%%%%% IMPORTANT! %%%%%%%%%%%%%%
\rhead{Applicant ID: ???? } % REPLACE ???? WITH YOUR APP ID
%%%%%%%%% IMPORTANT! %%%%%%%%%%%%%%
\lhead{Mathcamp 2021 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}}
%Below are the theorem, definition, example, lemma, etc. body types.
\newtheorem{theorem}{Theorem}
\newtheorem*{proposition}{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{postulate}[theorem]{Postulate}
\theoremstyle{definition}
\newtheorem{defn}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\theoremstyle{remark}
\newtheorem*{remark}{Remark}
\newtheorem*{notation}{Notation}
\newtheorem*{note}{Note}
% You can define new commands to make your life easier.
\newcommand{\BR}{\mathbb R}
\newcommand{\BC}{\mathbb C}
\newcommand{\BF}{\mathbb F}
\newcommand{\BQ}{\mathbb Q}
\newcommand{\BZ}{\mathbb Z}
\newcommand{\BN}{\mathbb N}
%% Here the main part of the document begins %%
\begin{document}
\thispagestyle{empty}
\begin{center}\section*{Mathcamp 2021 Qualifying Quiz Solutions}
%%%%%%%%% IMPORTANT! %%%%%%%%%%%%%%
Applicant ID: * * WRITE YOUR APPLICATION ID HERE (You can find this in your online application.) * *\end{center}
%%%%%%%%% IMPORTANT! %%%%%%%%%%%%%%
% Do not write your name on your Quiz! We read Quizzes without looking at the names so as not to introduce implicit bias. Thank you!
\vspace*{0.3cm} % vertical space between header on top of the page and main content
\subsection*{References} * * * LIST ANY REFERENCES USED HERE. CITE THEM AS APPROPRIATE IN THE SOLUTIONS. * * *
\section*{Problem 1}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% PROBLEM 1
People at Mathcamp can be in one of three categories: campers, JCs, and mentors. There is a universal rule about what happens when they talk: Mentors always lie to campers; campers always lie to JCs; JCs always lie to mentors. Except for these three cases, everyone always tells the truth.
\begin{enumerate}
\item[(a)] \statement{Sachi and Yuval have a conversation. Sachi says to Yuval, ``One of us is a mentor." Yuval replies to Sachi, ``One of us is a camper." What can you deduce about Yuval?}
\begin{solution}
* * * INSERT PROBLEM 1a SOLUTION HERE * * *
\end{solution}
\item[(b)] \statement{You are a camper and you meet someone named Miranda at camp. What question can you ask Miranda about herself to determine whether she is a JC?}
\begin{solution}
* * * INSERT PROBLEM 1b SOLUTION HERE * * *
\end{solution}
\item[(c)] \statement{Don and Viv are having a conversation as you pass by. Is there a single statement you can overhear from that conversation from which you can deduce that Don and Viv are both in the same group of people (both campers, or both JCs, or both mentors) without giving you any additional information about which group it is?}
\begin{solution}
* * * INSERT PROBLEM 1c SOLUTION HERE * * *
\end{solution}
\end{enumerate}
\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% PROBLEM 2
\section*{Problem 2}
Kai has a collection of magic, shape-changing dice.
When he rolls a blue die, it changes shape to have a number of sides equal to the number rolled minus one. For example, if a blue die starts out with 12 sides, then Kai has an equal probability of rolling any of the twelve integers from 1 through 12. If he rolls an 8, then the blue die changes shape to have 7 sides, and the next roll will have an equal probability of rolling any of the seven integers from 1 through 7. After rolling the same blue die over and over, eventually Kai will roll a 1, at which point the die will disappear.
\begin{enumerate}
\item[(a)] \statement{Suppose the blue die starts with 4 sides (and so it has an equal probability of rolling any of the four integers from 1 through 4). How many rolls, on average, will it take for the die to disappear?}
\begin{solution}
* * * INSERT PROBLEM 2a SOLUTION HERE * * *
\end{solution}
\end{enumerate}
Now Kai is playing a game with Helena. Kai rolls a blue die first (causing it to change shape), then Helena rolls the same blue die (which changes shape again), and then they continue to take turns rolling the same die until one of them rolls a 1. Whoever rolls the 1 loses.
\begin{enumerate}
\item[(b)] \statement{Suppose the blue die starts with 4 sides. What is the probability that Kai wins?}
\begin{solution}
* * * INSERT PROBLEM 2b SOLUTION HERE * * *
\end{solution}
\end{enumerate}
\emph{In parts (c)--(e), write your answer as a function of $N$ and possibly $k$, in closed form: a recurrence relation or a summation is a good start, but not the final answer.}
\begin{enumerate}
\item[(c)] \statement{Suppose the blue die starts with $N$ sides. What is the probability that Kai wins?}
\begin{solution}
* * * INSERT PROBLEM 2c SOLUTION HERE * * *
\end{solution}
\end{enumerate}
Kai also has green dice, which work slightly differently from blue dice. When he rolls a green die, it changes shape to have a number of sides equal to the number rolled (so if Kai rolls the maximum possible value, the green die doesn't change shape at all).
\begin{enumerate}
\item[(d)] \statement{He plays the same game with Helena, but now with an $N$-sided green die; the first player to roll a $1$ still loses. What is the probability that Kai wins?}
\begin{solution}
* * * INSERT PROBLEM 2d SOLUTION HERE * * *
\end{solution}
\item[(e)] \statement{Suppose now that Kai and Helena modify their game: the first person to roll one of the numbers $1, 2, \dots, k$ loses. If they start with an $N$-sided green die, what is the probability that Kai wins?}
\begin{solution}
* * * INSERT PROBLEM 2e SOLUTION HERE * * *
\end{solution}
\end{enumerate}
\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% PROBLEM 3
\section*{Problem 3}
A construction company is designing a new apartment complex. They have an $n \times n$ lot in which each $1 \times 1$ square can either occupy an apartment or a garden. The apartments must all have a scenic view: if an apartment is not on the edge of the apartment complex, then one of the $4$ adjacent lots must have a garden.
\begin{enumerate}
\item[(a)] \statement{What is the minimal number of gardens if $n=6$?}
\begin{solution}
* * * INSERT PROBLEM 3a SOLUTION HERE * * *
\end{solution}
\item[(b)] \statement{Prove that the number of gardens must be at least $\frac15 (n-2)^2$.}
\begin{solution}
* * * INSERT PROBLEM 3b SOLUTION HERE * * *
\end{solution}
\item[(c)] \statement{Prove that it is possible to construct an apartment complex with no more than $\frac15 n^2$ gardens for any $n$.}
\begin{solution}
* * * INSERT PROBLEM 3c SOLUTION HERE * * *
\end{solution}
\item[(d)] \statement{Now suppose that gardens have very tall trees that provide a scenic view to up to $20$ nearby lots. Specifically, if a garden is placed at the center of a $5 \times 5$ square, then every apartment in that square except the four $1\times 1$ corners will have a scenic view of the garden. What upper and lower bounds can you prove on the number of gardens needed?}
\begin{solution}
* * * INSERT PROBLEM 3d SOLUTION HERE * * *
\end{solution}
\end{enumerate}
\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% PROBLEM 4
\section*{Problem 4}
Let $S$ be a set of 8 points in the plane. Call a circle \emph{abundant} if it passes through at least 4 points of $S$.
\begin{enumerate}
\item[(a)] \statement{Show that there can be at most 14 abundant circles.}
\begin{solution}
* * * INSERT PROBLEM 4a SOLUTION HERE * * *
\end{solution}
\item[(b)] \statement{Can there be 14 abundant circles? If not, what is the maximum number possible?}
\begin{solution}
* * * INSERT PROBLEM 4b SOLUTION HERE * * *
\end{solution}
\end{enumerate}
\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% PROBLEM 5
\section*{Problem 5}
A small town has 192 people who want to know whether they have COVID-19. Fortunately, only 2 of them are actually sick. Unfortunately, the town only has enough resources to run 16 tests.
The ambitious scientists of the town have realized that they can combine as many as 32 samples into a single ``pooled sample", which will return a positive result if any of the people in the sample are positive, and will return a negative result if nobody in that sample has COVID-19. For example, pooling 10 people together will clear all 10 if the result is negative, but if the result is positive, not only do you not know who is sick, but even how many of the 10 are.
\begin{enumerate}
\item[(a)] \statement{Can you figure out a way to help them determine which 2 people to quarantine while avoiding quarantining anybody who is healthy? (The tests you do can depend on the results of earlier tests.)}
\begin{solution}
* * * INSERT PROBLEM 5a SOLUTION HERE * * *
\end{solution}
\item[(b)] \statement{A nearby, larger town of $1000$ people wants your help with testing. They also have 2 sick people, and will send over some pooled samples for you to test. However, because they don't have a testing center of their own, they'll need to prepare all the pooled samples at the same time. (The tests you do have to be planned ahead of time, and can't depend on the results of earlier tests.) Find the minimum number of pooled samples needed to identify who is sick, to within a factor of $2$. That is, find an $n$-sample strategy, and prove that $n/2$ samples are not enough, for some value of $n$.}
\begin{solution}
* * * INSERT PROBLEM 5b SOLUTION HERE * * *
\end{solution}
\item[(c)] \statement{A large city hears about your success and wants your help as well. They want to test $10\,000$ people per day, and each person has about a $5\%$ chance of testing positive, although you don't know the exact number on any given day. (They can do their own testing, and don't need to send samples over, so you can base each test on previous results.) Find a strategy to reduce the number of tests that need to be done; it doesn't need to be provably optimal, but do your best. On average, about how many tests will be required?}
\begin{solution}
* * * INSERT PROBLEM 5c SOLUTION HERE * * *
\end{solution}
\end{enumerate}
\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% PROBLEM 6
\section*{Problem 6}
Infinitely many campers line up in a row for a Competitive Hanabi Set (CHS) tournament. Each camper has an unknown, numerical skill level in playing CHS. A more skilled player will always beat a less skilled one, but the game is very subtle; it is impossible to compare skill levels, except in a one-on-one match. We will write $A \prec B$ if camper $A$ loses to camper $B$ in CHS (which means that $A$'s skill level is a lower number than $B$'s). A \emph{subsequence of $n$ campers} is an $n$-tuple of campers $(A_1, A_2, \dots, A_n)$ such that the campers are standing in the infinite row in that order, not necessarily consecutively. ($A_1$ is to the left of $A_2$, who is to the left of $A_3$, and so on.)
\begin{enumerate}
\item[(a)] \statement{You must schedule CHS games between the campers to find a subsequence $(A_1, A_2, A_3)$ of three campers such that either $A_1 \prec A_2 \prec A_3$ or $A_1 \succ A_2 \succ A_3$. You can use the results of each game to schedule the next. How can you minimize the number of games required in the worst case? Prove that your answer is optimal.}
\begin{solution}
* * * INSERT PROBLEM 6a SOLUTION HERE * * *
\end{solution}
\item[(b)] \statement{Now, suppose you want to find either a subsequence $(A_1, A_2, A_3)$ such that $A_1 \prec A_2 \prec A_3$, or a subsequence $(A_1, A_2, \dots, A_n)$ such that $A_1 \succ A_2 \succ \dots \succ A_n$. Show that you can always do this in less than $10n$ games. (As a challenge, how much can you improve this bound?)}
\begin{solution}
* * * INSERT PROBLEM 6b SOLUTION HERE * * *
\end{solution}
\item[(c)] \statement{Next, the campers come together in an unorganized crowd, and decide to hold a Two-Player Castlefall (TPC) competition. TPC is a highly strategic and complex game, so it cannot be reduced to a single skill level: in TPC, it is possible that $A \prec B$ and $B \prec C$, but $A \succ C$. You want to find $n$ campers $A_1, A_2, \dots, A_n$ such that whenever $i < j$, $A_i \prec A_j$. How can you minimize the number of TPC games required in the worst case? We don't know the optimal answer here, so you don't have to prove that your answer is optimal. You should prove that your strategy gives the bound you claim, and you should try to make the bound as small as possible.}
\begin{solution}
* * * INSERT PROBLEM 6c SOLUTION HERE * * *
\end{solution}
\end{enumerate}
\end{document}