Combinatorial Game Theory Quiz 3

The quiz lasts 75 minutes and covers everything from lessons 1-12.

  1. For each of the following Nim games, find one good move for the first player, if any. (10 points) [ Note : exactly one of the games is a win for the second player.]
    1. (5, 7, 8)
    2. (3, 4, 8, 9)
    3. (3, 5, 10, 12)
    4. (1, 6, 8, 9, 10)
  2. Consider the following Wythoff’s Queen game on a non-square board. Start with exactly one Queen. At each player’s turn, he picks up the Queen and moves it in one of the three indicated directions, any positive number of squares. The player who lands the Queen on the bottom-left hand corner wins, since the opponent is unable to make any move. Indicate whether each of the following 36 positions is winning or losing. (10 points)

  1. Consider the game sum G + H.
    1. Find G, H, such that G || 0, H || 0, and G + H = 0.
    2. Find G, H, such that G || 0, H || 0, and G + H || 0.
    3. Find G, H, such that G || 0, H || 0, and G + H > 0.
    4. Find G, H, such that G || 0, H || 0, and G + H < 0. (8 points)
  2. Consider the following partial games:

A = {3/8 | 1},  B = {-3/2 | -1/2},  C = {1/16 | 1/2},  D = {0 | 3/4}.

    1. These four games are all numbers. Find their values with the Simplicity Rule and show that A + B + C + D > 0.
    2. Left starts in the sum A + B + C + D and he can win. Among the four components A, B, C and D, which one should he move in? Write down all possibilities.
    3. Left made a move in D. Which component should Right move in, now that it’s his turn? (12 points)
  1. Given the following Toads-and-Frogs configurations:

compute the following configurations (hint: for the first one, do not consider its options). Check that the last game is fuzzy. (12 points)

  1. Compare the following games, and decide whether G > H, G < H, G = H or G || H. (Hint: it may help to analyse the game GH). (24 points)
    • G = 1/8, H = -3/4;
    • G = 300↑, H = 1/8;
    • G = *1904, H = *2008;
    • G = 3/4 + 2↓ + (*5), H = 3/4 + 3↓ + (*4);
    • G = 3/4 + 2↓ + (*6), H = 3/4 + 3↓ + (*5);
    • G = {5 | 2}, H = 3;
    • G = {5 | 2}, H = 1;
    • G = {5 | 2}, H = {7 | 3};
    • G = { {10 | 5} | {-2 | -3} }, H = 0;
    • G = { {0|4}, {1|2} | {4|7}, {5|6} }, H = 3;
    • G = {8 | 0} + {-1 | -5}, H = {2 | -4} + {5 | 3}.
  2. Recall the game of Cutcakes : given a cake, divided into m × n unit squares, each player at his turn takes a piece of cake and slices it along the edges of the squares, thus dividing the cake into two pieces. In addition, Left can only cut vertically, while Right can only cut horizontally. The values for m × n Cutcakes are given below: e. g. for a 6 × 8 cake, the value is -1.

    1. Based on the above grid, guess the values for 32 × n for n = 1, 3, 6, 10, 15, 21, 28.
    2. On a 7 × 9 cake, the value is -1, so Right wins. Find all possible winning moves for Right if he starts.
    3. In the midst of the game, there are three cakes of sizes 3 × 10, 8 × 6 and 13 × 5 left,
      together with some unit pieces. Given it is now Right‘s turn, can he win? If yes, find a winning move for him. (14 points)

Notes

  1. The class scored an average of 73.1 with a standard deviation of 13.4, out of a class of 20+ students.
  2. I added hints liberally throughout the final quiz; on hindsight these were probably a little unnecessary since the average score ended up approximately the same.
This entry was posted in Homework and tagged , , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s