\documentclass{article}
\usepackage{amsmath,amsfonts,amssymb}

\usepackage{diagbox}
\usepackage[colorlinks]{hyperref}

\usepackage{graphicx,caption,subcaption}

\usepackage{tikz}

\usepackage{url}
\urlstyle{tt}

\usepackage{geometry}
\geometry{%
 letterpaper,
 lmargin=2cm,
 rmargin=2cm,
 tmargin=2.3cm,
 bmargin=2.3cm,
 footskip=12pt,
 headheight=12pt}
 
\pagenumbering{gobble}
 
\usepackage[parfill]{parskip}

\begin{document}

\centerline{\LARGE \bf Mathcamp 2020 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{https://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{https://www.mathcamp.org/computers}{\texttt{www.mathcamp.org/computers}}.


\subsection*{Getting Help [PLEASE READ THIS!]}

If you need clarification on any of the problems, please email \href{mailto:quiz20@mathcamp.org}{\texttt{quiz20@mathcamp.org}}. We almost always reply within 24 hours, usually much sooner. 

{\bf 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 \href{https://www.mathcamp.org/qualifying_quiz/solutions/}{official discussion of solutions} begins. (Note that this is considerably after the application deadline! We appreciate your patience.) 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, standard techniques, etc. (One underappreciated source of mathematical awesomeness that we love pointing students to: \href{https://oeis.org}{\texttt{oeis.org}}.) 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 permanently disqualify you from attending Mathcamp.}

% \newpage

\subsection*{The Problems\footnote{Problem \#4 is due to Alvin Chen, MC '18--'19. Problem \#5 is due to Sean Li, MC '18. All other problems were written by the Mathcamp staff.}}


\begin{enumerate}

\item Caitlin wants to draw $n$ straight line segments, without lifting her pencil off the paper and without retracing her path, so that each segment crosses exactly one other segment (not counting intersections at vertices) and she ends up back where she started.

\begin{enumerate}
\item Show how she can do this for $n=6$. (Draw a picture!)
\item For which $n$ can it be done, and for which $n$ is it impossible? Prove your answer.
\end{enumerate}

\newpage

\item 
Here is a table of remainders when powers of $10$ are divided by $2020$:
\begin{center}
\begin{tabular}{rrr}
$k$ & $10^k$ & Remainder \\ \hline
$0$ & $1$ & $1$ \\
$1$ & $10$ & $10$ \\
$2$ & $100$ & $100$ \\
$3$ & $1000$ & $1000$ \\
$4$ & $10000$ & $1920$ \\
$5$ & $100000$ & $1020$ \\
$6$ & $1000000$ & $100$ \\
$7$ & $10000000$ & $1000$ \\
$8$ & $100000000$ & $1920$ \\
$9$ & $1000000000$ & $1020$
\end{tabular}
\end{center}
We see that the remainders repeat every four steps (period 4), with two exceptions at the
beginning, $1$ and $10$. We will call a sequence that repeats with period 4, with two
exceptions at the beginning, a {\em fortuitous sequence} (four-two-itous). Sequences that have
periods smaller than four (e.g. sequences that repeat every two steps) do not count as fortuitous.

\begin{enumerate}
\item In addition to 2020, for what other values of $m$ is the sequence of remainders when $10^k$ is divided by $m$ a fortuitous sequence?

\item In addition to 10, for what other values of $a$ is the sequence of remainders when $a^k$ is divided by 2020 a fortuitous sequence? 
%\item What can you say about the general problem? What pairs $(a, m)$ give rise
%to a fortuitous sequence when we look at the remainders when $a^k$ is divided
%by $m$? 
\end{enumerate}
You might find it helpful to look up the Chinese Remainder Theorem (for instance, at %\url{www.cut-the-knot.org/blue/chinese.shtml}
\href{https://www.cut-the-knot.org/blue/chinese.shtml}{\texttt{www.cut-the-knot. org/blue/chinese.shtml}}).



\item An island has two cities: Mathopolis and Campville. There are three roads connecting the cities: Red Road, Green Road, and Blue Road. The roads can intersect each other, but only at right angles. Also, no road intersects itself. (Unlike in the example below, roads don't always go left to right -- they can loop around and cross however they want, obeying the restrictions.) All along each road, there are signposts indicating the direction to Campville.

There are six types of intersections, which we divide into two groups:

\begin{center}
\includegraphics[width=3in]{three-roads.pdf}
\end{center}

Note that each group has a red-green intersection, a red-blue intersections, and a blue-green intersection. The intersections in the two groups are mirror images of each other.


In the example below, the red-blue crossing belongs to
group A, and the red-green and green-blue crossings belong to group B.
\begin{center}
\includegraphics[height=1in]{three-roads-2.pdf}
\end{center}

Let $a$ be the number of intersections in Group A, and $b$ the number in Group B.

\begin{enumerate}
\item Find, with proof, the set of possible values of $a - b$ under the
assumption that Red Road does not intersect Green Road.
\item Find the set of possible values of $a-b$, without the extra assumption.
\end{enumerate}

{\em Note:} This is one of those problems where you might quickly get the right idea but then struggle to write it down. Keep trying! If all you have is a vague, wordy, handwavy explanation, then you're not done with the problem: you haven't found the right way of thinking about it yet, haven't discovered its true essence. Once you do, the long, wordy explanation will suddenly transform into a clear, step-by-step, logical argument. 

(That said, any explanation is better than none; do the best you can, and send us what you have.)


\item Mathematical Chunks of Sentient Protoplasm (MCSPs, for short) are smart blobs who dream of merging together into one huge blob. But they can only do it following certain rules:

\begin{itemize}
 \item If two MCSPs have the same mass, or if their masses are $1$ apart, they can merge into a single MCSP, whose mass will be the sum of the original two.

 \item If an MCSP has even mass, it can split into two MCSPs, each with half the original mass.
\end{itemize} 

Suppose we start with $n$ MCSPs, with masses $1$ through $n$. For what values of $n$ is there a finite sequence of steps that will allow all $n$ MCSPs to merge together into a single MCSP and achieve their dream of unity?


\item Given a sequence of numbers, its \emph{head length} is the largest integer $m$ for which the first $m$ terms are
nondecreasing. For instance, the head length of $[1,1,2,4,3]$ is $4$.
Thus, we can compute the average head length for any set of sequences. For example, we can evaluate the head lengths for all six permutations of the sequence $[1,2,3]$:

\begin{itemize}
\item $[2,1,3]$, $[3,1,2]$, and $[3,2,1]$ each have head length $1$,
\item $[1,3,2]$ and $[2,3,1]$ have head length $2$, and
\item $[1,2,3]$ has head length $3$. 
\end{itemize}
Thus, a permutation of $[1,2,3]$ has average head length $(1+1+1+2+2+3)/6 = 5/3$.

Let $n$ be a positive integer.
\begin{enumerate}
\item Consider all the permutations of $[1,2,\dotsc,n]$.
\begin{enumerate}
	\item What fraction of them has head length $1$?
	\item What fraction of them has head length $k$, for $k<n$?
	\item What is the average head length of a permutation of $[1, 2, \dotsc, n]$?
\end{enumerate}	
\item What is the average head length of a permutation of $[1, 1, 2, 3, \dotsc, n]$?
\item What is the average head length of a sequence of length $n$ consisting of the numbers $\{1,2,3,4\}$?
\end{enumerate}

In each case, please express your answer as an explicit (rather than recursive) formula in terms of $n$.
You may use sigma notation in your answers.

\item Harini loves solving quadratic equations, but only if they have real roots. She starts with an equation 
$$
x^2+p_1x+q_1=0,
$$ 
with $p_1, q_1$ not both 0. If the equation has two real roots, Harini uses them to create a new quadratic equation, 
$$
x^2+p_2x+q_2 = 0,
$$ 
using the smaller of the two roots as $p_2$ and the larger one as $q_2$. For instance, if Harini's first equation was $x^2+2x-3 = 0$, which has roots $-3$ and $1$, then her second equation would be $x^2-3x+1=0$.


She keeps going in this way: at each step $n$, if the equation 
$$
x^2+p_n x+q_n=0
$$ 
has two real roots, Harini uses them as the coefficients of the next equation, 
$$
x^2+p_{n+1} x+q_{n+1}=0,
$$ 
always with the smaller root as $p_{n+1}$ and the larger root as $q_{n+1}$. (A repeated root counts as two equal roots, in which case $p_{n+1} = q_{n+1}$.) She stops when she gets to an equation that does not have real roots.
 
\begin{enumerate}
\item Prove that this process cannot continue forever.
\item What is the maximal possible length of Harini's sequence of equations?
\end{enumerate}
\end{enumerate}
\end{document}
