Exercise Solutions

Problem Set Solutions

1. Suppose the game of rooks is played on a $10\times 8$ board instead of an $8\times 8$ board. What is the winning strategy? Is it better to be player $1$ or player $2$?

   

   Solution: Using backwards induction, we can see that the winning squares are as follows.

   

   Therefore, being player $1$ is the best strategy, since you can move to a winning square on the first turn.

2. Instead of the game of rooks, let us play the game of queens. The game starts off on an $8\times 8$ board with a queen on the square near the bottom-right of the board, as shown below.

   

   A queen piece can move in a single direction toward the top-left corner (up, left, or diagonal) for any number of squares in one turn. The objective is to move the queen to the opposite corner of the board from where it started. Using backwards induction, find out if it’s better to start the game as player $1$ or player $2$.

   Solution: If you move the queen to any of the red squares in the diagram below, you will lose the game, since your opponent can move the queen to the corner in one step. Therefore, you want to force your opponent to move the queen to one of those losing squares. The winning squares are highlighted in green.

   

   Therefore, it is better to start off as player $1$ and move the queen diagonally to a winning square in the first turn and win the game in exactly $3$ turns.

3. This question explores more scenarios of the logic coin game.

   1. There are 25 coins in a pile. On each turn, a player can remove $1$, $2$, or $3$ coins. The player that takes the last coin loses. What is the winning strategy? Is it better to be player $1$ or player $2$?

   2. There are 40 coins in a pile. On each turn, a player can remove $2$, $3$, $4$, or $5$ coins. The player that takes the last coin wins. What is the winning strategy? Is it better to be player $1$ or player $2$?

   3. There are 100 coins in a pile. On each turn, a player can remove $2$, $3$, $4$, or $5$ coins. The player that takes the last coin loses. What is the winning strategy? Is it better to be player $1$ or player $2$?

   Solution:

   1. In this scenario, the objective is to force your opponent to take the last coin. Therefore, there needs to be exactly $1$ coin remaining in the coin pile after your turn, forcing your opponent to take the last coin. This means that we need to remove the second last coin on our turn. Recall from the lesson that in order to take the last coin, the strategy is to keep the coin pile as a multiple of $4$. Therefore, in order to take the second last coin, the strategy is to keep the coin pile as “one more than a multiple of $4$”, or $4x+1$ after your turn, where $x$ is some integer $\ge 0$. Since we start off with 25 coins, which equals $4\times 6+1$ (satisfying our condition), being player $2$ will guarantee that you win the game. After your opponent removes some coins, make sure that the total coins removed by your opponent and you sum to $4$ every turn to keep the number of coins in the pile equal to $4x+1$.

   2. In order to take the last coin, there needs to be exactly $7$ coins remaining in the pile after your turn, since no matter if your opponent takes $2$, $3$, $4$, or $5$ coins, you can always take the last coin. The winning strategy is to always make the remaining pile of coins a multiple of $7$ after your turn finishes. Since there are $40$ coins initially, being player $1$ and taking $5$ coins on the first turn will guarantee a win (since $35$ is a multiple of $7$), as long as you keep bringing the coin pile to a multiple of $7$ after each of your turn (if your opponent takes 2, you take 5, if your opponent takes 4, you take 3, and so on).

   3. In this scenario, you want to force your opponent to take the last coin. Therefore, there needs to be exactly $2$ coins remaining in the pile after your final turn, so that your opponent will be forced to take the last two coins. Using backwards induction, the winning strategy is to always make the remaining pile of coins “a multiple of $7$ plus $2$”, or $7x+2$.

      The initial coin pile consists of $100$ coins, and since $100=7\times 14+2$, the coin pile already satisfies the condition. In this scenario, the winning strategy is to be player $2$. After your opponent removes some coins, simply make sure that you and your opponent combine to remove $7$ coins each turn, so that the remaining coin pile will remain as “a multiple of $7$ plus $2$”. Using this strategy, you will eventually bring the pile of coins down to only $2$ coins, which forces your opponent into a loss condition.

