\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
\usepackage{tikz}       % creates diagrams
\usepackage{hyperref}   % web links
\hypersetup{colorlinks=true, urlcolor=blue}

%% 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 2025 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 2025 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}

A number is a {\em palindrome} if it reads the same backwards and forwards. For instance, 14541 is a palindrome, whereas 321 and 6560 are not. (Note that you can't write 6560 as 06560 to make it into a palindrome: zero is not a valid leading digit.)

Is it possible to write 2025 as a ratio of two palindromes? What about 2026?

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

\newpage

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

\section*{Problem 2}

Angela has just landed in the city of Metropolis. Her plan is to take the subway from the Airport station to the Museum station. Angela knows the following facts about the Metropolis subway system:

\begin{itemize}
    \item It has 15 lines, all of which are straight.

    \item Every pair of subway lines intersects. Where they meet, there's an interchange station where you can switch from one line to the other.

    \item Each station is the interchange station between exactly two different lines. (No three lines meet at the same station.)

    \item A ride of $n$ stops costs $n$ subway tokens. (So if $A$ and $B$ are consecutive stations, riding between them costs one token.) Switching lines doesn't cost extra. 
\end{itemize}

Unfortunately, Angela forgot to look up how far the Museum station is from the Airport station, and she has to buy tokens before she can consult a subway map.  

\begin{enumerate}

\item[(a)] What is the smallest number of tokens Angela can buy to guarantee that she can get from the airport to the museum? (She'll have access to a map once she buys the tokens, so she'll be able to take the actual cheapest route.)

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

\item[(b)] {\em Extra credit:} What if Angela cannot assume that all the subway lines are straight? (We do not have a complete answer to this question, but we're curious what you can come up with.) 

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

\end{enumerate}

\newpage


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

\section*{Problem 3} 

This problem is about perfect binary trees.  The first few
examples of perfect binary trees are shown below.
\begin{center}
\begin{tabular}{|c|c|}
\hline & \\
\includegraphics{trees/tree_0.pdf} & \includegraphics{trees/tree_1.pdf} \\
Height 0 & Height 1 \\ \hline & \\
\includegraphics{trees/tree_2.pdf} & \includegraphics{trees/tree_3.pdf} \\
Height 2 & Height 3 \\ \hline
\end{tabular}
\end{center}
In general, a \emph{perfect binary tree of height $n$} consists of $n+1$ rows of
nodes (which are depicted as circles in the above figure).
The top row has one node, called the {\em root}, and each subsequent row has twice
as many nodes as the previous row. The $2^n$ nodes in the bottom row are called the \emph{leaves}.
Each node except the root is connected by an edge to one
node in the row above it, and each node that is not a leaf is connected by an edge to two nodes in the row below it. 


We can {\em shuffle} a perfect binary tree
by deciding, for each non-leaf node, whether to switch the
left and right branches coming out of that node. For example, in the
diagram below, the tree on the right can be obtained from the tree on
the left via a shuffle in which we switch the left and right branches
from the nodes marked in red.
\begin{center}
\includegraphics{trees/tree_3_marked.pdf}~~~~\includegraphics{trees/tree_3_ordered.pdf}
\end{center}

Suppose the leaves of our tree are labeled with some permutation of the numbers $1$ to $2^n$, and we shuffle the tree to get as many leaf nodes as possible into the ``correct'' position (where the node's label corresponds to the node's number starting from the left). For example, our diagram shows that if $n=3$ and the starting permutation is 56873421, we can get all the leaf nodes into the correct position by shuffling. On the other hand, if the starting permutation is 18234567, we can't get all the leaf nodes into the correct position, since 1 and 8 would still be neighbors under any shuffle.

In the worst case scenario, for a perfect binary tree of height $n$, how many of the $2^n$ leaf nodes can you get into the correct position by shuffling? (Note: If your answer is $X$, then you need to prove two things: (1) for any starting permutation, you can always get at least $X$ nodes into the correct position by shuffling; (2) there are starting permutations for which you cannot get more than $X$ nodes into the correct position by shuffling.)

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

\newpage


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

\section*{Problem 4}

A {\em crescent} is a pentagon with five sides of equal length and internal angles $108^\circ$-$36^\circ$-$252^\circ$-$36^\circ$-$108^\circ$. This is just like a regular pentagon, but with one of the corners ``caved in":

\begin{center}
\includegraphics[width = 1.5in]{crescent.png}
\end{center}

\begin{enumerate}
\item[(a)] Show that it is possible to make a 12-sided polyhedron each of whose faces is a crescent. 

(You might find it helpful and/or fun to make a paper model; if so, we'd love to see a photo! However, a model is not a proof: you still need to show that all the lengths and angles work out precisely. One way to do this is to specify the coordinates of the vertices, and then check everything that needs to be checked. We suggest centering your polyhedron at $(0,0,0)$ to take advantage of symmetry.)

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

\item[(b)] A {\em net} for a polyhedron is a connected arrangement of polygons in the plane that can be folded along a subset of the edges to create the polyhedron. For example, here are a few possible nets for a cube:

\begin{center}
\includegraphics[width = 3in]{cube nets.png}
\end{center}

Is it possible to make a net for the polyhedron that you constructed in part (a)? Keep in mind that the twelve crescents forming the net are not allowed to overlap (except at the edges).

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

\end{enumerate}

\newpage

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

\section*{Problem 5}

The state of Infiana is an infinite plane of farmland, subdivided into an infinite square grid of 1 km $\times$ 1 km plots of land. A finite number of farmers (at least two) each own infinite territory in Infiana, with each $1\times 1$ plot belonging to exactly
one farmer. The plots that each farmer owns are connected by orthogonal adjacency; in other words, any two points belonging to the same farmer can be connected by a road that lies within that farmer's territory and that does not pass through a vertex of a $1\times1$ plot along the way.

A farmer may split their territory into two fields by building a fence along the gridlines, all within their own territory. The laws of Infiana dictate that the fence must be of finite length, but the resulting fields must still have infinite area. Each field can then be further subdivided into more fields. 

\begin{enumerate}

\item [(a)] For each positive integer $n$, give an example of a territory that can be split into $n$ pieces but no more.

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

\item[(b)] Prove that no territory can be broken up into infinitely many pieces.

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

\item[(c)] Prove that there are always at least two farmers who cannot split their territory at all.

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

\end{enumerate}


\newpage

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

\section*{Problem 6}

The \emph{Hilbert Curve} is a famous example of a space-filling curve. (You can read all about it on \href{https://en.wikipedia.org/wiki/Hilbert_curve}{Wikipedia}, though you don't need any of that information to solve this problem.) Inspired by the Hilbert curve, Misha decides to build an infinite running track of the same shape. Instead of making the segments smaller and smaller so that the whole thing fits inside a $1\times 1$ square, he makes all the segments 1 meter long and allows the track to extend over the entire first quadrant of the plane. 

The track is constructed in stages, as follows:

\begin{itemize}
    \item The initial stage $H_0$ starts at $(0,0)$ and covers the bottom left $1 \times 1$ square of the first quadrant. It consists of three segments in a $U$-shape:
\begin{center}
\begin{tikzpicture}
\draw[dashed] (-1,-1) rectangle (1,1);
\node at (0,0) {$H_0$};
\node at (2,0) {$=$};
\draw[very thick] (3,-1)--(3,1)--(5,1)--(5,-1);
\end{tikzpicture}
\end{center}
\item For each positive integer $n$, the stage $H_n$ starts at $(0,0)$ and covers the bottom left $(2^{n+1}-1) \times (2^{n+1}-1)$ square of the first quadrant. It begins with $H_{n-1}$, then continues with three rotated or reflected copies of $H_{n-1}$ joined together with line segments of length $1$, as shown below:
\begin{center}
\begin{tikzpicture}[every text node part/.style={align=center}]
\node at (-2.5,1.5) {$n$ odd:};
\draw[dashed] (-1,-1) rectangle (1,1);
\node at (0,0) {$H_{n-1}$ \\ (original)};
\draw[dashed] (2,-1) rectangle (4,1);
\node[rotate=270] at (3,0) {$H_{n-1}$ \\ (copy)};
\draw[dashed] (2,2) rectangle (4,4);
\node[rotate=270] at (3,3) {$H_{n-1}$ \\ (copy)};
\draw[dashed] (-1,2) rectangle (1,4);
\node[rotate=180] at (0,3) {$H_{n-1}$ \\ (copy)};
\draw[very thick] (1,-1)--(2,-1);
\draw[very thick] (2,1)--(2,2);
\draw[very thick] (2,4)--(1,4);
\node at (4.5,1.5) {$=$};
\draw[dashed] (5,-1) rectangle (10,4);
\node[rotate=270] at (7.5,1.5) {$H_{n}$};
\end{tikzpicture}
\\~\\
\begin{tikzpicture}[every text node part/.style={align=center}]
\node at (-2.5,1.5) {$n$ even:};
\draw[dashed] (-1,-1) rectangle (1,1);
\node[rotate=270] at (0,0) {$H_{n-1}$ \\ (original)};
\draw[dashed] (2,-1) rectangle (4,1);
\node[rotate=90] at (3,0) {$H_{n-1}$ \\ (copy)};
\draw[dashed] (2,2) rectangle (4,4);
\node at (3,3) {$H_{n-1}$ \\ (copy)};
\draw[dashed] (-1,2) rectangle (1,4);
\node at (0,3) {$H_{n-1}$ \\ (copy)};
\draw[very thick] (-1,1)--(-1,2);
\draw[very thick] (1,2)--(2,2);
\draw[very thick] (4,2)--(4,1);
\node at (4.5,1.5) {$=$};
\draw[dashed] (5,-1) rectangle (10,4);
\node at (7.5,1.5) {$H_{n}$};
\end{tikzpicture}
\end{center}

\end{itemize}

Note that the procedures for constructing $H_n$ for even and odd $n$ are essentially the same. We display them separately to emphasize that when $n$ is odd, the construction results in $H_{n}$ appearing sideways (reflected about the line $y=x$). 

The first few stages of the construction are shown below:\footnote{Image from \url{https://www.designcoding.net/hilbert-curve/}}

\includegraphics[width=6.1in]{hilbert.png}

\begin{tikzpicture}[scale=0.75]
\node at (0,0) {$H_0$};
\node[rotate=270] at (1.8,0) {$H_1$};
\node at (4.5,0) {$H_2$};
\node[rotate=270] at (8.6,0) {$H_3$};
\node at (16,0) {$H_4$};
\end{tikzpicture}

{\bf General hint for this problem: it helps to write all distances along the running track in base 4.}

\begin{enumerate}

\item [(a)] Warm-up: how long is $H_n$?

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

\item[(b)] How far along the track does a runner travel to get to the point $(n,n)$? (Hint: try it first for $n=2^k$.)

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

\item [(c)] One interesting feature of this running track is that you sometimes pass within a 1-meter distance of points that are very far ahead of you along the track --- or very far behind! Suppose Anna, Benny, and Charlotte all start from $(0,0)$ at the same time. Anna strolls at 1 m/s, Benny walks at 2 m/s, and Charlotte jogs at 3 m/s. Which pair(s) of them will pass within 1 meter of each other infinitely often? (Provide a proof both for the pairs that do and for the pairs that don't!)

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

\item[(d)] Della and Ellie each take a stroll along the running track at a speed of 1 m/s. Ellie starts $k$ seconds after Della, where $k$ is a positive {\em odd} integer.  Show that there is some value of $k$ such that Della and Ellie never pass within 1 meter of each other.

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

\end{enumerate}

\end{document}
