• Let a game be played by two players on an arbitrary graph \(G\)
  • the current state of the game is a certain vertex
• The players perform moves by turns,
  • from the current vertex to an adjacent vertex
• The person that is unable to move will either lose or win the game

• We consider the case of an arbitrary directed graph with cycles
• Given an initial state, who will win the game (or draw)?
  • both players play with optimal strategies

• We will solve the problem efficiently
  • for all possible starting vertices
  • \(O(m)\)
    • linear time with respect to the edges

• Winning vertex
  • Player always wins if they start at this vertex
  • If they play optimally
• Losing vertex
  • Player always loses if they start at this vertex
  • If the opponent plays optimally

• If a vertex has no outgoing edges
  • It is a losing vertex LV
• If a vertex has an outgoing edge to a LV
  • then it is a winning vertex WV
• If all outgoing edges from a vertex lead to WV
  • then it is a LV
• If a vertex is not a WV or a LV then it is a draw vertex (DV)

• A vertex is a DV, if and only if
  • it has no outgoing edges to LV vertices
  • it has at least one outgoing edge to a DV vertex

• Go through all vertices
• Apply first or second rule to label the vertex
• Repeat

Running time \(O(nm)\)

• Mark all vertices with no outgoing edges as LV
• Start a DFS from each
  • Follow reverse edges
  • Only go to undefined vertices (UV)
  • LV \(\leftarrow\) UV
    • Mark UV as WV
  • WV \(\leftarrow\) UV
    • if all outgoing edges from UV is to WV
      • (do in \(O(1)\) using an edge counter at vertices, decrement when arriving from a WV)
      • Mark UV as LV
    • otherwise, stop the DFS

Every edge is visited once, hence \(O(m)\).

// This vector of vectors represents the reversed adjacency list of the graph.
vector<vector<int>> adj_rev;

// These vectors are used to store information about each vertex in the graph.
// winning[v] is true if vertex v is in a winning state, and false otherwise.
// losing[v] is true if vertex v is in a losing state, and false otherwise.
// visited[v] is true if the vertex v has been visited during the depth-first search.
// degree[v] represents the in-degree (number of incoming edges) of vertex v.
vector<bool> winning;
vector<bool> losing;
vector<bool> visited;
vector<int> degree;

// Depth-First Search (DFS) function to traverse the graph and determine winning and losing states.
void dfs(int v) {
    // Mark the current vertex as visited.
    visited[v] = true;

    // Traverse all vertices u that have an incoming edge from v in the reversed adjacency list.
    for (int u : adj_rev[v]) {
        // If vertex u has not been visited yet.
        if (!visited[u]) {
            // If the current vertex v is in a losing state, mark u as winning.
            if (losing[v])
                winning[u] = true;
            // If the in-degree of vertex u is reduced to 0, mark u as losing.
            else if (--degree[u] == 0)
                losing[u] = true;
            // Otherwise, continue the DFS traversal for vertex u.
            else
                continue;

            // Recursively call the DFS function for vertex u.
            dfs(u);
        }
    }
}

• Play on a \(m\times n\) board
• Some cells cannot be entered
• One of the cells is exit cell
• The positions of policeman and thief are known
• If policeman and thief on same cell
  • policeman wins
• If thief on exit cell and has turn
  • policeman loses

• Policeman walks in 8 direction, thief in 4
• They move in turns
• Policeman moves first
• They can skip a turn, if they want to

• Coordinates of the policeman: \(P\)
• Coordinates of the thief: \(T\)
• Coordinates of the exit: \(E\)
• Whose turn it is: \(P_t\) (true if policeman’s turn)
• One state/vertex is defined by \((P,T,P_t)\)

• Initial winning and losing vertices
  • if \(P==T\), then Policeman wins
  • else if \(T==E\), then Policeman loses

• An alternative definition for the same game is on undirected graphs
• You have an arbitrary graph \(G\)
  • Note that any grid can also be expressed as a graph
  • But, not all graphs can be expressed as 2D-grids
