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

Define a ``digital number" in base $b$ ($b>1$) to be a positive integer $n$ such that the base-$b$ digits of $n^2$ add up to $n$. For example, $9$ is a digital number in base $10$ because $9^2 = 81$, and $8+1=9$. Also, $9$ is a digital number in base $7$ because $9^2 = 81$ is written as $144$ in base $7$, and $1+4+4=9$. 
\begin{enumerate}
\item[(a)] There are five other digital numbers in base $7$, aside from $9$. What are they?

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

\item[(b)] It is not a coincidence that base $7 = 2^2 + 2 + 1$ has unusually many digital numbers. Prove that for all $k \ge 2$, there are at least five digital numbers in base $k^2+k+1$.

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

\item[(c)] Find all integers $b>1$ such that $b+3$ is a digital number in base $b$. (Prove your answer!)

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

\item[(d)] Prove that in any base $b \ge 16$, every digital number is less than $b^{3/2}$. What's the best upper bound you can prove on the largest digital number in base $b$, when $b$ is large?

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

\end{enumerate}

\newpage


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

\section*{Problem 2}

Figure~\ref{pixel-fractal} shows the $13^{\text{th}}$ stage of a fractal obtained by the following process. The $1^{\text{st}}$ stage is a single black square. The $n^{\text{th}}$ stage is obtained by combining two congruent copies of the $(n-1)^{\text{th}}$ stage: one copy is rotated $90^\circ$ counterclockwise and placed to the right of the other, so that they are aligned along the bottom side. An example of this is shown in Figure~\ref{combining-two-copies}.

\begin{figure}[h]
\centering
\begin{subfigure}[t]{0.34\textwidth}
\centering
	\includegraphics[scale=0.4]{stage13.png}
\caption{The $13^{\text{th}}$ stage of the fractal}
\label{pixel-fractal}
\end{subfigure}
\begin{subfigure}[t]{0.55\textwidth}
\centering
	\includegraphics[scale=0.4]{stage13plus1.png}
\caption{Obtaining the $14^{\text{th}}$ stage from the $13^{\text{th}}$}
\label{combining-two-copies}
\end{subfigure}
\caption{Diagrams of the fractal in problem 2}
\end{figure}

\begin{enumerate}

\item[(a)] As $n$ increases, the slope of the diagonal line from the bottom left corner to the top right corner gets closer and closer to some value $m$. What is $m$?

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

\item[(b)] In the $n^{\text{th}}$ stage, let $a_n$ be the area of the black region above the diagonal line, and let $b_n$ be the area of the black region below the diagonal line. 

As $n$ increases, $a_n/b_n$ gets closer and closer to some value $a/b$. What is $a/b$?

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

\end{enumerate}

\newpage


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

\section*{Problem 3} 

Marvin is playing a solitaire game with marbles. There are $n$ bowls (for some positive integer $n$), and initially each bowl contains one marble. Each turn, Marvin may either
\begin{itemize}
\item remove a marble from a bowl, or
\item choose a bowl $A$ with at least one marble and a different bowl $B$ with at least as many marbles as bowl $A$, and move one marble from bowl $A$ to bowl $B$. 
\end{itemize}
The game ends when there are no marbles left, but Marvin wants to make it last as long as possible.

\begin{enumerate}

\item[(a)] Prove that the game must end after at most $\frac{n(n+1)}{2}$ turns.

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

\item[(b)] Prove that for every positive integer $k$, there is an $n$ such that Marvin can make the $n$-bowl game last for at least $kn$ turns.

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

\item[(c)] Marisa comes along and asks to join the game. Marvin and Marisa revise the rules: they will alternate taking turns, starting with Marisa. When the game ends, whoever took the last turn is the winner.

Prove that among any three consecutive values of $n$, there is at least one value for which Marvin has a winning strategy.

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

\end{enumerate}

\newpage


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

\section*{Problem 4}

An architect is designing a city. The city will be built on the segment of the $x$-axis from (0,0) to (1,0). Each building is a rectangle whose bottom edge rests on this segment of the $x$-axis. In the architect's vision, the city has infinitely many buildings: the $n^{\text{th}}$ building to be built will have width $(1/2)^n$ and height $n$. Two buildings cannot overlap, but they can share a vertical edge.