4. This question is an extension of the pirate game. Suppose that the rules are exactly the same as the pirate game in the lesson, but the only difference being that the proposer of the coin distribution plan does not have a casting vote. If the voting is a tie, then the proposer of that plan is thrown overboard.

   Suppose you are pirate A, the most senior of the five pirates. What coin distribution plan would you propose to split the $100$ gold coins?

   Solution: Let us use backwards induction once again. A reminder that each pirate will vote “yes” if the current proposal will gain them more coins than if they vote “no”, and vice versa.

   In the final vote where only pirate D and E are alive, pirate D will be thrown overboard no matter how much they offer pirate E. Since pirate D has no casting vote, pirate E will always vote “no” in order to kill off pirate D and keep all the coins for themselves. The payoff in this scenario would be D:$0$(death) and E:$100$.

   If there are three pirates left (C, D, and E), pirate C can predict that even if they give pirate D $0$ coins, pirate D will vote “yes” since he gets to survive, since if he votes “no” and pirate C gets thrown overboard, pirate D will certainly die in the next scenario. In this scenario, pirate C can simply keep all $100$ coins to themselves and gain the majority vote. The payoff in this scenario would be C:$100$ (vote for), D:$0$ (vote for), E:$0$ (vote against).

   If there are four pirates left (B, C, D, and E), pirate B can predict that pirate C will vote “no” in order to potentially get $100$ coins by voting pirate B off. In order to gain pirate D and E’s vote, pirate B needs to offer both pirates $1$ coin each and keep $98$ coins for themselves, since pirate D and pirate E knows that $1$ is better than $0$. The payoff in this scenario would be B:$98$ (vote for), C:$0$ (vote against), D:$1$ (vote for), E:$1$ (vote for).

   Finally, when we come to the current scenario, pirate A needs to gain $2$ votes to win as majority. In this case, pirate A can give $1$ coin to pirate C, and $2$ coins to either pirate D or pirate E to gain their vote. There are two possible distribution plans in this case:

   • A:$97$ (vote for), B:$0$ (vote against), C:$1$ (vote for), D:$2$ (vote for), E:$0$ (vote against) or

   • A:$97$ (vote for), B:$0$ (vote against), C:$1$ (vote for), D:$0$ (vote against), E:$2$ (vote for).

5. The calendar game is a $2$-player turn based game where players take turns writing down dates. The first player must begin with writing down January $1$^st. After this, the second player takes the previous date and may increase either the month or the day, but not both. For example, the next player can choose January $20$^th or June $1$^st, but not March $29$^th. The player who writes down December $31$^st wins. What is the winning strategy?

   Solution: Using backwards induction, if you write down November $30$^th, you will win, since the only options for your opponent is to write down December $30$^th (where you can increase the day by $1$ and win) or November $31$^st (where you can increase the month by $1$ and win). Going backwards from here, if you write down October $29$^th, you will be able to write down November $30$^th on your next turn. Continuing this pattern, you will win if you write down September $28$^th, August $27$^th, July $26$^th, June $25$^th, May $24$^th, April $23$^rd, March $22$^nd, Feburary $21$^st, or January $20$^th. You can write down January $20$ by being the $2$^nd player and increasing the day to guarantee a win.

6. Notakto is another $2$-player turn-based game played on a finite number of $3\times 3$ boards. It is a variation of tic-tac-toe, and both players play the same piece on the board (such as an “X”). Each player takes turns placing an X on the board(s) in a vacant space. If one player makes a three-in-a-row on a board, that board becomes “dead” and no more pieces can be played on that board. When one player makes a three-in-a-row and there are no more boards to play on, that player loses.

   For example, if the current state of the board is as follows and it is player $1$’s turn, player $1$ loses, since player $1$ cannot place down an X on a vacant spot without making a “three-in-a-row”.

   

   Try playing this game with a friend or a family member. Is there a winning strategy for

   1. $1$ board?

   2. $2$ boards?

   3. $3$ boards?

   4. $x$ boards?

   Solution:

   1. The optimal strategy for a single board game of Notakto allows player $1$ to force a win. By playing the first piece in the center of the board and playing a knight’s move (shown below) after your opponent takes a turn, you will guarantee a win on this board.

      

      Let us explore why the knight’s move is so powerful. After player $1$ plays the knight’s move, the possible moves for player two are highlighted in green in the image below.

      

      No matter which green X player $2$ chooses to place down (in green), player $1$ will always be able to force the board into a loss condition for player $2$. Here are player $1$’s next move (in blue) in each of the $4$ scenarios.

      

      Hide/Reveal Description of Game Boards

      Each game board has three black X's: one in the top row first column, one in the middle row second column, and one in the bottom row second colum. One green X and one blue X are also placed on each board as follows:

      1. The green X is in the middle row first column. The blue X is in the top row third column.

      2. The green X is in the bottom row first column. The blue X is in the middle row third column.

      3. The green X is in the middle row third column. The blue X is in the bottom row first column.

      4. The green X is in the top row third column. The blue X is in the middle row first column.

      ---

   2. Knowing that player $1$ always wins the first board, player $2$ has the winning strategy in the case of $2$ boards. Player $2$ should play their X in the center square of the empty board on their first turn. This allows player $2$ to strategically sacrifice the first board by making a three-in-a-row when possible. This reduces the game state to a single board game of Notakto, where player $2$ can reuse the knight’s move to win the game.

   3. Extrapolating from the case of $2$ boards, player $1$ now has the winning strategy. By sacrificing the first board in the same way as above (making a three-in-a-row on the first board), this reduces the game state to a two-board game of Notakto, player $1$ is now essentially “player $2$” in the two-board game state in part (b), and will be able to use the same strategy as above to win.

   4. For a game of Notakto with $x$ boards, if $x$ is odd, then the game will be won by player $1$. If $x$ is even, then the game will be won by player $2$. This method of extrapolation uses forwards induction instead of backwards induction, which is another useful tool in game theory.

7. If you have $30$ minutes to spare, visit the website here and play through the simulation game. This game uses elements of game theory to explore human psychology. In the lesson and problems, we always want to use the strategy that is most beneficial to us, many times at the cost of others. When we play games with other people, each with their own set of strategy, who will ultimately come out on top? This activity will explore these questions.