• First the cop chooses her node
• Then, the robber chooses her node
• The cop and the robber move in turns
  • Cop first
• If the cop can get to the robber’s node, cop wins
• If the robber can avoid the cop indefinitely, robber wins

Lemma: Any cycle of size greater than 3 can be used by the robber to escape forever.

Proof: Robber initially chooses a node not adjacent to the cop. Then she moves in the same direction as the cop, forever.

Definition: Vertex \(v\) is dominated by vertex \(w\), if its closed neighbourhood is a subset of the neighbourhood of \(w\).

Definition: A vertex \(v\) is a losing vertex if it is dominated by another vertex.

Definition: An undirected graph \(G\) is a cop-win graph if the cop can always force a win on this graph.

Definition: An undirected graph \(G\) is a robber-win graph if the robber can forever escape the cop on this graph.

Lemma: Every cop-win graph has a dominated vertex

Proof: Otherwise, the robber would have an escape path from any vertex

• However, we can’t say the opposite
  • If a graph has a dominated vertex, it can still be a robber-win graph

Lemma: There is a dominated vertex in any cop-win graph, whose removal will result in another cop-win graph.

Proof: We will prove by showing that a robber cannot convert a cop-win graph to a robber-win graph by adding a dominated vertex. Let \(G\) be any cop-win graph. Add a dominated vertex \(v\) to \(G\) to obtain \(G'\). Let \(w\) be the vertex dominating \(v\) in \(G'\). Obviously, the closed neighbourhood of \(v\) is a subset of the neighbourhood of \(w\) in \(G'\), by definition. This means, any move from \(v\) can also be made from \(w\). Therefore, going to \(v\) has no advantages over \(w\) for the robber, she is simply going to a more restricted vertex. If the robber ever had a winning strategy in \(G'\), she could simply replace \(v\) moves by \(w\) moves and would still win. Therefore, if \(G'\) is robber-win, then \(G\) is also robber-win. We know that \(G\) is cop-win. A contradiction. Therefore, \(G'\) is also cop-win.

Corollary: A cop-win graph can be dismantled down to a single node by removing dominated nodes one by one.

Proof: It follows from the previous two lemmas.

• For all edges, count the number of triangles they participate
• Find a vertex whose degree is one more than the triangle count of one of its edges
  • Remove the vertex
  • Update triangle counts
  • Repeat
• Running time : \(O(md)\), where \(m\) is edge count, \(d\) is degeneracy (bound by vertex count)

\(v\) is dominated by \(u\). Any dominated vertex \(v\) and dominating vertex \(u\) has an edge in between, which makes \(\delta_v-1\) triangles with \(v\)’s neighbours (except \(u\)).

• Describes the so-called impartial two-player game
  • moves and winning/losing depends only on the state of the game
  • the only difference between the players is that one of them moves first
• Assume perfect information
  • no information is hidden
  • no randomicity
• Game is finite
  • after a number of moves, one of the players lose the game
  • no draws

• Any perfect-information impartial game can be reduced to Nim!
• There are a few piles of stones, each with several stones
• The player in turn, can take any desired number of stones from any desired pile and throw them away
• A player loses if they can’t make a move
  • All piles are empty
• Also can say: “the player who picks the last stones, wins”.
• The game state is described by a set of positive integers
  • Each move decreases one of these integers

Theorem. The current player has a winning strategy iff the xor-sum of the pile sizes is non-zero. The xor-sum (a.k.a. nim-sum) of a sequence \(a\) is \(a_1\oplus a_2\oplus a_3\oplus\ldots\oplus a_n\), where \(\oplus\) is the bitwise exclusive or.

• Let’s rephrase things in simple terms:
  • Let \(s\) be the current xor-sum of the piles’ sizes
  • If it is your turn, and \(s\) is non-zero you can always win
  • If it is your turn, and \(s\) is zero, and your opponent plays the right moves, then you will lose

          X
    X     X                1        1
    X  X  X   -->> 1   1   0  -->>  0   -->>  YOU WIN!
    X  X  X        1   0   0        1
    3  2  4                         s 

