\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=1.5cm,
  rmargin=1.5cm,
  tmargin=2cm,
  bmargin=2cm,
  footskip=12pt,
  headheight=12pt}
  
  
\usepackage[parfill]{parskip}
\newcommand{\ATAN}{\operatorname{TAN}^{-1}}
\DeclareMathOperator{\COS}{COS}
  
\usepackage{lastpage}
\usepackage{fancyhdr}
\pagestyle{fancy}
\headheight 35pt

\rhead{Applicant ID:  * * INSERT YOUR APPLICANT ID HERE  * *}
\lhead{Mathcamp 2020 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}}


\def\a{{\alpha}}
\def\b{{\beta}}
\def\g{{\gamma}}
                      
\begin{document}

\thispagestyle{empty}

\begin{center}\section*{Mathcamp 2020 Qualifying Quiz Solutions}

Applicant ID:   * * APPLICATION ID HERE (You can find this in your online application.)  * *\end{center}

\subsection*{References}   * * * LIST ANY REFERENCES USED HERE.  CITE AS APPROPRIATE IN THE SOLUTIONS. * * *

\subsection*{Solutions}

\begin{enumerate}

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

\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!)

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

\item For which $n$ can it be done, and for which $n$ is it impossible? Prove your answer.
\begin{solution}
* * *  INSERT PROBLEM 1b SOLUTION HERE * * *
\end{solution}

\end{enumerate}

\newpage


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

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

(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}}).)

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


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

\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? 
\begin{solution}
* * *  INSERT PROBLEM 2b SOLUTION HERE * * *
\end{solution}

\end{enumerate}

\newpage


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

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

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

\item Find the set of possible values of $a-b$, without the extra assumption.
\begin{solution}
* * *  INSERT PROBLEM 3b SOLUTION HERE * * *
\end{solution}

\end{enumerate}

\newpage


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

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

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

\newpage

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

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

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.

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

\item What is the average head length of a permutation of $[1, 1, 2, 3, \dotsc, n]$?
\begin{solution}
* * *  INSERT PROBLEM 5b SOLUTION HERE * * *
\end{solution}

\item What is the average head length of a sequence of length $n$ consisting of the numbers $\{1,2,3,4\}$?

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

\end{enumerate}

\newpage

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

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

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

\item What is the maximal possible length of Harini's sequence of equations?
\begin{solution}
* * *  INSERT PROBLEM 6b SOLUTION HERE * * *
\end{solution}

\end{enumerate}

\end{enumerate}

\end{document}
