\documentclass[11pt,twoside]{article}    
\usepackage{latex-macros/course}% !! use the macros 

%\backwardscompatibility        % !! use for backwards compatibility
%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip query
%\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}

\begin{document} 
\inclassproblems{2, Fri.}                    % !! start the paper

\begin{problem}
Subset take-away\footnote{From Christenson \& Tilford, \emph{David Gale's
Subset Takeaway Game, American Mathematical Monthly, Oct. 1997}} is a two
player game involving a fixed finite set, $A$.  Players alternately choose
proper, nonempty subsets of $A$ with the condition that one may not name a
set containing a set that was named earlier.  $A$ player who is unable to
move loses.

For example, if $A$ is $\set{1}$, then there are no legal moves and the
second player wins.  If $A$ is $\set{1,2}$, then the only legal moves are
$\set{1}$ and $\set{2}$.  Each is a good reply to the other, and so once
again the second player wins.

The first interesting case is when $A$ has three elements.  This time, if
the first player picks a subset with one element, the second player picks
the subset with the other two elements.  If the first player picks a
subset with two elements, the second player picks the subset whose sole
member is the third element.  \iffalse In short, in response to any first
move, the second player may choose the complementary set.\fi Both cases
produce positions equivalent to the starting position when $A$ has two
elements, and thus leads to a win for the second player.

Verify that when $A$ has four elements, the second player still has a
winning strategy.\footnote{David Gale worked out some of the properties of
this game and conjectured that the second player wins the game for
any set $A$.  This remains an open problem.}

\solution{
\textbf{Case 1:}[1st player chooses a size 1 subset] Then 2nd player
should choose the size 3 subset consisting of the other 3 elements.  This
results in a position corresponding to a size 3 game, and is therefore a
win for the 2nd player.

\textbf{Case 2:}[1st player chooses a size 3 subset] Then 2nd player
should choose the size 1 subset containing the remaining element.  This
results in a position corresponding to a size 3 game, and is therefore a
win for the 2nd player.

\textbf{Case 3:}[1st player chooses a size 2 subset $\set{a,b}$] Then 2nd
player should choose the complementary size 2 subset $\set{c,d}$.  Here
$a,b,c,d$ are the numbers 1,2,3,4 in some order.  So the possible
remaining moves are the four other subsets of size 2 and the four subsets
of size 1.
\begin{quote}

\textbf{Subcase 3.1:} At some point in further play, Player 1 picks a size
2 subset, $\set{a,c}$.  Then its complement, $\set{b,d}$, will also be
available as a possible move, and Player 2 should choose the complement.
This leaves a situation in which one of the Subcases 3.1--3 will again
apply.

\textbf{Subcase 3.2:} At some point in further play, Player 1 picks a size 1
subset, $\set{x}$, and this leaves a size 2 subset available as a legal
move.  Then a size 2 subset, $\set{x,y}$, must have been chosen
previously, and the size 1 set $\set{y}$ will be available as a possible
move.  Player 2 should choose $\set{y}$.  This leaves a situation that is
the same as the game on the complement of $\set{x,y}$, which Player 2 can
win.

\textbf{Subcase 3.3:} At some point in further play, Player 1 picks a size
1 subset and no size 2 subset remains as a legal move.  Then some other
size 1 subset will also available as a possible move, and Player 2 should
choose any such size 1 subset.  This either leaves no more moves, or the
situation of a game of size 2, which Player 2 will win in either case.
\end{quote}

We leave it to the reader to check that the moves prescribed in the
subcases 3.1--3 will indeed be possible.  Granting this, it follows that
these subcases exhaust the possible plays, which shows that Player 2 wins
in any of the subcases.  Hence Player 2 has a winning strategy in all
cases.}

\end{problem}


\begin{problem}
\bparts
\ppart Define a bijection between $\naturals$ and $\integers$.

\solution{
One such bijection is
\[
f(n) \eqdef \begin{cases}
                -n/2 & \text{if $n$ is even},\\
                 (n+1)/2 & \text{if $n$ is odd}.
\end{cases}
\]
}

\ppart Define a bijection between $\naturals$ and $\naturals \times
\naturals$ (the ordered pairs (0,0),(0,1),(1,2),\dots of natural numbers).

\solution{
Let $L_k$ be the list of pairs whose sum is $k$ in the increasing order of
first coordinate, so $L_k = (0,k), (1, k-1), (2, k-2), \dots, (k,0)$.
Then form the infinite list consisting of the elements of $L_0$ then
the elements of $L_1$, then the elements of $L_2$, \dots:
\[
(0,0),(0,1),(1,0),(0,2)(1,1)(2,0),(0,3)\dots
\]
Define $f(n)$ to be the $n-1$st pair in the list (so $f(0) = (0,0)$).
}

\eparts
\end{problem}

\end{document}
