\documentclass[11pt]{article}

\usepackage{amsmath,amsfonts,amssymb}

\usepackage[colorlinks]{hyperref}

\usepackage{graphicx}

\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 2023 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 of the problems, please email the Quiz committee at 
\href{mailto:quiz23@mathcamp.org}{\texttt{quiz23@mathcamp.org}}. We almost always reply within 24 hours, usually much sooner. In addition to replying to your email: if we see the same clarification question several times, we will post the answer at \href{https://www.mathcamp.org/qualifying_quiz/faq_answers/}{\texttt{www.mathcamp.org/qqFAQ}}.

You may not consult or get help from anyone else on any aspect of the Qualifying Quiz. To be safe, we ask that you don't even discuss the problems with other people in a general way (``Wow, \#7 was really tricky!'') until the official discussion of solutions begins (typically several weeks after the application deadline). If someone else uses ideas from your solution to cheat, we will hold both of you responsible.

While other people are completely off limits, you are welcome (in fact, encouraged) to use books or the Web to look up definitions, formulas, etc. Any information obtained from such sources must be clearly referenced in your solution, in a way that would make it easy for us to look up the exact source if we wanted to. But 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. If in doubt about what is allowed, please ask! 

{\em Any deviation from these rules will be considered plagiarism and may disqualify you from attending Mathcamp.}

\subsection*{The Problems\footnote{All problem were written by the Mathcamp staff. }}



\begin{enumerate}

%Problem 1
\item 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.)

%Problem 2
\item
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 below.
\begin{center}
\includegraphics[width=0.65\textwidth]{bizarro-billiards.pdf}
\end{center}

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

\item 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?

\item 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.
\end{enumerate}

%Problem 3
\item
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 Prove that you can eventually find a set of coins that weighs exactly X grams.

\item Prove that you can find such a set in at most 10000 weighings. 
\end{enumerate}

\vfill\eject
%Problem 4
\item
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 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? 


\item 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? 


\item 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.)}
\end{enumerate}


%Problem 5
\item
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 
For each $n$, who wins?
\item \label{symmetric}
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?
\item Same as (b), but the players are considered distinct (so $N=1$, $T=3$ isn't a repetition of $N=3$, $T=1$).
\end{enumerate}

\vfill\eject

%Problem 6
\item
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 Prove that one million boards aren't enough.
\item Give a specific number of boards with which you can reach $(2023, 2023)$.
\item Prove that one billion boards aren't enough. 
\end{enumerate}


\end{enumerate}
\end{document}