\documentclass[11pt]{article}

\usepackage[varg]{txfonts}
\usepackage{hyperref}
\urlstyle{tt}

\usepackage{geometry}
\geometry{%
  letterpaper,
  lmargin=3cm,
  rmargin=3cm,
  tmargin=3cm,
  bmargin=3.5cm,
  footskip=36pt,
  headheight=36pt}
  

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

\begin{document}

\begin{center}\section*{Mathcamp 2010 Qualifying Quiz Solutions}

Name:   * * * INSERT YOUR NAME HERE  * * *\end{center}

\subsection*{References}   * * * LIST ANY REFERENCE TEXTS USED HERE.   CITE AS APPROPRIATE IN THE SOLUTIONS. * * *

\subsection*{Solutions}

\begin{enumerate}
\item % HANOI VARIATION - Problem 1
%
This problem is a variation of the famous Tower of Hanoi problem.  Suppose now that the three pegs are arranged in order --- A, B, and C --- and on a single move you can only move rings between A and B or between B and C. A ring can move from A to C or vice versa only in two moves (and then only provided that there isn't a smaller ring on B).

\begin{enumerate}
\item What is the minimum number of moves required to move a stack of $n$ rings from A to C? Prove your answer.
\begin{solution}
* * *  INSERT PROBLEM 1a SOLUTION HERE * * *
\end{solution}

\item What is the minimum number of moves required to move a stack of $n$ rings from A to B? Prove your answer.
\begin{solution}
* * *  INSERT PROBLEM 1b SOLUTION HERE * * *
\end{solution}

\end{enumerate} 

\item % 100-GAME  - Problem 2
%
Consider the following two-player game. Starting with the number 0, players take turns adding to the current sum; on your turn, you can add either 4 or 7. If on your turn you can make the new sum end in two zeros (i.e., if your turn leaves a multiple of 100), you win.

Assuming best play, is there a winning strategy for either player, or will the game go on indefinitely? If there is a winning strategy, should you move first or second, and how do you play from there?

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



\item %  $n+r$ AND $n-s$  -- Problem 3
%
Suppose $r$ and $s$ are positive integers. Let $F$ be a function from the set of all positive integers $\{1,2,3,\ldots\}$ to itself with the following properties:

\begin{itemize}
\item $F$ is one-to-one and onto. (If you don't know these terms, look them up online.)
\item For every positive integer $n$, either $F(n) = n+r$ or $F(n) = n-s$.
\end{itemize}     

\begin{enumerate}
\item If $r=5$ and $s = 8$, what is $F(2010)$?

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

\item Find, with proof, the smallest positive integer $k$ such that the $k$-fold composition of $F$ with itself is the identity function; that is, $F(F(...F(n))) = n$ for all $n$ (where there are $k$ copies of $F$ on the left-hand side). The answer will depend on $r$ and $s$.

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

\end{enumerate}


\item % $2^n$ AND $5^n$  -- Problem 4
%
For some positive integer $n$, the numbers $2^n$ and $5^n$ begin with the same 10 digits when written in base 10. What are these digits? You do not need to show that such an $n$ exists, but you do need to prove that, assuming such an $n$ exists, your answer is the only possible one. 

\textit{Extra:} Do you have any ideas about how to prove that such an $n$ exists?

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



\item %  NONREPEATING STRINGS -- Problem 5
%
Let $a_n$ be the number of strings of length $n$ that can be formed from the symbols X and O, with the restriction that a string may not consist entirely of multiple copies of one string of shorter length. For example, for $n=4$, the string XXOX is allowed, while the strings XXXX and XOXO are not allowed. It is not hard to check that $a_4 = 12$.

Here is a table showing $a_n$ and approximate values of the ratio $a_{n+1}/a_n$ for different values of $n$.
\[
\setlength{\arraycolsep}{0.3cm}
\begin{array}{|c|cccccccc|}
\hline\hline
n           & 1 & 2 & 3   & 4   & 5     & 6     & 7   & 8 \\
\hline
a_n         & 2 & 2 & 6 & 12  & 30  & 54    & 126   & 240 \\
\hline
a_{n+1}/a_n & 1 & 3 & 2 & 2.5 & 1.8 & 2.333 & 1.905 & 2.1 \\
\hline\hline
\end{array}
\]

The table suggests two conjectures:
%
\begin{enumerate}
\item For any $n>2$, the number $a_n$ is divisible by 6,
\item $\displaystyle \lim_{n\to\infty} a_{n+1} / a_n = 2$.
\end{enumerate}
%
Prove or disprove each of these conjectures.

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


\item % DISTANCE TO INTEGER -- Problem 6

For $0 \leq x \leq 1$, let $T(x) = x$ if $x\leq 1/2$, and $T(x) = 1-x$ if $x \geq 1/2$. In other words, $T(x)$ is the distance from $x$ to the nearest integer. Let 
\[
f(x) = \sum_{n=1}^\infty T(x^n). 
\]
Does there exist a value of $x$ (still between 0 and 1) such that $f(x) = 2010$? Find all such values or show that none exist.

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


\item % DOMINOS -- Problem 7
%
For what values of $M$ and $N$ can an $M \times N$ chessboard be covered by an equal number of horizontal and vertical dominoes? (A domino always covers two adjacent squares on the board.)

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


\item %  NEIGHBORS -- Problem 8
%
If we tile the plane with black and white squares in a regular checkerboard pattern, then every square has an equal number (four) of black and white neighbors. (Two squares are considered neighbors if they are not the same but have at least one common point; squares that touch just at a vertex count as neighbors.) But if we try the analogous pattern of cubes in 3-dimensional space, it no longer works this way.

\begin{enumerate}
\item How many neighbors of each color does a white cube have?
\begin{solution}
* * *  INSERT PROBLEM 8a SOLUTION HERE * * *
\end{solution}

\item Find a coloring pattern for a grid of cubes in 3-dimensional space so that every cube, whether black or white, has an equal number of black and white neighbors.
\begin{solution}
* * *  INSERT PROBLEM 8b SOLUTION HERE * * *
\end{solution}

\item What happens in $n$-dimensional space for $n>3$? Is it still possible to find a color pattern for a grid of hypercubes, so that every hypercube, whether black or white, has an equal number of black and white neighbors?
\begin{solution}
* * *  INSERT PROBLEM 8c SOLUTION HERE * * *
\end{solution}

\end{enumerate}



\end{enumerate}


\end{document}