
\documentclass[12pt]{article}
\usepackage{graphicx}
\usepackage{amssymb}
\usepackage{lscape}
\usepackage{verbatim}
%
\font\elevenss=cmss11
\font\tenss=cmss10
\font\niness=cmss9
\font\eightss=cmss8
\font\sevenss=cmss8 at 7pt
\font\sixss=cmss8 at 6pt
\font\fivess=cmss8 at 5pt
\newfam\ssfam
\textfont\ssfam=\elevenss \scriptfont\ssfam=\eightss
 \scriptscriptfont\ssfam=\sixss
\def\ss{\fam\ssfam \elevenss}
%
\setlength{\evensidemargin}{-.05in}
\setlength{\oddsidemargin}{-.05in}
\setlength{\textwidth}{6.4in}
\renewcommand{\baselinestretch}{1.0}
\setlength{\parskip}{15pt plus 2pt minus 1pt}

\def\ray{\overrightarrow}
\def\pb{\pagebreak}
\def\blank{\underline{\;\;\;\;\;\;}}
\def\W{{\mathbb W}}
\def\br{\hfill \break}
\def\ssc{\noindent} 

\begin{document}

\begin{center}
{\Large \bf Poison}
\end{center}

Our first job (aside from playing the game a few times) was
to ``devise a winning strategy'' for Poison.  This means giving
complete instructions as to how to win the game, including how
to decide whether one wants to go first.  Although the original
problem was framed in terms of a ten counter game, it will be easiest
to answer this in the general context where we start with any number 
of counters.

The key to this game is to leave a number of counters that has a remainder
of~1 when divided by~3.  In algebraic terms, we can say such a number
is $3x+1$ where $x$ is an integer.  Therefore, our first rule is
\begin{quote}
{\bf Rule~1:} If the number of counters is $3x+1$ where $x$ is an integer,
then you want to go second.  Otherwise you want to go first.
\end{quote}
If the number of counters is not $3x+1$ then it must be $3x+2$ or $3x$,
for some integer $x$, since the remainder on division by~3 can only
be 0, 1 or 2.  Thus we have the next rule:
\begin{quote}
{\bf Rule~2:} If the starting number is $3x+2$, then you must take away~1, 
and if the starting number is $3x$ then you must take away~2.
\end{quote}
If you are allowed to choose who goes first and you follow these rules,
then when it is your opponent's turn to play for the first time, she 
will always face a number of counters that is one more than a multiple of~3.
Why?  Because either it was that to start with, and you made your opponent
go first, or it was $3x+2$ and you took~1 leaving $3x+1$, or it was
$3x$ and you took~2 to leave $3x-2$ which is the same as $3(x-1) + 1$,
so is also one more than a multiple of~3.  

To continue the play after your opponent has played, there is only one
other rule you must follow.
\begin{quote}
{\bf Rule 3:} Always take the opposite of what your opponent has taken.
That is, if she takes~1, you take~2, and if she takes~2, you take~1.
\end{quote}
This rule guarantees that any two moves in a row beginning with your
opponent's move will always consume a total of~3 counters.  Now observe:
if the number of counters is one more than a multiple of~3, and you
remove three counters, the number remaining is still one more than a 
multiple of~3.  Since we have already guaranteed your opponent will face
one more than a multiple of~3 on her first move, this guarantees she will
face one more than a multiple of~3 on {\em every} move.  

Could it happen that you are unable to follow Rule~3 because there are not
enough counters left?  If there are no counters left, you have won, so 
inability to follow Rule~3 can happen only if you are required to take two
and there is only one left.  This can never happen, since your opponent 
always plays from one more than a multiple of~3, and there is no move
from one more than a multiple of~3 that leaves only one counter.

We have now proved that if you get to decide whether to go first, you can
force your opponent always to face one more than a multiple of~3, which
will inevitably result in her moving from~4 counters, and finally from
her having to move from~1 counter, that is, to take the poisoned one.
You win!

Let's try out our strategy on a game with 431 counters.  Since 
$$431 = 3 \times 143 + 2 \, $$
our strategy says to take~1 and leave 430 which is one more than
a multiple of~3.  Following Rule~3 will now guarantee a win.

Having generalized to a game with any number of counters, we can go
further and generalize to a game where instead of a maximum of~2 
counters, the maximum is some greater number $k$.  You see, just as
the first strategic point we discovered in the two counter game was to 
leave your opponent with~4, the first strategic point in the $k$ counter
game is to leave your with $k+2$.  Then whatever number they take, you
can still take the ``opposite''; in this case that means if they take
$x$ then you take $k+1-x$.  So in the max-3 game ($k=3$), if they take~1
you take~3, if they take~2 you take~2, and if they take~1 you take~3.
This guarantees that $k+1$ counters disappear every pair of moves.
If the original number is one more than a multiple of $k+1$ then 
you go second, otherwise you can take some number of counters to leave
your opponent with one more than a multiple of $k+1$ and then follow
the ``opposite'' rule.  The proof that this works is pretty much the
same as in the two counter game.

