\documentclass[11pt]{article}

\usepackage{amsmath,amsfonts,amssymb}

\usepackage[colorlinks]{hyperref}

\usepackage{tikz,tikzsymbols,graphicx}

\usepackage{subcaption}

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

\begin{document}

\centerline{\Large \bf Mathcamp 2024 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{http://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{http://www.mathcamp.org/computers}{\texttt{www.mathcamp.org/computers}}.

If you need clarification on any problem, please email \href{mailto:quiz24@mathcamp.org}{\texttt{quiz24@mathcamp.org}}. You may not consult or get help from anyone else. You can 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! {\em Any deviation from these rules will be considered plagiarism and may disqualify you from attending Mathcamp.}

\subsection*{The Problems\footnote{Problem \#3 is due to Leo Kargin (MC 2022--2023). Problem \#4 is due to Maya Kalai (MC 2023). Problems \#1, \#2, \#5, and \#6 were written by the Mathcamp staff.}}


\begin{enumerate}
\item 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.)}

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

\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!
\end{enumerate}



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

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

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

\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?
\end{enumerate}

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

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

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

\end{enumerate}

\item ``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.45\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.22\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.22\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}.

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

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

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

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

\end{enumerate}

%\item Four meteorologists are exploring an infinite flat planet. At every point on the planet, the air has some temperature, and the temperature never changes over time---though different points may have different temperatures.
%
%The four meteorologists start at the same place. Then, each one picks a fixed direction and speed, and goes off exploring. Every hour, they take a temperature reading and transmit their findings back to Earth. Scientists on Earth collect this data and make two surprising observations:
%\begin{itemize}
%\item Every hour, the average of the four temperatures they measure is 0 degrees Celsius.
%\item If the meteorologists try the experiment again from any other starting point (but keep the same fixed direction and speed that they had before), they still get an average of 0 degrees every hour.
%\end{itemize}
%One way this could happen is if every point on the infinite planet had exactly the same temperature: 0 degrees Celsius. Is anything else possible---could there be variation in the temperatures?

\item 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.
\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$.) 

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

\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).
\end{enumerate}
\end{enumerate}

\end{document}