We will prove it by induction on the next slide.

• Base case: empty game, \(s=0\), you lose
• Inductive hypothesis
  • Assume you are in state \(Q\)
    • Theorem is true for all states reachable from \(Q\)
• Inductive step: show theorem is true for \(Q\)
  • Two cases
    • \(s\) is zero
    • \(s\) is non-zero

• Note that when you change a pile’s size from \(x\) to \(y\)
  • \(s\) changes as \(s\oplus x \oplus y\)
• So, when you change any pile when \(s=0\)
  • \(s\oplus x \oplus y = 0\oplus x\oplus y = x\oplus y\)
• We know that \(y<x\), so \(x\oplus y\) cannot be zero
  • Whatever we do, we reach a state where the opponent wins

• Consider binary representation of \(s\), for example \(1001101\)
  • Consider the largest non-zero bit (7th bit on the example)
• One of the piles must be big enough to have a 1 on that bit
• Let \(x\) be the size of that pile
  • We will change the size of that pile to \(y=x\oplus s\)
  • \(y\) is less than \(x\), because the largest bit was 1 in both \(x\) and \(s\), it is 0 in \(y\)
  • So, \(x \rightarrow y\) is a legal move
• The new xor sum is \(s\oplus x\oplus y=s\oplus x\oplus(x\oplus s)=0\)
  • We found a legal move to always put the opponent in a losing state!

• Is the (13,12,8) state a winning-state?
• If so, what is a winning move?

• Is the (13,12,8) state a winning-state?
  • The xor-sum of 13, 12 and 8 is

      1101
      1100
      1000
      ----
      1001  -> non-zero

Hence the state is a winning-state

• If so, what is a winning move?
  • Change any pile to make the sum zero:
    • Change the first pile to 0100 = 4
    • Change the second pile to 0101 = 5
    • Change the third pile to 0001 = 1

• What is the nim-sum of 27 and 17?
• The nim-sum of 38 and x is 25. Find x.

• What is teh nim-sum of 27 and 17?
  • 11011 (+) 10001 = 01010 = 10
• The nim-sum of 38 and x is 25. Find x.
  • 100110 (+) xxxxxx = 011001
  • xxxxxx = 100110 (+) 011001 = 111111 = 63

• Find all winning moves in the game of nim,
  • with three piles of 12, 19, and 27 chips.
  • with four piles of 13, 17, 19, and 23 chips.

Nimble. Nimble is played on a game board consisting of a line of squares labelled: 0, 1, 2, 3, … . A finite number of coins is placed on the squares with possibly more than one coin on a single square. A move consists in taking one of the coins and moving it to any square to the left, possibly moving over some of the coins, and possibly onto a square already containing one or more coins. The players alternate moves and the game ends when all coins are on the square labelled 0. The last player to move wins. Show that this game is just nim in disguise. In the following position with 6 coins, who wins, the next player or the other? What is a winning move?

Turning Turtles A horizontal line of n coins is laid out randomly with some coins showing heads and some tails. A move consists of turning over one of the coins from heads to tails, and in addition, if desired, turning over one other coin to the left of it (from heads to tails or tails to heads). For example consider the sequence of n = 13 coins:

T   H   T   T   H   T   T   T   H   H   T   H   T
1   2   3   4   5   6   7   8   9  10  11  12  13

One possible move in this position is to turn the coin in place 9 from heads to tails, and also the coin in place 4 from tails to heads.

T   H   T   H   H   T   T   T   T   H   T   H   T
1   2   3   4   5   6   7   8   9  10  11  12  13

Turning Turtles A horizontal line of n coins is laid out randomly with some coins showing heads and some tails. A move consists of turning over one of the coins from heads to tails, and in addition, if desired, turning over one other coin to the left of it (from heads to tails or tails to heads).

