Combinatorial Game Theory Quiz 2

This quiz lasts 70 minutes and covers materials from lessons 1-9.

  1. Use the simplicity rule to compute the values of the following games. (10 points)
    • {1/2 | }
    • {-1/4 | }
    • {1/8 | 3/8}
    • {0 | 7/8}
    • {1/8 | 9/16}
    • { | }
  2. Compare the following games by writing G < H, G = H, G > H or G || H. (12 points)
    • G = 1 + ↑, H = 1/2 + 10↑
    • G = ↑, H = *10
    • G = 3↑, H = *10
    • G = -1/2 + 3↑ + (*8), H = -1/2 + 3↑ + (*9)
    • G = -1/2 + 3↑ + (*8), H = -1/2 + 4↑ + (*9)
    • G = -1/2 + 3↑ + (*5), H = -1/2 + 4↑ + (*6)
  3. The game of Maundy’s Cutcakes is played as follows. Take a cake, divided into m × n unit squares. At each player’s turn, he takes a piece of cake and makes any number of slices along the edges of the squares, dividing the piece into two or more pieces of exactly the same dimension. As before, Left can only cut vertically, while Right can only cut horizontally. A typical game may proceed as follows if Left starts:

It turns out this game is a number for all m × n cakes. Find the numbers for all 1 ≤ m ≤ 6, and 1 ≤ n ≤ 6. (16 points)

  1. Compute the values of the following Toads-and-Frogs games (some of them are given). Note that Left has more than one possible move in some of the games. (18 points)

  1. Decide whether each of the following statements is true or false. For false statements, find a counterexample. (18 points)
    1. If the first player wins in G, and the first player wins in H, then the first player wins in G+H.
    2. If the first player wins in G, and the second player wins in H, then the first player wins in G+H.
    3. If the first player wins in G, and Left wins in H, then Left wins in G+H.
    4. If x, y are any numbers and m = {x | y}, then x < m < y.
    5. If G + G = 2, then either G = 1 or G = 1* = 1+*.
    6. If G and H are games which are numbers, then we cannot have G || H.
    7. If A < 0 and X || 0, then the game G = {A | X} equals zero.
    8. If G + G = 1, then G cannot be negative.
    9. If G + G = 1, then G cannot be fuzzy.
  2. Find the values of the following six Hackenbush diagrams:

Find the value of the following Hackenbush game when the length tends to infinity (no rigourous proof required). (16 points in all)

Note

Out of a class of >20 students, the average score was 72.4/90, with a standard deviation of 11.5. This time, I think the quiz is a little simple. 😛

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