\documentclass{article}
\usepackage{enumitem}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{graphicx} % Required for inserting images
\usepackage{hyperref}
\usepackage{tikz}

\title{Mathcamp 2026 Qualifying Quiz\footnote{Problems 1, 3, and 6 are by Tejo Madhavarapu (MC '25).  Problem 2 is by Misha Lavrov (MC staff).  Problem 4 is by Eli Gold (MC '23-'25) and Everett Guo (MC '24-'25).  Problem 5 is by Tarun Rapaka (MC '24-'25).}}
\date{}

\begin{document}

\maketitle

\begin{enumerate}
\item

A group of $n$ people play a game where they all stand in a circle, each wearing a red or blue hat. In each round of the game, any player whose neighbors' hat colors match each other advances to the next round, while the players with one red-hat neighbor and one blue-hat neighbor are eliminated. 
(If there are one or two remaining players, then no one is eliminated.)
The process repeats until either everyone is eliminated, or there is a round where no one is eliminated.  An example game is shown below.
\begin{center}
\begin{tikzpicture}[scale=1.25]
\draw(0,0) circle(1.0);
\fill[color=blue](0.0,1.0) circle(0.15);
\fill[color=red](0.4338837391175581,0.9009688679024191) circle(0.15);
\fill[color=blue](0.7818314824680298,0.6234898018587336) circle(0.15);
\fill[color=blue](0.9749279121818236,0.22252093395631445) circle(0.15);
\fill[color=red](0.9749279121818236,-0.22252093395631434) circle(0.15);
\fill[color=red](0.7818314824680299,-0.6234898018587335) circle(0.15);
\fill[color=red](0.43388373911755823,-0.900968867902419) circle(0.15);
\fill[color=blue](1.2246467991473532e-16,-1.0) circle(0.15);
\fill[color=blue](-0.433883739117558,-0.9009688679024191) circle(0.15);
\fill[color=red](-0.7818314824680297,-0.6234898018587337) circle(0.15);
\fill[color=blue](-0.9749279121818236,-0.2225209339563146) circle(0.15);
\fill[color=blue](-0.9749279121818238,0.22252093395631334) circle(0.15);
\fill[color=blue](-0.7818314824680299,0.6234898018587334) circle(0.15);
\fill[color=blue](-0.4338837391175575,0.9009688679024194) circle(0.15);
\draw(3,0) circle(1.0);
\fill[color=red](3.433883739117558,0.9009688679024191) circle(0.15);
\fill[color=red](3.78183148246803,-0.6234898018587335) circle(0.15);
\fill[color=red](2.2181685175319705,-0.6234898018587337) circle(0.15);
\fill[color=blue](2.025072087818176,0.22252093395631334) circle(0.15);
\fill[color=blue](2.21816851753197,0.6234898018587334) circle(0.15);
\fill[color=blue](2.5661162608824424,0.9009688679024194) circle(0.15);
\draw(6,0) circle(1.0);
\fill[color=red](6.78183148246803,-0.6234898018587335) circle(0.15);
\fill[color=blue](5.21816851753197,0.6234898018587334) circle(0.15);
\end{tikzpicture}
\end{center}
\begin{enumerate}[label=\alph*.]
\item For which values of $n$ is it possible for all players to be eliminated?
\item For those $n$ for which it is possible for all players to be eliminated, what is the minimum number of rounds that it
can take to eliminate all players (in terms of $n$)?  What is the maximum?
\end{enumerate}

\item A pentabend is the following shape (or its reflection).  Its boundary is made up of five congruent arcs.
Each arc is $1/6$ of a circle of radius $1$, so it has
length $\pi/3$.
\begin{center}
\includegraphics[width=3in]{pentabend.png}
\end{center}

Suppose we take $X$ pentabends and join them, without overlap and along complete arcs only, into a bigger figure whose boundary has length $Y$. Then this figure is said to have roundness $X/Y$.

What is the maximum possible roundness of such a figure? You should find the best lower and upper bounds you can (the largest roundness of any figure you can find, and the smallest value that you can prove can never be exceeded) even if they do not meet. 

\item One day, at dawn, the corner of a quarter-infinite grid of squares catches fire. Each day, firefighters choose a square that is not on fire and protect it, permanently preventing it from catching fire. Every night, the fire spreads from all the squares that are currently on fire to all orthogonally adjacent squares that are not protected.  Squares already on fire remain on fire.
\begin{enumerate}[label=\alph*.]
\item Prove that the firefighters cannot contain the fire to a finite area.
\item Now suppose that an $m \times n$ rectangle in the corner of the grid is initially on fire.  Also suppose that on the first day, the firefighters are allowed to protect more than one square.  (On subsequent days, they can still only protect one square per day.)  What
is the minimum number of squares that the firefighters need to protect
on the first day in order be able to eventually contain the fire to a finite area?
\end{enumerate}

\item  Let $\mathbb{Z}$ denote the set of integers.
An \emph{arithmetic sequence} is a set of the form 
$\{an + b : n \in \mathbb{Z} \}$ with $a,b \in \mathbb{Z}$ and $a \ne 0$.

A set of integers is called \emph{sequential} if it is a (possibly infinite or empty) union of arithmetic sequences.
A set of integers is called \emph{con-sequential} if its complement in $\mathbb{Z}$ is sequential.
\begin{enumerate}[label=\alph*.]
\item Show that an intersection of two sequential sets is sequential.  Is an infinite intersection of sequential sets necessarily sequential?
\item Show that a union of finitely many arithmetic sequences and finitely many integers is con-sequential.
Does every con-sequential set have this form?
\item
Convince yourself that a finite union of arithmetic sequences is both sequential and con-sequential.  Are there any other sets that are sequential and con-sequential?
\end{enumerate}

\item
\begin{enumerate}[label=\alph*.]
 \item Let $n$ and $k$ be positive integers with $k \ge 2$. Tony is trying to unlock the door to the Cookie Ferry, which is secured by a string of $n$ digits. Each digit may be one of the values $0$ through $k-1$, and the string originally starts off as all $0$s. On every move, Tony may either increase a single digit by $1$, or change a single $k-1$ to $0$. To unlock the door, Tony must perform a sequence of moves such that each of the $k^n$ possible strings appears exactly once, and such that the ending string has all of its digits equal to $k-1.$

Determine, with proof, all positive integers $n$ and $k$ for which Tony can unlock the door.
(For instance, when $n=3$ and $k=2$, this is possible because Tony can use the sequence of moves $000 \to 001 \to 011 \to 010 \to 110 \to 100 \to 101 \to 111.$)

\item The staff are looking for a new combination for the Cookie Ferry, with $n=2$.  If they perform a sequence of moves starting from $00$, such that each of the $k^2$ strings appears exactly once, then what are the possible ending strings (in terms of $k$)?
\end{enumerate}
\item
    Oh no! The campers have run away with... the staff's stash of cookies! 

    A group of 15 mentors found out about this and came to try to win their cookies back. The campers decided to arrange a small game for them: each mentor will be moved to a separate room, given a box of sandwich cookies or chocolate chip cookies, and then has to guess the name of another mentor who received a box of the same type of cookies. The mentors who guess correctly get to keep their boxes of cookies, and the other boxes are taken away.
    
    Before being led to their separate rooms, the
    mentors are allowed to coordinate to formulate a strategy, but they cannot communicate after they are separated.

    How many boxes of cookies can the mentors guarantee to keep? (This is a hard question, so we'd appreciate any partial progress!)
\end{enumerate}
\end{document}