1. Show that this game is just nim in disguise if an H in place n is taken to represent a nim pile of n chips.

2. Assuming (a) to be true, find a winning move in the above position.

1. Turning the first coin at position k from H to T represents removing a pile with k stones. Turning a coin to the left of it at position m (m < k) acts like removing k-m stones from a nim pile.

2. To find a winning move simply find one or two coins to turn, such that after turning them the xor-sum of the positions of the remaining heads are zero.

Any state of any impartial game has a corresponding Nim state!

• Consider the following modification to Nim
  • We can now also add stones to piles
  • This doesn’t change the winning strategy
    • Even if you increase a pile, your opponent can decrease it back to the old value
      • This cannot be a winning strategy!
    • Eventually you have to make a standard nim move

• Let’s consider a state \(v\) of a two-player impartial game
  • Let \(v_i\) be the states reachable from it
    • (where \(i \in \{ 1, 2, \dots, k \} , k \ge 0\)).
• To this state, we can assign a fully equivalent game of Nim with one pile of size \(x\).
  • \(x\) is the Grundy value or nim-value of state \(v\).

• This number can be found recursively:

\[ x = \text{mex}\ \{ x_1, \ldots, x_k \}, \]

• where \(x_i\) is the Grundy value for state \(v_i\)
• the function \(\text{mex}\) (minimum excludant) is the smallest non-negative integer not found in the given set.

• Viewing the game as a graph, we can gradually calculate the Grundy values starting from vertices without outgoing edges.
• Grundy value being equal to zero means a state is losing.

Find the SG-values for the nodes of the following graph:

Find the SG-values for the nodes of the following graph:

At-Least-Half. Consider the one-pile game with the rule that you must remove at least half of the counters. The only terminal position is zero.

At-Least-Half. Consider the one-pile game with the rule that you must remove at least half of the counters. The only terminal position is zero.

We may compute the Sprague-Grundy function inductively as

x    0  1  2  3  4  5  6  7  8  9  10  11  12 ...
g(x) 0  1  2  2  3  3  3  3  4  4   4   4   4 ...

In closed form \(g(x) = \lfloor \lg x \rfloor + 1\).

At-Most-Half. Consider the one-pile game with the rule that you may remove at most half the chips. Of course, you must remove at least one, so the terminal positions are 0 and 1. Find the Sprague-Grundy function.

At-Most-Half. Consider the one-pile game with the rule that you may remove at most half the chips. Of course, you must remove at least one, so the terminal positions are 0 and 1. Find the Sprague-Grundy function.

We may compute the Sprague-Grundy function inductively as

x    0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15...
g(x) 0  0  1  0  2  1  3  0  4  2   5   1   6   3   7   0...

In closed form

\[ g(x) = \left\{\begin{array}{lr} x/2, & \text{for even x}\\ g(\lfloor x/2 \rfloor), & \text{otherwise}\\ \end{array}\right\} \]

Consider the one-pile game with the rule that you may remove c chips from a pile of n chips if and only if c is a divisor of n, including 1 and n. For example, from a pile of 12 chips, you may remove 1, 2, 3, 4, 6, or 12 chips. The only terminal position is 0. Find the Sprague-Grundy function.

Suppose the above rules are in force with the exception that it is not allowed to remove the whole pile. This is called the Aliquot game by Silverman, (1971). Thus, if there are 12 chips, you may remove 1, 2, 3, 4, or 6 chips. The only terminal position is 1. Find the Sprague-Grundy function.

The game starts with a pile of \(n\) stones, and the player to move may take any positive number of stones. Calculate the Grundy Numbers for this game. The last player to move wins. Which player wins the game?

• If there are no stones, the player loses. There is no reachable state from here. Therefore, the grundy value for this state is \(0\).

• If there is \(1\) stone, we can remove it and reach state with grundy value \(0\). \(mex(\{0\})=1\), hence this state has grundy value \(1\).

