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 V₀.

   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 V_t producing V_t+1.

   If at the beginning of round t, V_t 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.)