% This file was converted to LaTeX by Writer2LaTeX ver. 0.4
% see http://www.hj-gym.dk/~hj/writer2latex for more info
\documentclass[11pt,twoside]{article}
\usepackage[ascii]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[english]{babel}
\usepackage{amsthm,amsmath,amssymb,amsfonts,textcomp}
\usepackage{color}
\usepackage{calc}
\usepackage{hyperref}
\usepackage{geometry}                % See geometry.pdf to learn the layout options. There are lots.
\geometry{letterpaper} 

\newtheorem{theorem}{Theorem}
\theoremstyle{definition} 
\newtheorem{question}{Problem}

% Check if we are compiling under latex or pdflatex, and include the
% appropriate graphics package
\ifx\pdftexversion\undefined
 \usepackage[dvips]{graphicx}
\else
 \usepackage{graphicx}
\fi


\title{A Selection of Problems We've Done in\newline
Mountlake Math Challenge 2009-2010  }
\date{}
\begin{document}
\makeatother
\maketitle

\subsection* {Nim}

NIM is a game played with piles of stones (or pennies). You will need a partner to play this game. Here are the rules:


\begin{enumerate}


\item On your turn, you can take as many stones you want from one pile.

\item You must take at least one stone on each turn.

\item Players alternate taking turns.

\item The player who takes the last stone from the last pile wins.
\end{enumerate}

Try playing NIM with your partner. Keep track of who goes first in each game. There is always one player who is guaranteed to win if he/she plays according to a certain strategy. It is your job to figure out what this strategy is. Decide if Player 1 wins or Player 2 wins in each game.
\bigskip

Game 1: Pile 1 has two stones. Pile 2 has four stones. Pile 3 has six stones. \\
Winner is:  Player 1 or Player 2 \\
Strategy:
\medskip

Game 2: Pile 1 has three stones. Pile 2 has four stones. Pile 3 has eight stones. \\
Winner is:  Player 1 or Player 2 \\
Strategy:
\medskip

Game 3: Pile 1 has one stone. Pile 2 has four stones. Pile 3 has six stones. \\
Winner is:  Player 1 or Player 2 \\
Strategy:

\bigskip

 \bigskip
 
\subsection* {The Princess or the Tiger}

{\selectlanguage{english}
  from: Raymond Smullyan}


\bigskip

{\selectlanguage{english}
The King of Indrahabad had heard of a story where a prisoner had to
choose between two doors: behind one there was a princess, behind the
other a tiger. If the prisoner chose the princess, he could marry her;
if he chose the tiger, he would probably be eaten.}

{\selectlanguage{english}
The King thought this was a nice idea for his prisoners. But
he didn't want to leave things completely to chance, so he decided that
he would put some signs up on the doors. The signs would give some
clues as to what was behind the doors. A clever prisoner who can reason
logically would be able to save his own life. And, of course, in that
way the King could ensure that the husbands for all his daughters would
be smart!}

{\selectlanguage{english}
To make it a bit more difficult the King decided that it would
also be possible that there are princesses behind both doors or tigers
behind both doors. But there will never be more than one princess per
room or one tiger per room.}


\bigskip

{\selectlanguage{english}
}

{\selectlanguage{english}
The following two signs were put up on the doors:}



\begin{center}
\begin{minipage}{2.1346in}
{\centering\selectlanguage{english}
I
\par}

{\centering\selectlanguage{english}\itshape
In one of these rooms, there is a princess and, in the other, there is a
tiger.
\par}
\end{minipage}\end{center}
\begin{center}
\begin{minipage}{2.1346in}
{\centering\selectlanguage{english}
II
\par}

{\centering\selectlanguage{english}\itshape
In this room, there is a princess and, in the other room, there is a tiger.
\par}
\end{minipage}\end{center}

\bigskip

{\selectlanguage{english}
The prisoner asked: ``Is it true, what the signs say?''}

{\selectlanguage{english}
The King said: ``One is true and one is false''.}

{\selectlanguage{english}
Which door would you take if you were the prisoner? Why?}

