\documentclass{article}

\usepackage[varg]{txfonts}
\usepackage{hyperref}
\urlstyle{tt}

\usepackage{geometry}
\geometry{%
  letterpaper,
  lmargin=2cm,
  rmargin=2cm,
  tmargin=2cm,
  bmargin=2cm,
  footskip=12pt,
  headheight=12pt}
  
\usepackage{parskip}

\begin{document}

\section*{Mathcamp 2013 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 need to justify all your assertions and prove to us that your solution is correct. (For some tips on writing proofs, see {\sf \href{http://www.mathcamp.org/proofs}{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.

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 do four or five problems and declare yourself done! The more problems you attempt, the better your chances. The problems are roughly in increasing order of difficulty, but the later problems often have some easier parts. We strongly recommend that you try {\em all} the problems and send us the results of your efforts: partial solutions, conjectures, methods -- everything counts. 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 {\sf \href{http://www.mathcamp.org/computers}{www.mathcamp.org/computers}}.

If you need clarification on a problem, please  email {\sf \href{mailto:quiz13@mathcamp.org}{quiz13@mathcamp.org}}. You may not consult or get help from anyone else. You may 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. Any deviation from these rules will be considered plagiarism and may disqualify you from attending Mathcamp. Read more about our policy on getting help at {\sf \href{http://www.mathcamp.org/honesty}{www.mathcamp.org/honesty}}.

You may handwrite or type your Quiz. For those interested in typing mathematics beautifully, we also offer you the LaTeX source file for the Qualifying Quiz. Please don't let it distract you from solving the problems, though! For more information on LaTeX, take a look at our LaTeX tutorial for The QQ. No matter how you write up your solutions, we require that you upload them with your application as PDF files; visit our PDF tutorial if you need help. (Source code and tutorials can be found at {\sf \href{http://www.mathcamp.org/quiz}{www.mathcamp.org/quiz}}.)

Finally: {\em don't write your name on your Quiz.} (Really!) Instead, write your {\bf applicant ID number} on your quiz. (You will receive an applicant ID number when you start your online application, on the welcome page.) Why not your name? When we grade Quizzes, we want to be thinking just about the math. So we're doing an experiment this year in which we evaluate all applicants just by ID number and then uncover the names later. We appreciate your help with the experiment. 

Good luck and have fun!

\subsection*{The Problems\footnote{Problems 1, 2, and 7 were written by the Mathcamp staff. Problem 5 is folklore. The other problems are due to Mathcamp alumni: Charles Steinhardt, MC'96-'98, Lilly Chin, MC '10-'11 and Aaron Landesman, MC '10-'12 (\#3); Billy Swartworth, MC '11-'12 (\#4); and Zach Abel, MC '03-'04 (\#6). Thanks to all!}}

\begin{enumerate}

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

\item A teacher asks 100 students to help her with a math contest that she's organizing: each student is supposed to come up with one or two problems to include in the contest. All 100 students do as requested, which takes the teacher by surprise: she actually needed only $n$ problems, with $n < 100$, so now she has to decide which problems to use. She announces that she will call on the students one by one, at random, and collect {\em all} the problems from each student she calls on. Once she has $n$ problems, she will stop. (If the last student wrote two problems and the teacher only needs one of them, she'll pick one at random.) 

\begin{enumerate}
\item Angela thought of one problem, Bill thought of two. Bill tells Angela, ``Because I wrote more problems than you, I have a better chance of getting a problem on the contest." Angela says, ``But the teacher is picking people completely at random! My chances of getting picked are as good as yours." Who is right? Does it depend on $n$? Does it depend on how many problems the other students came up with? (Be sure to explain any special cases.)
\item Catherine only thought of one problem, but she overhears Bill talking to Angela and gets worried. She quickly composes another problem, just in case. Does this change her chances of having a problem on the contest? Does it change Bill's or Angela's chances, and if so, in what direction? (Note: you do not need to compute the exact probabilities.)  
\end{enumerate}

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

\item  The subscript $!$ sometimes indicates that a string of numbers is to be interpreted in \emph{factorial base}: the $i$-th number from the right ranges from $0$ to $i$ and tells you what multiple of $i!$ to add. For example, 
$$
20301_! = 2\cdot 5! + 0\cdot 4! + 3\cdot 3!+0\cdot 2!+1\cdot 1! = 240+18+1=259.
$$

\begin{enumerate}
\item Warm-up: show that a number is even if and only if its factorial base representation ends in $0$. State and prove a similar condition for divisibility by $3$.
\item The number $27$ has the property that its binary representation $11011_2$ ends with its factorial base representation $1011_!$. Show that there are infinitely many numbers with this property. 
\end{enumerate}


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

\item  Charles and Lilly are playing a game. They start with an empty pot, to which a piece of candy is automatically added at the beginning of every turn. The player whose turn it is then has a choice: he/she can either take all the candy in the pot or pass. (For instance, if Lilly goes first and takes the pot on her first turn, she gets one piece of candy. If she passes and Charles takes the pot on the next turn, he gets two pieces, etc.) If a player decides to take the pot, he/she must pass on his/her next $k$ turns. The winner is the first player to collect $n$ pieces of candy.\footnote{This is a variant of the online game Reaper (http://www.artofproblemsolving.com/Edutainment/r2). Playing the original version of Reaper will not help you solve this problem, but you can check it out just for fun.}

Charles unwisely offers Lilly the choice of going first or second. Which should she choose in order to be sure of winning, and how should she play? (Her choice may depend on $n$ and/or $k$. You need to describe Lilly's strategy completely and prove that Charles cannot win against it, no matter what he does. We suggest you start with the case $k=1$.)



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

\item A {\em binary block} is a rectangle whose side-lengths are powers of two. 

\begin{enumerate}
\item Show that any $m \times n$ rectangle can be chopped up into binary blocks no two of which are the same. For example, a $5\times 5$ rectangle can be cut into binary blocks of dimensions $4\times 4$, $4 \times 1$, $1 \times 4$, and $1 \times 1$. (Note that a $4\times 1$ block is considered different from a $1 \times 4$ block: rotation is not allowed.)
\item If $m=1$ or $m=2$, show that you get the same set of binary blocks from your $m\times n$ rectangle no matter how you arrange the cuts. (In other words, the set of blocks is uniquely determined by $m$ and $n$ in this case.)
\item On the other hand, if $m=n=5$, there is more than one set of binary blocks that works. Can you demonstrate this?
\item Ideally, we'd like to find a set of rectangular blocks with integer sides (not necessarily powers of two) such that (i) every $m \times n$ rectangle can be cut into blocks from this set that are all different, and (ii) the blocks obtained in this way are uniquely determined by $m$ and $n$. As we just saw, the set of binary blocks satisfies condition (i) but not (ii). Can you find a different set of blocks that satisfies both conditions?
\item (Hard!) Our results in (b) and (c) raise the question: for what values of $m$ and $n$ is the set of binary blocks unique? Try to find a necessary and sufficient condition for uniqueness. (You'll need to prove that if $m$ and $n$ satisfy the condition, uniqueness is guaranteed, whereas if they don't satisfy it, there are at least two different sets of blocks that work. If the general version seems too hard, try for some partial results: are there classes of numbers $m$ and $n$ for which you can prove that there is only one set of binary blocks? Are there classes of numbers for which you can prove that there is more than one?)
\end{enumerate}


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

\item A farmer living on the $xy$-plane wants to fence off a rectangular field with sides parallel to the axes and area at least 1. A malicious king tries to stop the farmer by preemptively placing stakes at infinitely many points in the plane (thereby staking his own claim to those points). It's a constitutional monarchy, so the king can't just claim every point for himself: the law dictates that each point where he places a stake must have a circle of non-zero radius around it that contains no other stakes. (These unclaimed circles around each stake can be of different sizes and can be as small as the king likes.) Can the king place his stakes in such a way that the farmer can't find a rectangle of area 1 with no stakes anywhere in its interior or boundary? 

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

\item Isosceles triangle $ABC$ has $AB=AC$ and $\angle BAC = \alpha$. The
triangle is originally situated in the plane with $A$ at $(0,0)$ and
midpoint $M$ of side $BC$ at $(1,0)$. You are allowed to move the
triangle by reflecting it across any of its edges. Your goal is to
come up with a sequence of moves that switches $A$ and $M$ -- that is, brings $A$ to $(1,0)$ and $M$ to $(0,0)$.

\begin{enumerate}
\item Show that such a switch is impossible if $\alpha=60^\circ$ or $90^\circ$.
\item If $\alpha = 45^\circ$, show that such a switch is still impossible, but that the triangle can come close to its destination: we can simultaneously get $A$ within distance
0.1 of $(1,0)$ and $M$ within distance 0.1 of $(0,0)$. Can we get even closer? How close?
\item Does there exist an angle $\alpha$ for which switching $A$ and $M$ is possible?
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% PROBLEM 7

\item Let $f$ be a function on the nonnegative integers such that $f(2n) = f(f(n))$ and $f(2n+1) = f(2n) + 1$. 

\begin{enumerate}
\item If $f(0)=0$, find a simple formula for $f(n)$.  
\item Show that $f(0)$ cannot equal 1. For what nonnegative integers $k$ (if any) can $f(0)$ equal $2^k$? 
\item For what nonnegative integers $k$ (if any) can $f(0)$ equal $2^k+2$?
\item (Open question!) What else can you say about the possible values of $f(0)$? Are there values of $f(0)$ for which more than one such function exists? If so, how many different functions are there? Partial results are welcome. 
 \end{enumerate}



\end{enumerate}


\end{document}

