Assignment 3, Due Thursday, October 11th.

  1. Consider the following 2-player game played with bit vectors of length n. Player A chooses the inital values of the n bits. This vector evolves with time. Call the initial state V0.

    B's goal is to convert the vector to the vector of all zeros. A's goal is to prevent this from ever happening. There is a series of rounds for t=0, 1, ... In the tth round:

    B picks an n-bit pattern P.

    A circularly shifts P by any amount she wants, then xors the result with the current vector Vt producing Vt+1.

    If at the beginning of round t, Vt is zero, then B has won. Otherwise the game continues.

    1. Determine precisely the set of values of n for which B has a winning strategy. Prove your result.
    2. For those values of n where B has a winning strategy, give an upper bound on the number of rounds required for B to win.

  2. Fill a 4x4x4 tic-tac-toe board with 32 Xs and 32 Os such that neither player has a winning line.

  3. Extra Credit: Do the same for 3x3x3x3 and 4x4x4x4 :-)

  4. Problem 8 in section 1.5 of Ferguson. (Page I-8). (This is the SOS game.)
Mathematical Games
Daniel Sleator
Last modified: Tue Sep 18 14:24:02 EDT 2001