\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

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

The picture below shows a variant of a famous paradoxical puzzle. On the left, we take two rectangles of area 60, and cut each one into two pieces. On the right, we rearrange the four pieces, and put them together into a single rectangle of area 119. How could this be?

\centerline{\includegraphics[width=0.9\textwidth]{rectangle-paradox-wide.png}}

\begin{enumerate}
\item[(a)] Explain what's wrong. \textit{(Similar paradoxes can be found under names such as ``Chessboard paradox'' or ``Missing square puzzle''. It's fine to look at a source that explains such a paradox, provided you cite it---and explain it in your own words.)}

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

\item[(b)] Although two $5 \times 12$ rectangles cannot \emph{really} be rearranged into a $7\times 17$ rectangle, it is possible to take two $a \times b$ rectangles and cut them as shown in the picture above to make a $c \times d$ rectangle, with no paradox. What should the lengths $a,b,c,d$ be (up to scaling, of course)?

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

\item[(c)] It is also possible to take \emph{three} congruent rectangles, cut each one into two pieces, and rearrange them to form a single rectangle similar to the original three. How can we do this?

Try to find an answer that lets you create a paradoxical decomposition of your own!

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

\end{enumerate}

\newpage

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

\section*{Problem 2}

Kayla has two red boxes, two green boxes, and two blue boxes. Each of the six boxes contains a secret number. Kayla hands the boxes to Leo and asks him to write the letters $A$, $a$, $B$, $b$, $C$, and $c$ on the boxes. We will write $\#A$, $\#a$, $\#B$, $\#b$, $\#C$, and $\#c$ to refer to the secret numbers inside these boxes.

From there, the boxes go to Maya, who opens the boxes and reports the differences $\#A-\#a$, $\#B-\#b$, and $\#C-\#c$ (in that order). Next, the boxes go to Nathan, who opens the boxes and reports the sum of the numbers in the red boxes, the sum of the numbers in the green boxes, and the sum of the numbers in the blue boxes (in that order). The resealed boxes, along with Maya's and Nathan's reports, are then handed back to Kayla, who must determine the numbers in each of the boxes.

Kayla expected Leo to label same-color boxes with the same letter, which would have made it easy for Kayla to figure the numbers: for example, knowing $\#A-\#a$ from Maya and $\#A+\#a$ from Nathan, Kayla could solve for $\#A$ and $\#a$. However, to Kayla's surprise, Leo is color blind, so his labeling had nothing to do with the colors. 

\begin{enumerate}
\item[(a)] For which of the labelings that Leo used is it still possible for Kayla to determine the six secret numbers? (Kayla can see which colors have which labels on them.)

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

\item[(b)] Generalize your answer to a problem with $2n$ boxes of $n$ different colors, labeled with $n$ different uppercase and lowercase letters.

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

\end{enumerate}

\newpage


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

\section*{Problem 3} 

Here is a curious fact you may not have known about mathematicians: when asked a yes-or-no question, number theorists will always tell the truth, while analysts will always lie. Be careful: if you ask someone a yes-or-no question, and they cannot answer either ``yes'' or ``no'' to it, then the universe explodes in paradox. For example, this happens if you ask an number theorist, ``Is your answer to this question `no'?''

\begin{enumerate}
\item[(a)] What yes-or-no question can be asked to both a number theorist and an analyst to cause the universe to explode in both cases?

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

\item[(b)] To try to prevent the universe from exploding in paradox, logicians have decided to act as paradox detectors. When you ask a logician a yes-or-no question, the logician will answer ``yes'' if asking the question to a number theorist would cause the universe to explode, and ``no'' otherwise. For example, if you ask a logician, ``Is your answer to this question `no'?'' the logician will answer ``yes''.

What yes-or-no question can be asked to a logician to cause the universe to explode?

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

\end{enumerate}

\newpage


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

\section*{Problem 4}