• If we have \(2\) stones, we can remove \(1\) or \(2\) to reach states with grundy values \(1\) and \(0\). \(mex(\{0,1\})=2\). Therefore, the grundy value of this state is \(2\)

• \(\ldots\)

• Since each state (except 0) can reach state \(0\), the first player always wins.

The game starts with a pile of n stones, and the player to move may take any positive number of stones up to 3. The last player to move wins. Which player wins the game?

• 0 \(\rightarrow \text{r:}\{\} \rightarrow \text{mex}(\{\}) = 0 \rightarrow \text{grundy}(0)=0\)
• 1 \(\rightarrow \text{r:}\{0\} \rightarrow \text{mex}(\{0\}) = 1 \rightarrow \text{grundy}(1)=1\)
• 2 \(\rightarrow \text{r:}\{0,1\} \rightarrow \text{mex}(\{0,1\}) = 2 \rightarrow \text{grundy}(2)=2\)
• 3 \(\rightarrow \text{r:}\{0,1,2\} \rightarrow \text{mex}(\{0,1,2\}) = 3 \rightarrow \text{grundy}(3)=3\)
• 4 \(\rightarrow \text{r:}\{1,2,3\} \rightarrow \text{mex}(\{1,2,3\}) = 0 \rightarrow \text{grundy}(4)=0\)
• 5 \(\rightarrow \text{r:}\{2,3,4\} \rightarrow \text{mex}(\{2,3,0\}) = 1 \rightarrow \text{grundy}(5)=1\)
• 6 \(\rightarrow \text{r:}\{3,4,5\} \rightarrow \text{mex}(\{3,0,1\}) = 2 \rightarrow \text{grundy}(6)=2\)
• 7 \(\rightarrow \text{r:}\{4,5,6\} \rightarrow \text{mex}(\{0,1,2\}) = 3 \rightarrow \text{grundy}(7)=3\)
• \(\ldots\)

The game starts with a number- \(n\) and the player to move divides the number with \(2, 3\) or \(6\) and then takes the floor. If the integer becomes \(0\), it is removed. The last player to move wins. Which player wins the game?

• 0 \(\rightarrow \text{r:}\{\} \rightarrow \text{mex}(\{\}) = 0 \rightarrow \text{grundy}(0)=0\)
• 1 \(\rightarrow \text{r:}\{0,0,0\} \rightarrow \text{mex}(\{0\}) = 1 \rightarrow \text{grundy}(1)=1\)
• 2 \(\rightarrow \text{r:}\{1,0,0\} \rightarrow \text{mex}(\{1,0\}) = 2 \rightarrow \text{grundy}(2)=2\)
• 3 \(\rightarrow \text{r:}\{1,0,0\} \rightarrow \text{mex}(\{1,0\}) = 2 \rightarrow \text{grundy}(3)=2\)
• 4 \(\rightarrow \text{r:}\{2,1,0\} \rightarrow \text{mex}(\{2,1,0\}) = 3 \rightarrow \text{grundy}(4)=3\)
• 5 \(\rightarrow \text{r:}\{2,1,0\} \rightarrow \text{mex}(\{2,1,0\}) = 3 \rightarrow \text{grundy}(5)=3\)
• 6 \(\rightarrow \text{r:}\{3,2,1\} \rightarrow \text{mex}(\{2,1\}) = 0 \rightarrow \text{grundy}(6)=0\)
• 7 \(\rightarrow \text{r:}\{3,2,1\} \rightarrow \text{mex}(\{2,1\}) = 0 \rightarrow \text{grundy}(7)=0\)
• 8 \(\rightarrow \text{r:}\{4,2,1\} \rightarrow \text{mex}(\{3,2,1\}) = 0 \rightarrow \text{grundy}(6)=0\)
• \(\ldots\)

