\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
\usepackage{subcaption} % allows subfigures

%% 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 2023 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 2023 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. * * *

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% PROBLEM 1

\section*{Problem 1}

You have a funny calculator with only two buttons: $+1$ and $\times 2$. The first button adds $1$ to the current number, the second multiplies it by $2$. 
For each nonnegative integer $n$,
what is the shortest sequence of buttons that will get you from $0$ to $n$?
(As with all problems on the Qualifying Quiz, make sure to justify your answer with a proof.)

\begin{solution}
* * *  INSERT PROBLEM 1a SOLUTION HERE * * *
\end{solution}

\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% PROBLEM 2

\section*{Problem 2}

Ordinarily, when an object bounces off of a surface --- whether it's light reflecting from a mirror or a billiard ball bouncing off the side of a billiards table --- its path makes the same angle with the surface before and after the bounce. However, a Bizarro Billiards table behaves differently.

The table is a rectangle with two horizontal and two vertical sides in the $x$--$y$ plane. The rule that determines how balls bounce is:

\begin{itemize}
\item If the ball is moving up and right along a line with slope $1$, and it hits the top side of the table, it bounces off and continues moving down and right along a line with slope $-1/2$.
\item If the ball is moving up and right along a line with slope $2$, and it hits the top side of the table, it bounces off and continues moving down and right along a line with slope $-1$.
\item These two bounces are reversible: if the ball is moving up and left along a line with slope $-1/2$ or $-1$, it bounces off and continues moving down and left along a line with slope $1$ or slope $2$, respectively.
\item When the ball is bouncing off another side of the table, the rule for bouncing is the same as it would be if you rotated the table to make that side the top side.
\end{itemize}

This rule is summarized in the diagram on the next page.
\begin{center}
\includegraphics[width=0.65\textwidth]{bizarro-billiards.pdf}
\end{center}
\begin{enumerate}

\item[(a)] Suppose that the ball starts in the top left corner (point $B$) moving down and right along a line with slope $-1$. If the ball hits side $AD$ and bounces off, then hits side $BC$ and bounces off, and then ends up at corner $D$, what must the proportions of the rectangle be?

\begin{solution}
* * *  INSERT PROBLEM 2a SOLUTION HERE * * *
\end{solution}

\item[(b)] Suppose that the ball starts in the bottom left corner (point $A$) moving up and right along a line with slope $1$. If the ball hits side $BC$ and bounces off, then hits side $CD$ and bounces off, then hits side $AD$ and bounces off, and then ends up at corner $B$, what must the proportions of the rectangle be?

\begin{solution}
* * *  INSERT PROBLEM 2b SOLUTION HERE * * *
\end{solution}

\item[(c)] Suppose that the rectangle has height $AB = 3$ and width $BC = 5$, and the ball starts in the bottom left corner (point $A$) moving up and right along a line with slope $1$. Describe the trajectory that the ball takes.

\begin{solution}
* * *  INSERT PROBLEM 2c SOLUTION HERE * * *
\end{solution}

\end{enumerate}

\newpage


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% PROBLEM 3

\section*{Problem 3} 

You have $4046$ identical-looking coins, but $2023$ of them weigh $1$ gram each, while the other $2023$ coins weigh $2$ grams each. You cannot distinguish these coins in any way manually. However, you have a partially-working scale, tuned to some
unknown integer value $X$: when you weigh a set of coins, the scale reports if the weight is ``less than $X$ grams'' or ``at least $X$ grams''.  You know that
$1 < X < 6070$.

\begin{enumerate}

\item[(a)] Prove that you can eventually find a set of coins that weighs exactly X grams.

\begin{solution}
* * *  INSERT PROBLEM 3a SOLUTION HERE * * *
\end{solution}

\item[(b)] Prove that you can find such a set in at most 10000 weighings. 

\begin{solution}
* * *  INSERT PROBLEM 3b SOLUTION HERE * * *
\end{solution}

\end{enumerate}

\newpage


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% PROBLEM 4

\section*{Problem 4}

You are exploring the maze below. The red and blue doors are locked, but you know that there is a Red Key in a treasure chest in one of the rooms, and a Blue Key in a different treasure chest.  Once you have the Red Key, you can open all of the red doors. Likewise, once you have the Blue Key, you can open all of the blue doors. 

