Combinatorial Game Theory Quiz 1

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

  1. For A-C, determine whether the following Nim games are first or second-player wins. There is no need to find the winning move. (10 points)
    1. (10, 15, 17, 19)
    2. (7, 14, 17, 24)
    3. (19, 18, 5, 11)
    4. If (5, 7, 9, m) is a second-player win, what is m?
  2. The following Nim games are all first-player wins. Find ALL possible winning moves from each game. (10 points)
    1. (5, 8, 10, 13, 17)
    2. (5, 14, 15)
    3. (11, 12, 13, 15)
  3. In the game Cube Game, start with several heaps of stones. Two players alternately remove a positive cube number of stones from exactly one of the heaps, and the player who removes the last stone wins. Find the Nim value of one heap of n stones, for n between 45 and 50 inclusive. (12 points)
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
0 *1 0 *1 0 *1 0 *1 *2 0 *1 0 *1 0 *1 0 *1
17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
*2 0 *1 0 *1 0 *1 0 *1 *2 *3 *2 *3 *2 *3 *2 *3
34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
0 *1 *3 0 *1 0 *1 0 *1 0 *1
  1. Determine whether the following are first- or second-player wins. (7 points)
    • (21, 28, 33)
    • (44, 49, 50)
    • (33, 37, 40, 45)
  1. Find ALL possible winning moves from the following Cube Game configurations. (16 points)
    • (6, 7, 8)
    • (24, 25, 26)
    • (34, 35, 36)
  2. In a certain game, moves a, b, c, d, e and f result in remoteness values of 5, 7, 8, 9, 10, 11 respectively. What is the best move for the first player? What is his worst move? Explain your answer briefly. (6 points)
    Suppose the remoteness values were 4, 8, 10, 12, 20, 22 instead. Same as above: what are the best and worst moves for the first player? (6 points)
  3. Consider the game of Triple Kayles: given a continuous row of n bottles, a valid move knocks down three neighbouring bottles, possibly separating the row into two rows.

  1. A player loses if there’s no valid move for him (i.e. when each row has only 1 or 2 bottles, the next player loses). Find the Nim values of Triple Kayles for one row of n bottles, for 15 ≤ n ≤ 20. Also, prove that if the Nim value for n is *0, then either n=1 or n is even. (14 points)
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
0 0 0 *1 *1 *1 *2 *2 0 *3 *3 *1 *1 *1 0
  1. Remember Wythoff’s Queens? Each queen can move in three possible directions:

Now consider the chessboard below: at each player’s turn, he picks just one queen and moves an arbitrary number of moves either left, down or diagonally left-down. Each square can hold any number of queens at any time.

wytqueenvariant

But the rules have changed now: the first player to put any queen onto the black square wins. Analyse the above board: who wins? (14 points).

Some Notes

  1. When I conducted the course in 2008, the average score was 73.5 out of 95 with a standard deviation of 8.3. Yup, the students were pretty good! Either that, or the quiz was too simple. 😛
  2. The students ranged from years 1-4 (equivalently, Sec. 1-4 or grades 7-10).
  3. Q7 was pretty tricky, and if my memory serves me well, only 2 out of 20+ students solved it correctly.
  4. Some students were tricked by Q4 because <rot13>gurl qvq abg ernyvfr gung avz inyhrf, hayvxr gur avz urncf, pna npghnyyl vapernfr</rot13>!
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