• 9 \(\rightarrow \text{r:}\{4,3,1\} \rightarrow \text{mex}(\{3,2,1\}) = 0 \rightarrow \text{gr}(9)=0\)
• 10 \(\rightarrow \text{r:}\{5,3,1\} \rightarrow \text{mex}(\{3,2,1\}) = 0 \rightarrow \text{gr}(10)=0\)
• 11 \(\rightarrow \text{r:}\{5,3,1\} \rightarrow \text{mex}(\{3,2,1\}) = 0 \rightarrow \text{gr}(11)=0\)
• 12 \(\rightarrow \text{r:}\{6,4,2\} \rightarrow \text{mex}(\{0,3,2\}) = 1 \rightarrow \text{gr}(12)=1\)
• 13 \(\rightarrow \text{r:}\{6,4,2\} \rightarrow \text{mex}(\{0,3,2\}) = 1 \rightarrow \text{gr}(13)=1\)
• 14 \(\rightarrow \text{r:}\{7,4,2\} \rightarrow \text{mex}(\{0,3,2\}) = 1 \rightarrow \text{gr}(14)=1\)
• 15 \(\rightarrow \text{r:}\{7,5,2\} \rightarrow \text{mex}(\{0,3,2\}) = 1 \rightarrow \text{gr}(15)=1\)
• 16 \(\rightarrow \text{r:}\{8,5,2\} \rightarrow \text{mex}(\{0,3,2\}) = 1 \rightarrow \text{gr}(16)=1\)
• 17 \(\rightarrow \text{r:}\{8,5,2\} \rightarrow \text{mex}(\{0,3,2\}) = 1 \rightarrow \text{gr}(17)=1\)
• 18 \(\rightarrow \text{r:}\{9,6,3\} \rightarrow \text{mex}(\{0,0,2\}) = 1 \rightarrow \text{gr}(18)=1\)
• \(\ldots\)

Consider a game where you have to cut slices from a rectangular board. Each player, in her turn, cuts a slice either horizontally or vertically, with a thickness of \(1\). The player who has nothing left to cut loses the game. If you start with a \(5\times 5\) board, can you win?

• Start with \((0,0) \rightarrow 0\)

  • Actually, \((0,*) \rightarrow 0\) and \((*,0) \rightarrow 0\)

• Note that each state \((i,j)\) can be transitioned to one of states \((i-1,j)\) or \((i,j-1)\).

• We can quickly create a 2d-matrix of all states as follows:

      0   1   2   3   4   5
    -------------------------
  0 | 0 | 0 | 0 | 0 | 0 | 0 |
    -------------------------
  1 | 0 | 1 | 2 | 1 | 2 | 1 |
    -------------------------
  2 | 0 | 2 | 0 | 2 | 0 | 2 |    You will lose!
    -------------------------
  3 | 0 | 1 | 2 | 0 | 1 | 0 |
    -------------------------
  4 | 0 | 2 | 0 | 1 | 0 | 1 |
    -------------------------
  5 | 0 | 1 | 2 | 0 | 1 | 0 |
    -------------------------

• Consider a composite game of \(N\) sub-games and two players, \(A\) and \(B\).
• Sprague-Grundy Theorem says
  • The first player to play wins iff
    • Both players play optimally, and
    • The xor-sum of the grundy values of the current state of each sub-game is non-zero
  • Otherwise, if the xor-sum evaluates to zero, then the first player loses.

• SG theorem makes sense with our previous Nim conclusion
  • Consider each pile of a Nim game an independent sub-game
  • The first player wins if the xor-sum of the piles is non-zero
  • Same as saying the xor-sum of sub-games is non-zero

• Break a composite game into sub-games
• For each sub-game, calculate the grundy value for the current state
• Calculate the xor-sum of all
• If non-zero, claim victory!

Consider a game where you have to cut slices from a rectangular board. Each player, in her turn, cuts a slice either horizontally or vertically, with a thickness of \(1\). The player who has nothing left to cut loses the game. If you start with a \(5\times 5\) board, can you win?

