90 Chapter 7

7.5 Consider the modified version of the game Buckets of Fish, where on each turn a player may

take a fish from one bucket and then either add or remove as many fish as desired from any of

the buckets to the left. What is the winning strategy? Suppose that a player may add or take

away at most one fish from each of the earlier buckets. What then is the winning strategy?

7.6 Consider another modified version of the game Buckets of Fish, where on each turn a player

may take one, two, or three fish from a given bucket, and then add or remove any number of

fish to each of the buckets to the left. What is the winning strategy? And what if players can

take up to four, or up to five, and so on?

7.7 Consider a further modified version of the game Buckets of Fish, where on each turn a player

may take any positive number of fish from any given bucket and add any number of fish to

each of the buckets to the left. What is the winning strategy? [Hint: Would it be a good idea

for a player to leave the buckets in such a way that the leftmost two buckets have the same

number of fish, and also the next two, and the next two, and so on?]

7.8 Define and prove a sense in which the balancing strategy is the only winning strategy in Nim.

7.9 What is the winning strategy for mis

`

ere Nim? Prove your answer. [Hint: Prove that a move is

a winning move in mis

`

ere Nim if and only if it is a winning move in Nim, except in the case

that it leads to a position with all piles having only one coin.]

7.10 Suppose that we have a Gold Coin game position with pennies at positions n

0

< n

1

< ···< n

k

,

and a gold coin at position n. How many moves are in the longest possible legal play?

7.11 Give a complete analysis of the game of Chomp for a 3 × 2 chocolate bar. Would you rather

go first or second? What is the winning play?

7.12 Describe a winning strategy in the game of Chomp for a square chocolate bar n×n, with n > 1,

and prove that it is winning.

7.13 How large is the game tree for tic-tac-toe? Perhaps it is difficult to say exactly, but what are

the best upper and lower bounds you can prove? Does the game have certain symmetries that

allow you to understand the game with only part of the game tree?

7.14 How many nodes are there in the game tree of chess on the level after two moves for each

player?

7.15 Criticize the play of both players in the tic-tac-toe game illustrated in figure 7.1. Did the

winning player play well? On which move did the losing player go wrong?

7.16 Describe a natural version of three-dimensional tic-tac-toe, and prove that the first player has

a winning strategy.

Credits

Although forms of the game of Nim have reportedly been known since ancient times, the

mathematical analysis of the game is due to Charles L. Bouton (1901). The fundamental

theorem of finite games was proved by Zermelo in 1913.