\centerline{\includegraphics[scale=0.4]{game-level.png}}
\begin{enumerate}

\item[(a)] If I chose two random treasure chests to put the keys in, most likely you will not be able to get to them. Suppose I choose randomly from only the \emph{valid} assignments: those in which you can get to all of the treasure chests. What is the probability that the Red Key will be in the first treasure chest you open? 

\begin{solution}
* * *  INSERT PROBLEM 4a SOLUTION HERE * * *
\end{solution}

\item[(b)] Suppose I choose a random key, and put it in a random treasure chest that you can get to. Then I repeat with the other key, but allow it to be placed in any other treasure chest that you can get to \emph{after} picking up the first key I placed.  What is the probability that the Red Key will be in the first treasure chest you open? 

\begin{solution}
* * *  INSERT PROBLEM 4b SOLUTION HERE * * *
\end{solution}

\item[(c)] The two methods from (a) and (b) give different probabilities, but they're very close together. Can you draw a different map in which the method of (a) gives a probability of picking up the Red Key from the first chest you open of less than 1\%, but the method of (b) gives a probability more than 99\%?  Your map may have any number of doors, treasure chests, and colors --- but no other types of obstacle, and only one key of each color.

\textit{(To generalize the method from (b), I place the keys in random order, and place the $k^{\text{th}}$ key in an empty treasure chest you can get to if you have the first $k-1$ keys. If all the treasure chests you can get to are full when I try to place the $k^{\text{th}}$ key, I take back all the keys placed and start over, once again randomly choosing an order for the keys.)}

\begin{solution}
* * *  INSERT PROBLEM 4c SOLUTION HERE * * *
\end{solution}

\end{enumerate}

\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% PROBLEM 5

\section*{Problem 5}

Narmada and Travis are playing a game in turns; Narmada goes first.
Each player stands on their own number line, which has spaces numbered
$1$ through $n$ for some integer $n \ge 3$.
Narmada starts at position $1$ on her number line, and Travis starts at position $n$ on his.
On each player's turn, that player must move to another number on their number line.  (The new number need not be adjacent to the old one.) 
But no repetitions are allowed in the pair
of positions: if Narmada moves back to position $1$, then Travis cannot move back to position $n$
on his next move, because the ordered pair $(1,n)$ has already occurred.
The first player who cannot move loses. Assume both players play optimally.
\begin{enumerate}

\item[(a)] For each $n$, who wins?

\begin{solution}
* * *  INSERT PROBLEM 5a SOLUTION HERE * * *
\end{solution}

\item[(b)] Now suppose they are on the same number line, and cannot simultaneously occupy the same spot. (So if Narmada is at $1$ and Travis is at $3$, Narmada can move to $2, 4, 5, \dotsc, n$ but not $1$ or $3$.) Furthermore, a position is considered the same if the same spots are occupied (so $N=1$, $T=3$ is a repetition of $N=3$, $T=1$). For each $n$, who wins?

\begin{solution}
* * *  INSERT PROBLEM 5b SOLUTION HERE * * *
\end{solution}

\item[(c)] Same as (b), but the players are considered distinct (so $N=1$, $T=3$ isn’t a repetition of $N=3$, $T=1$).

\begin{solution}
* * *  INSERT PROBLEM 5c SOLUTION HERE * * *
\end{solution}

\end{enumerate}

\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% PROBLEM 6

\section*{Problem 6}

The first quadrant is lava. The rest of the plane (including the $x$ and $y$ axes)
is safe.
To traverse the lava, you can place a board, which is a line segment of length at most
$1$, between two safe endpoints.  Once a board is placed, the line
segment becomes safe,
and points on it may be used as endpoints of a subsequent board.

Your goal is to reach
the point $(2023, 2023)$.

\begin{enumerate}

\item[(a)] Prove that one million boards aren't enough.

\begin{solution}
* * *  INSERT PROBLEM 6a SOLUTION HERE * * *
\end{solution}

\item[(b)] Give a specific number of boards with which you can reach $(2023, 2023)$.

\begin{solution}
* * *  INSERT PROBLEM 6b SOLUTION HERE * * *
\end{solution}

\item[(c)] Prove that one billion boards aren't enough. 

\begin{solution}
* * *  INSERT PROBLEM 6c SOLUTION HERE * * *
\end{solution}

\end{enumerate} 

\end{document}