A group of 11 Mathcampers decided to bake a rainbow unicorn sprinkle cake with 10 slices. Unfortunately they cannot split up the slices into smaller pieces, because they do not want to risk upsetting the unicorn. Each Mathcamper wants a slice of the cake (but not more, because Mathcampers aren't greedy). Each Mathcamper helped bake the cake to some extent. The Mathcampers have been assigned fractions $x_1, x_2, \dots, x_{11}$ representing their share of the credit in baking the cake, where $0 < x_i < \frac1{10}$ for each $i$, and $x_1 + x_2 + \dots + x_{11}=1$.


\begin{enumerate}
\item[(a)] How can you randomly distribute the slices of cake such that the $i$\textsuperscript{th} Mathcamper has a probability  of exactly $10x_i$ of getting a slice of cake?

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

\item[(b)] Generalize your solution to distribute $k$ slices to $n$ campers, for all $k$ and $n$ with $n > k \ge 1$.

As before, the Mathcampers have been assigned fractions $x_1, x_2, \dots, x_n$ representing their share of the credit in baking the cake, where $0 < x_i < \frac1k$ for each $i$, and $x_1 +  \dots + x_n=1$; for each $i$, you want the $i$\textsuperscript{th} Mathcamper to have a probability of exactly $k x_i$ of getting a slice of cake.

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

\item[(c)] Suppose that, in the setup of part (b), you do not know the value of $k$ (the number of slices). Instead, you will put the Mathcampers in a random order, according to some strategy, and then serve slices of cake in that order until the cake runs out. Is there a way to do this so that for each $i$, the $i$\textsuperscript{th} Mathcamper will have a probability of exactly $k x_i$ of getting a slice of cake---no matter what $k$ turns out to be? (You may still assume that we have $0 < x_i < \frac1k$ for all $i$, and $x_1 +  \dots + x_n=1$.)

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

\end{enumerate}

\newpage

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

\section*{Problem 5}

``Half stitching'' is a form of embroidery which makes images out of diagonal stitches in a square grid. Our images will all be created from a single thread, which alternates traveling in straight lines (called stitches) along the front and the back of the grid:
\begin{itemize}
\item The front of the grid is where the image is formed. Here, each stitch goes from a point $(x,y)$ either to $(x+1,y+1)$ or $(x-1,y-1)$. We say that we \emph{stitch a square} if a stitch on the front follows its diagonal (from top right to bottom left or from bottom left to top right).

\item The back of the grid is not part of the image. Here, each stitch can follow any straight line---but it must travel a positive distance, because if you end a stitch where it started, it will unravel.
\end{itemize}
This problem is about minimizing the total length of thread needed to stitch a given pattern. For example, Figure~\ref{fig:example-stitches-long} and Figure~\ref{fig:example-stitches-short} (with front stitches in red and back stitches in blue) have the same pattern stitched, but the thread is $2\sqrt2 + 2\sqrt5$ units long in the first case and only $2\sqrt2 + 2$ units long in the second case.

\begin{figure}[h]
\centering

\begin{subfigure}[b]{0.3\textwidth}
	\centering
	\includegraphics[scale=0.14]{half-stitching-1.png}

	\caption{A $3\times 4$ grid}
	\label{fig:grid-stitches}
\end{subfigure}
\quad
\begin{subfigure}[b]{0.3\textwidth}
	\centering
	\includegraphics[scale=0.14]{half-stitching-2.png}

	\caption{A comb with $4$ teeth}
	\label{fig:comb}
\end{subfigure}
\quad
\begin{subfigure}[b]{0.3\textwidth}
	\centering
	\includegraphics[scale=0.14]{half-stitching-3.png}

	\caption{A tall comb with $4$ teeth}
	\label{fig:tall-comb}
\end{subfigure}

\medskip

\begin{subfigure}[b]{0.4\textwidth}
	\centering
	\includegraphics[scale=0.14]{half-stitching-4.png}

	\caption{A wide comb with $3$ teeth}
	\label{fig:wide-comb}
\end{subfigure}
\quad
\begin{subfigure}[b]{0.25\textwidth}
	\centering
	\includegraphics[scale=0.14]{half-stitching-0-long.png}
	\caption{Two example stitches}
	\label{fig:example-stitches-long}
\end{subfigure}
\quad
\begin{subfigure}[b]{0.25\textwidth}
	\centering
	\includegraphics[scale=0.14]{half-stitching-0-short.png}
	\caption{Two example stitches}
	\label{fig:example-stitches-short}
\end{subfigure}

\caption{Diagrams for problem 5}
\label{fig:stitches}
\end{figure}
\begin{enumerate}
\item[(a)] Show that the minimum length of thread (front and back) needed to stitch every square in an $m \times n$ rectangular grid is $mn(\sqrt2+1) - 1$. An example with $m=3$ and $n=4$ is shown in Figure~\ref{fig:grid-stitches}.

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

\item[(b)] A \textit{comb with $n$ teeth} is a pattern of width $2n-1$ and height $2$ that stitches every square in the bottom row and every other square in the top row; an example of this pattern with $n=4$ is shown in Figure~\ref{fig:comb}. What is the minimum length of thread (front and back) needed to stitch this pattern, in terms of $n$?

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

\item[(c)] A \textit{tall comb with $n$ teeth} is a pattern of width $2n-1$ and height $3$ that stitches every square in the bottom row and every other square in the top two rows; an example of this pattern with $n=4$ is shown in Figure~\ref{fig:tall-comb}. What is the minimum length of thread (front and back) needed to stitch this pattern, in terms of $n$?

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

\item[(d)] A \textit{wide comb with $n$ teeth} is a pattern of width $5n-4$ and height $2$ that stitches every square in the bottom row and every \emph{fifth} square in the top row; an example of this pattern with $n=3$ is shown in Figure~\ref{fig:wide-comb}. What is the minimum length of thread (front and back) needed to stitch this pattern, in terms of $n$?

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

\item[(e)] Can you prove anything in general about the minimum length of thread needed to stitch a pattern?

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

\end{enumerate}

\newpage

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

\section*{Problem 6}

You may have heard of the Borromean rings (a famous pattern of 3 equal circles) or the Olympic rings (a famous pattern of 5 equal circles). The \textbf{unchanging rings} (which aren't famous because we just made up the name) are a pattern that can be made from different numbers of circles, with some special points on them marked.

A system of unchanging rings must satisfy three \textbf{unchanging rules}:
\begin{enumerate}
\item[I.] If two circles meet at a marked point, they share exactly two marked points.
\item[II.] If two marked points lie on a common circle, they must share exactly two common circles.
\item[III.] We can get from any circle to any other by some number of hops along marked points.
\end{enumerate}
One possible system of unchanging rings is shown below:

\centerline{\includegraphics[width=0.2\textwidth]{unchanging-rings.png}}

\begin{enumerate}
\item[(a)] Draw a system of unchanging rings with more than $4$ circles, all equal in size.

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

\end{enumerate}

Maybe you thought this problem was about geometry? Just kidding! You see, there is a special kind of circle called a \textbf{math circle}: it's not a geometric object, but a group of people doing math together. Let's say that a ``marked point'' in such a case is a person participating in one or more of the math circles. We can form a system of unchanging rings out of math circles as well, by satisfying the unchanging rules.

\begin{enumerate}
\item[(b)] Prove that every system of unchanging rings (whether made up of ordinary circles or math circles) has an \textbf{unchanging constant} $n$, such that every circle contains exactly $n$ marked points, and every marked point is contained in exactly $n$ circles. (In the example drawn above, $n=3$.) 

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

\item[(c)] In a system of unchanging rings with unchanging constant $n$, what is the maximum number of circles?

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

\item[(d)] For some $n$, find a nonempty system of unchanging rings with unchanging constant $n$ such that it has fewer circles than the maximum you found in part (c).

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

\end{enumerate} 

\end{document}
