Grundy values and graph games

Questions 1 to 5 of 8

1. 1. What is mex({0, 1, 3})?

   2403
2. 2. A vertex has successors with Grundy values 0, 2 and 3. What is its Grundy value?

   Type a number.

3. 3. Two tokens sit on vertices with Grundy values 2 and 3 in a DAG game, where every play ends. Who wins with best play?

   The second player, because the two values are different.Neither player, because the game is a draw.The first player, because 2 XOR 3 is 1, which is not 0.The second player, because 2 + 3 is 5, which is odd.
4. 4. A teammate says two tokens with Grundy values 1 and 1 give a win for the player to move, because 1 + 1 = 2 is not 0. What is wrong?

   Nothing, addition is the right rule for sums.Sums use XOR, not addition: 1 XOR 1 is 0, so the player to move loses.Grundy values only work for graphs with cycles.The sum is 2, so the player to move wins by moving to value 0.
5. 5. On the graph with the self-loop 6 -> 6, what is the label of vertex 6?

   W, because it has a move.L, because it has no way out.W or L, depending on who moves first.D, because play can go on forever.