HW 0

1. Induction on the distance d from v to a vertex of out-degree 0. For
   the base case, if
   d = 0 then f(v) = 0, while v is a vertex of out-degree 0, and clearly a P-position
   since there is no legal move at all. On the other hand, if d > 0
   then either f(v) = 0 or f(v) > 0. If f(v) = 0 then every move from
   v is to a position with Grundy value 1 or greater. By the induction
   hypothesis, these are N-positions, so v is a P-position. On the
   other hand, if f(v) > 0 then there is at least one move from v to a
   position w with f(w) = 0. By the induction hypothesis, w is a
   P-position, so v is an N-position.

2. [Digraph omitted] The winning positions are those with nonzero
   residue mod 3. The Grundy value of the position with n counters
   remaining is n mod 3.

3. [Digraph omitted] The winning positions are those with an odd
   number of counters remaining. The Grundy value of the position with
   n counters remaining is n mod 2.

4. The Grundy values are 2, 0, and 1. The nim-sum is 3, so this is an
   N-position. A winning move is to move the first game from 2 to 1,
   which can only be done by taking one counter from that pile.

5. The grundy function f(i) = i, and the winning move is to take all
   the counters. Of course, if the pile is empty, then there is no
   winning move.

6. 4 + 5 + 6 + 8 = 15, so this is an N-position. The unique winning
   move is to take one counter from the pile of 8.