• This time consider the two directions to be two separate nim games with 5 stones each.
• You can remove only one stone from one pile.
• For each game \(g(0) = 0, g(1) = 1, g(2) = 0, g(3) = 1, g(4) = 0, g(5) = 1\)
• The current player wins iff the xor-sum of the grundy values of the two games are non-zero.
• For the state of (5,5), you will lose, since the xor-sum is 0.

Consider a game of Nim on a single heap and with a subtraction set of \(\{1,3,4\}\). Analyze its Grundy values.

Consider a game of Nim where you start with three piles of stones having 1 million, 1 million and 1, 1 million and 2 stones. In one turn, each player is allowed to get at least 1 and at most 3 stones from a single pile. Will the starting player win?

• Last number is the number we are looking for
  • First game grundy values: 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3…, 0
  • Second game: 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3…, 1
  • Third game: 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3…, 2
• xor-sum of 0 (00), 1 (01), 2 (10) is non-zero (11)
  • the first player wins

Consider a game of Nim where you start with three piles of stones having 1 million, 1 million and 1, 1 million and 2 stones. This time you can get at most 1 stone from the first pile, at most 2 from the second pile and at most 3 from the third pile.

• Last number is the number we are looking for
  • First game grundy values: 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1…, 0
  • Second game: 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2…, 2
  • Third game: 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3…, 2
• xor-sum of 0 (00), 2 (10), 2 (10) is zero (00)
  • the first player will lose

Suppose in a game with a pile containing a large number of chips, you can remove any number from 1 to 6 chips at each turn.

• What is the winning strategy? What are the losing states?
• If there are initially 31 chips in the pile, what is your winning move, if any?

The Thirty-one Game. (Geoffrey Mott-Smith (1954)) From a deck of cards, take the Ace, 2, 3, 4, 5, and 6 of each suit. These 24 cards are laid out face up on a table. The players alternate turning over cards and the sum of the turned over cards is computed as play progresses. Each Ace counts as one. The player who first makes the sum go above 31 loses. It would seem that this is equivalent to the game of the previous exercise played on a pile of 31 chips. But there is a catch. No integer may be chosen more than four times.

• If you are the first to move, and if you use the strategy found in the previous exercise, what happens if the opponent keeps choosing 4?
• Nevertheless, the first player can win with optimal play. How?

The Thirty-one Game. (Geoffrey Mott-Smith (1954)) From a deck of cards, take the Ace, 2, 3, 4, 5, and 6 of each suit. These 24 cards are laid out face up on a table. The players alternate turning over cards and the sum of the turned over cards is computed as play progresses. Each Ace counts as one. The player who first makes the sum go above 31 loses. It would seem that this is equivalent to the game of the previous exercise played on a pile of 31 chips. But there is a catch. No integer may be chosen more than four times.

• You get out of 3s to repsond!
• Hint: Start with a 2!

Find the set of losing states for the following subtraction sets:

1. S = {1, 3, 5, 7}.

2. S = {1, 3, 6}.

3. S = {1, 2, 4, 8, 16,…} = all powers of 2.

4. Who wins each of these games if play starts at 100 chips, the first player or the second?

Empty and Divide. There are two boxes. Initially, one box contains m chips and the other contains n chips. Such a position is denoted by (m, n), where m > 0 and n > 0. The two players alternate moving. A move consists of emptying one of the boxes, and dividing the contents of the other between the two boxes with at least one chip in each box. There is a unique terminal position, namely (1, 1). Last player to move wins. Find all losing states.

Consider a game where a player is able to replace any heap of size \(k\) with up to \(k-1\) heaps of any positive size strictly less than \(k\). Prove that in this game, the Sprague-Grundy function of a heap of size \(k\) is \(0\) if \(k=1\), and \(2^{k-2}\) otherwise.

Consider a game on heaps, where a turn consists of taking a heap of size \(n\), and a positive integer \(d\) that divides \(n\), where \(1 \leq d < n\), and splits it into \(n/d\) heaps of size \(d\).

Analyze the Sprague-Grundy function of this game. (Try doing it with just the odd heap sizes first)