\documentstyle[12pt,twoside]{article}

\addtolength{\topmargin}{-1in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9in}

\raggedbottom

\input{macros-course}

\iffalse
\setlength{\topmargin}{-0.50in}
\setlength{\textheight}{8.5in}
\setlength{\oddsidemargin}{0.0in}
\setlength{\evensidemargin}{-0.0in}
\setlength{\textwidth}{6.5in}
\addtolength{\parskip}{2pt}
\addtolength{\itemsep}{0.1in}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{claim}{Claim}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newcommand{\qed}{\mbox{\ \ \ }\rule{6pt}{7pt} \bigskip}
\fi
\newtheorem{fact}{Fact}
\begin{document}

\handout{teamprobs1}{Problems for Recitation 1}{September 10, 1998}

\begin{enumerate}
\iffalse
\item Prove that 
\[\forall k \in \naturals\ :\ (\sqrt{2})^k \mbox{ is rational iff k is even.}\]
\fi

\item The {\em Gale game} is played on a finite set,
$A$, of size two or more, e.g., $A$ might be the set of integers from 1 to
$n\ge 2$.  Two players alternate moves.  A {\em move} is a choice of a
nonempty {\em proper} subset (that is, a nonempty subset of $A$ other than $A$
itself), subject to the constraint that no subset may be chosen which {\em
contains} a previously chosen subset.  The player who first gets stuck
without an allowed move loses.

For example, when $A = \{1, 2, 3, 4\}$, the moves might be:
\[
\begin{array}{ccccccccc}
player: & 1 &2 & 1 &2 & 1 &2 & 1 &2\\
move:   &\{1,2\} &\{3,4\} & \{1,3\} & \{2,4\} & \{1\} & \{2\} & \{3\} & \{4\}\\
\end{array}
\]
At this point, the first player has no valid move and therefore loses.

{\em Gale's Conjecture} is that the second player can always win.  Note
that this does not mean that the second player {\em will} win every game.
He can lose if he plays stupidly, but there always is a way for the second
to win no matter what moves the first player makes.  (This is like the
situation in tic-tac-toe, where the first player {\em can} lose by playing
stupidly, but has a simple {\em strategy} which guarantees that he will never
lose.)

(a) Prove Gale's Conjecture for the games with $n=2$ and 3.

(b) Must every Gale game end with a winner (remember, chess games don't)?
What is the length of the longest, and shortest, possible games on
$\{1,\dots,n\}$?  Explain.

(c) Try to prove Gale's Conjecture for $n=4$.  Hint: you will be
overwhelmed with cases if you don't identify "symmetric" cases.  For
example, if player 1's first move is $\{1,2,3\}$, and you work out how
player 2 will win, then you can adapt your strategy to work against {\em
any} first move consisting of a set of size three, by permuting the roles
of 1, 2, 3, and 4.

\item  You are given 12 identical looking balls, and told that
one of them is of different weight from the other 11, but you don't 
know in advance whether it is heavier or lighter. Can you
find the ball that is of different weight using only 3 weighings?

\end{enumerate}

\end{document}

