Assignment 2, Due Tuesday, September 25th.
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 H1=1, H2=2,..., be the sizes of the initial piles for
which the first player has no winning strategy, the P-positions.
Show that if f(Hj)³ Hj, then Hj+1=Hj+Hl where
If f(Hj)<Hj, show that the sequence of losing positions is finite
and that Hj is the final term.
- 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
- 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.
- (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.)
- Compute the grundy number of the sprouts position that
consists of 3 spots connected by a line. (*----*----*)
Last modified: Tue Sep 18 14:24:02 EDT 2001