\bigskip
\bigskip

 \question[\emph{Another logic puzzle}]{Suppose that you are a prisoner, and you are confronted with two doors: one leading to freedom, and one leading to the executioner's chamber, but you don't know which is which. A sentry guards each door. You know that one sentry always lies, and one sentry always tells the truth. Again, you don't know which is which. You are allowed to ask one of the sentries one question. What is a question you ask a sentry that will tell you with certainty which door leads to freedom?}

\subsection*{Graphs}
\question{How many times can three people shake hands if each person shakes hands with each other person exactly once? Same question for four people? Five people? Six? Ten?} 

\bigskip
 

 \question{In a certain kingdom, the are 8 cities, and three roads lead out of each city. How many roads are  there  in  the  kingdom? What if there were 12 cities, and three roads leading out of each? Now suppose there are 20 cities and four roads out of each? Lastly, what if there are three cities with three roads leading out of each?} 

\subsection*{The Pigeon Hole Principle}



{ \question{A drawer contains socks of two different colors: black or white. If you pull socks out of the drawer without looking, what is the minimum number of socks to pull out to assure yourself of a match?} 
 


\bigskip

 
 \question{The population of King county is about $1,800,000$ people. If humans have no more than one million hairs on their heads, show that there must be two people in the county with the same number of hairs on their heads.} 


\bigskip



 \question{Thirteen crates of apples arrives at a warehouse. Each crate contains apples of one of three varieties:  Delicious, Granny Smith, or Pink Lady. Are there four crates of one variety? Why?}  



 \question{Are there five crates of one variety? Why?} 
  
\bigskip

 \question{Show that if fifteen people attend a party and some shake hands with others (but not with themselves), then at the end, there are at least two people who have shaken hands with the same number of people.}   

\bigskip

\subsection*{How Do We Do That?}

\bigskip

 \question{There are two egg timers: one for 7 minutes and one for 11 minutes. How can we use these timers to measure exactly 15 minutes?}
 
 \bigskip
 
  \question{Find a two digit number, the sum of whose digits does not change when multiplied by a one digit number.}
  
  \subsection*{Parity or Paired Things}
  
  
 \question{Seven gears are arranged on a plane as shown below. Can all the gears rotate simultaneously?}
 

\bigskip
\begin{figure}[h]%
\begin{center}%
\scalebox{0.88}{%
\includegraphics{gears}%
}
\caption{}%
\label{FigureModel}%
\end{center}%
\end{figure}

\bigskip


 \question{Remembering that a knight's move in chess is straight two squares and over one, show that if a knight starts in one corner of a chessboard and after several moves returns to it, then it must have made an even number of moves.}

\bigskip

 \question{ Can a $5 \times 5$ square checkerboard be covered by $1 \times 2$ dominoes? How or why not?} 
 
   \subsection*{Divisibility by 2, 3, 5, 9, and 11}
 
 \question{How can you quickly determine whether a number is divisible by 2 or by 5? More importantly, why does this work?} 
  
\bigskip

 \question{How can you quickly determine whether a number is divisible by 3? And, this is harder, why does this work? Is there a similar approach to divisibility by 9?} 
 
 \bigskip

 \question{How can you quickly determine whether a number is divisible by 11? } 
 
  \bigskip
 
 \subsection*{Lines and Squares}
 
 
\question{In each of the following figures, find the total number of intersections made by the dotted lines. Then find the total number of rectangles formed by the dotted lines. Do you see any pattern to the progression? Do you see a relationship with the line problem?} 
\bigskip



\begin{figure}[h]%
\begin{center}%
\scalebox{0.22}{%
\includegraphics{Squares24}%
}
\caption{Number intersections : $ \qquad$ Number Rectangles:}%
\label{FigureModel}%
\end{center}%
\end{figure}

\bigskip

\begin{figure}[h]%
\begin{center}%
\scalebox{0.22}{%
\includegraphics{Squares34}%
}
\caption{Number intersections : $ \qquad$ Number Rectangles:}%
\label{FigureModel}%
\end{center}%
\end{figure}

\bigskip


\begin{figure}[h]%
\begin{center}%
\scalebox{0.22}{%
\includegraphics{Squares35}%
}
\caption{Number intersections : $ \qquad$ Number Rectangles:}%
\label{FigureModel}%
\end{center}%
\end{figure}

\subsection*{Permutations}

 \question{How many rearrangements of letters of the word "SPECIAL" are there?} 
 
 \bigskip

\bigskip

 \question{Which word has more arrangements of letters: "MEAT" or "MEET"? Why? How many arrangements does each word have? How many arrangements does "MEEM" and "MEEE" have?} 


\bigskip  

"MEAT":

\bigskip

"MEET":

\bigskip

"MEEM":

\bigskip

"MEEE":

\bigskip

\bigskip


 \question{How many arrangements are there of the letters in  "CARAVAN"?} 
 
 \bigskip
 \bigskip
   
  \question{How many ways are there to put $n$ \emph{different} balls into $m$ different boxes?}

 \bigskip
 \bigskip

\question{How many ways are there to put $n$ \emph{identical} balls into $m$ different boxes?}
 
  \bigskip

\end{document}  