Assignment 2, Due Tuesday, September 25th.

1. Consider the following take-away game. As usual we start with a non-empty pile of chips and the first player removes some, but not all of the chips from the pile. Subsequently, a player may take at most f(n) chips from the pile. Here n is the number of chips removed by the previous player and f is some non-decreasing function.
   
   Let H₁=1, H₂=2,..., be the sizes of the initial piles for which the first player has no winning strategy, the P-positions.
   
   Show that if f(H_j)³ H_j, then H_j+1=H_j+H_l where

   Hl=

   min i£ j

   {Hi| f(Hi)³ Hj}.

   If f(H_j)<H_j, show that the sequence of losing positions is finite and that H_j is the final term.

2. Smart Dots is a windows-based program for playing Dots and Boxes. Beat Smart Dots playing in Grandmaster mode, in the 3x5 game, letting the computer go first. This can be done using the strategies described in the handout. Report the last position reached in the game where no box has 3 sides completed. Also report the final position.

3. Brussel Sprouts is a modified form of Sprouts. In Brussel Sprouts, the initial position is a set of n "+" signs. Each of the four points of the + sign is one "life". A move consists of drawing a curve starting at one life and ending at another, followed by drawing a slash through the middle of the curve just drawn, adding two more lives (one on each side of the line just drawn). Prove that the number of moves in a game of Brussel Sprouts is a function of n. Find the function.

4. (REVISED SEPT 18) Here's an idea for improving the Applegate-Jacobson-Sleator sprouts program. In the set representation of a sprouts position there is a set of regions, and each of these is a set of boundaries. Each boundry is a sequence of spots encountered as you walk around the boundary with your right hand touching the boundary. Suppose you reversed the sequence defining one of these boundaries. Is this an equivalent position? Express your opinion and justify it informally. (Note that if true, then this would give a way to improve the program -- the canonization step could be made to map even more positions onto the same representation.)

5. Compute the grundy number of the sprouts position that consists of 3 spots connected by a line. (*----*----*)