The sun rises in the east (in the positive $x$ direction, to the right of the city). A building \emph{has a nice view} if you can see the sunrise from the top floor: there are no taller buildings to its right blocking the view.

There are also some parks in the city. You may have noticed that the widths of the buildings add up to $1$, so there's no room to add parks. Therefore all the parks are very small: just single points on the $x$-axis. However, parks must still be outdoors: If a building's bottom edge runs from $(a,0)$ to $(b,0)$, we cannot add a park at any point $(x,0)$ for $a<x<b$.

\begin{enumerate}

\item[(a)] Suppose that there is a park at the point (1/3, 0). Is it possible to design the city so that every building east of the park has a nice view? Can any buildings west of the park have a nice view?

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

\item[(b)] Suppose that there are two parks: one at $(x_1, 0)$ and one at $(x_2,0)$, with $0 < x_1 < x_2 < 1$.

For which $x_1$ and $x_2$ is it possible to design such a city? (No nice views are required.)

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

\item[(c)] For which $x_1$ and $x_2$ is it possible to design the city so that every building between the two parks has a nice view?

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

\item[(d)] Show that it's possible to design the city so that no building shares a vertical edge with any other building. Can any buildings in such a city have a nice view---and if so, how many? 

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

\end{enumerate}

\newpage

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

\section*{Problem 5}

Assaf, Ben, Charlotte, Dan, and Emily are set to appear on the hit reality TV game show \emph{Singleton}. At the end of each episode, one of the contestants is ``voted out of the set" and eliminated from the game. The last contestant remaining wins.

In the voting phase of the episode, each contestant left in the game casts a vote against another contestant still in the game. They vote one at a time, in alphabetical order. The votes are public: when a contestant goes to vote, they are aware of all votes cast so far, and can use that information to inform who they vote against. Once everyone has voted, the contestant that received the most votes is eliminated. If there is a tie, the player who is last alphabetically among those who received the maximum number of votes is eliminated.

It is common knowledge that the contestants all act rationally according to the following priorities:

\begin{enumerate}
\item[I.] A contestant's top priority is to avoid elimination for as many episodes as possible (in particular, they would like to win the game if possible).
\item[II.] A contestant wants to eliminate someone in this episode that is as early in the alphabet as possible (without compromising the top priority of lasting as long as they can). 
\end{enumerate}

\begin{enumerate}

\item[(a)] Who gets eliminated in the first episode? Who wins the game?

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

\item[(b)] Suppose the game show begins with an immunity challenge. The winner of the challenge cannot be eliminated in the first episode; nobody is allowed to vote against them. If Dan wins the immunity challenge, who gets voted out? What if Emily wins instead? What if Assaf wins?

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

\item[(c)]Suppose the winner of the immunity challenge is allowed to give their immunity away to another contestant. Does it ever make sense for a contestant to choose to do so? 

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

\end{enumerate}

\newpage

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

\section*{Problem 6}

You are investigating a dangerous cult, with the goal of uncovering its reclusive Mastermind. From previously gathered intelligence, you know that the cult has 100 members: the Mastermind, the Go-between, the Figurehead, and 97 Pawns. Each member of the cult associates with some, but not all, of the other members. In particular:

\begin{itemize}
\item The Mastermind is very reclusive; they associate with the Go-between, but no other member.
\item The Go-between associates with the Mastermind and the Figurehead, but none of the Pawns.
\item The Figurehead associates with everyone except the Mastermind.
\item The Pawns associate with the Figurehead, but not the Mastermind nor the Go-between. Some pairs of Pawns may also associate with each other (so, each Pawn could potentially have up to 97 total associations).
\end{itemize}

You cannot figure out which members have special roles just by looking. However, each day, you can select a pair of members to investigate, and determine whether they associate with each other.

\begin{enumerate}

\item[(a)] Prove that if you investigate \emph{all} pairs of members, then you can identify the Mastermind.

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

\item[(b)] Is there a strategy to find the Mastermind in under 1000 days?

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

\item[(c)] Suppose there are $n$ members in the cult: one Mastermind, one Go-between, one Figurehead, and $n-3$ Pawns. How quickly can you find the Mastermind? 

\textit{(We don't know the exact answer to (c), but we know some good bounds. Do your best!)}

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

\end{enumerate} 

\end{document}
