\documentclass{article}

\usepackage{amsmath,amsfonts,amssymb}

\usepackage[colorlinks]{hyperref}

\usepackage{tikz,tikzsymbols}

\usepackage{subcaption}

\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}

\begin{document}

\centerline{\Large \bf Mathcamp 2021 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:quiz21@mathcamp.org}{\texttt{quiz21@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{Problem \#5 is due to Charles Steinhardt, MC '96--'98. All other problems were written by the Mathcamp staff.}}

\begin{enumerate}
\item 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:

\begin{itemize}
\item  Mentors always lie to campers. (They say all sorts of bizarre things about so-called ``imaginary numbers" and ``sizes of infinity".)
\item Campers always lie to JCs. (They say things like ``yes, of course I've called my parents today".)
\item JCs always lie to mentors. (They say things like ``of course, I will definitely bring you some chalk".) 
\end{itemize}

Except for these three cases, everyone always tells the truth. The information in this problem is common knowledge at Mathcamp; you can also assume that whenever anyone makes a statement to anyone else, they know the category of the person they're talking to.

\begin{enumerate}
\item[(a)] Sachi and Yuval have a conversation. Sachi says to Yuval, ``At least one of us is a mentor." Yuval replies to Sachi, ``At least one of us is a camper." What can you deduce about Yuval?

\item[(b)] 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?

\item[(c)] 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?
\end{enumerate}

\item 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)] 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?
\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)] Suppose the blue die starts with 4 sides. What is the probability that Kai wins?

\item[(c)] Suppose the blue die starts with $N$ sides. What is the probability that Kai wins?
\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)] 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?
\item[(e)] 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? 
\end{enumerate}
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.

\item 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. For reference, consider the first two diagrams below: diagram~(i) shows a valid design, while the design in diagram~(ii) has one apartment without a scenic view.

\newcommand{\happy}[1]{\Smiley[#1][yellow]}
\newcommand{\sad}[1]{\Sadey[#1][red]}
\newcommand{\tree}[1]{\BasicTree[#1]{green!20!black}{green!50!black}{green!70!black}{leaf}}
\renewcommand\thesubfigure{\roman{subfigure}}

\begin{figure*}[h!]
\centering
\begin{subfigure}[t]{0.3\textwidth}
\centering
\begin{tikzpicture}
\path [fill, green!70!black] (-.5,-.5) rectangle (4.5,4.5);
\path [fill, white] (0,0) rectangle (4,4);
\foreach\i in {0,...,3} \foreach\j in {0,...,3}
\path (\i,\j) ++(0.5,0.5) node {\happy2};
\path [fill, white] (1,2) rectangle +(1,1) ++(.5,.5) node {\tree2};
\path [fill, white] (2,1) rectangle +(1,1) ++(.5,.5) node {\tree2};
\draw (0,0) grid (4,4);
\end{tikzpicture}
\caption{A valid $4 \times 4$ design}
\end{subfigure}%
~
\begin{subfigure}[t]{0.3\textwidth}
\centering
\begin{tikzpicture}
\path [fill, green!70!black] (-.5,-.5) rectangle (4.5,4.5);
\path [fill, white] (0,0) rectangle (4,4);
\foreach\i in {0,...,3} \foreach\j in {0,...,3}
  \path (\i,\j) ++(0.5,0.5) node {\happy2};
\path [fill, white] (2,2) rectangle +(1,1) ++(.5,.5) node {\tree2};
\path [fill, white] (1,1) rectangle +(1,1) ++(.5,.5) node [black] {\sad2};  
\draw (0,0) grid (4,4);
\end{tikzpicture}
\caption{An invalid design}
\end{subfigure}%
~
\begin{subfigure}[t]{0.3\textwidth}
\centering
\begin{tikzpicture}[scale=5/9]
\path [fill, green!70!black] (-.5,-.5) rectangle (8.5,8.5);
\path [fill, white] (0,0) rectangle (8,8);
\foreach\i in {0,...,7} \foreach\j in {0,...,7}
  \path (\i,\j) ++(0.5,0.5) node {\happy{1.2}};
\path [fill, white] (4,2) rectangle +(1,1) ++(.5,.5) node {\tree{1.5}};
\foreach\i in {1,...,6}
  \path [fill, white] (1,\i) rectangle +(1,1) ++(.5,.5) node [black] {\sad{1.2}};  
\foreach\i in {4,...,6}
  \path [fill, white] (2,\i) rectangle +(1,1) ++(.5,.5) node [black] {\sad{1.2}};  
\foreach\i in {5,...,6}
  \path [fill, white] (3,\i) rectangle +(1,1) ++(.5,.5) node [black] {\sad{1.2}};  
\foreach\i in {5,...,6}
  \path [fill, white] (4,\i) rectangle +(1,1) ++(.5,.5) node [black] {\sad{1.2}};  
\foreach\i in {5,...,6}
  \path [fill, white] (5,\i) rectangle +(1,1) ++(.5,.5) node [black] {\sad{1.2}};  
\foreach\i in {4,...,6}
\path [fill, white] (6,\i) rectangle +(1,1) ++(.5,.5) node [black] {\sad{1.2}};  
\draw (0,0) grid (8,8);
\end{tikzpicture}
\caption{Variant in part (d)}
\end{subfigure}
\end{figure*}

\begin{enumerate}
\item[(a)] What is the minimal number of gardens if $n=6$?

\item[(b)] Prove that the number of gardens must be at least $\frac15 (n-2)^2$.

\item[(c)] Prove that it is possible to construct an apartment complex with no more than $\frac15 n^2$ gardens for any $n$.

\item[(d)] 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. An example of this is shown in diagram~(iii) above.

What upper and lower bounds can you prove on the number of gardens needed? 
\end{enumerate}

\item  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)] Show that there can be at most 14 abundant circles.

\item[(b)] Can there be 14 abundant circles? If not, what is the maximum number possible?
\end{enumerate}

If you find it hard to think about $14$ circles at once, there's a trick. A technique called circle inversion can transform circles and lines into other circles and lines; if applied carefully, it can simplify difficult geometry problems. If you have not encountered this technique before, you may find \href{https://www.mathcamp.org/static/yearly/2021/quiz/inversion.pdf}{our handout on inversion} helpful.

\item 
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)] 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.)

\item[(b)] 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$.

\item[(c)] 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?

\end{enumerate}

\item 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)] 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.

\item[(b)] 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?)

\item[(c)] 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.
\end{enumerate}
\end{enumerate}
\end{document}