\pb
\begin{center}
{\Large Notes on the solution}
\end{center}

{\small
\begin{enumerate}
\item Note first of all that the paradigm from page~112 is not part
of the writeup or its structure.  The paradigm helps me illustrate to
you how, in diverse mathematical situations, you are learning to work
from the concrete to the general.  It has nothing to do with writeups.
\item The quotation marks in the first sentence are to show the material
was quoted, not to indicate any unusual meaning.
\item To exhibit understanding of the problem and make the writeup readable,
it is not required to restate the problem (although you can if you want to).
The first paragraph of the answer merely summarizes what the writeup will
address.
\item In this writeup, the justification is mixed in with the statement of 
the rules.  It was easiest to explain why Rules~1 and~2 guarantee the 
opponent will always face a number one more than a multiple of~3 
on her first play right after explaining the rules.
\item The argument used to justify why Rule~3 guarantees you always leave
your opponent one more than a multiple of~3 is called {\em mathematical 
induction}.  You don't need to know this, but I thought it would help to
point out some of the underlying logic you have used.  
\item Another piece of logic you used was the proof by cases: you proved 
that your opponent always faces one more than a multiple of~3 on her
first turn by proving separately that this holds in all three possible
cases, where the cases are the three possible remainders on division by~3.
\item In your writeup, we would not take off points if you omitted
the point made in the paragraph ``Could it happen...  ".  But technically,
to prove your strategy works, you need to address this. 
\item The answer to the last question about a game with 431 counters is
not highlighted or set aside in a box at the beginning, but because it
gets its own paragraph, I think it's easy enough to spot.
\item The generalization in the final paragraph is more than was asked
for and would receive extra credit.  We're not expecting you to answer more
than was asked on a regular basis, and we won't give you extra credit 
for answering random things we didn't ask, but when there is a direct 
generalization that you can extend your original analysis to cover, 
it is good mathematics to continue your dicsussion jut a bit, and you 
will certainly earn extra credit for it.   
\item Look at the meta-rubric (if you haven't found it already, it's on
the bottom of the main course website).  All items on this have been
successfully addressed in this writeup.  Note that having a good plan
does not entail a long psychological discussion of what you tried before
figuring out the solution you ended up with.  In this case, the plan
is almost absent since your solution is complete.  Sometimes the plan
will involve assigning value to variables, then solving equations, or
comparing the factorizations of two numbers, in which cases it is good
to make clear what the plan is even if you are unable to get all the
way through its execution.
\item What would a bad writeup have been?  Here are some quotes from
problematic solutions to Poison. 
\begin{enumerate}
\item {\bf The strategy for winning at Poison is to make sure you leave
your opponent with 4, 7, 10 and so on.}  The main problem with this
is that it doesn't tell you how to accomplish this.  Another problem
is that you should be able to state this pattern either verbally (``one
more than a multiple of~3'') or mathematically ($3x+1$ for some integer 
$x$'').  There is nothing wrong with first identifying the pattern as
4, 7, 10, ..., but in order to be understood, you should also find a
more direct description when possible.
\item {\bf To win at ten counter poison, if you are playing second, always
take the opposite of what the opponent does.}  A problem with this (leaving
aside the issue of whether ``take the opposite'' is sufficiently clear)
is that it does not sound like a complete strategy.  It says what to do
if you go second, but if you go first then what?  We know there's no way
for the first player to win ten counter poision against a smart opponent,
but this must be stated.  Thus ``Don't go first!'' is better than ``If
you go second...".  
\item {\bf To win at Poison, if $(N-1)/3$ is a whole number, go second 
and take the opposite of the other player every time, while if $(N-1)/3
= x + 1/3$ or $x + 2/3$, then go first and take~1 or~2 respectively.}
This solution pretty much has all the correct ingredients right there 
in one sentence, but that's just the problem: you can't jam this much
into a sentence.  Look what is left unsaid.  We don't know what $N$ is
(a separate sentence saying we are analyzing the $N$ counter game would
cure this).  We don't know that $x$ must be an integer, and since we are
working with fractions, we certainly can't assume the reader will realize
we mean $x$ to be a whole number.  The instruction to take the opposite
is left in a form we're not sure is adequate, and it is omitted altogether
in the case where you choose to go first.  
\end{enumerate}
\end{enumerate}
}

\end{document}

