# Cut The Knot!

An interactive column using Java applets
by Alex Bogomolny

# Taking Games Seriously

April 2001

What may be said about the book whose preface opens in the following manner?

Does a book need a Preface? What more, after fifteen years of toil, do three talented authors have to add?

In twenty years since it first appeared Winning Ways for Your Mathematical Plays became a classic and a rarity. So did its companion book On Numbers And Games that was written in just about a week by one of the WW's authors and saw the light of the day five years earlier. The authors of course remained good friends.

There's more good news. Thanks to A. and K. Peters, both books are now in new editions. ONAG and the first volume of WW are already out. The remaining three volumes of WW are scheduled to appear over the year 2001.

How much do the books differ from their first editions? I can't give a comprehensive answer, but there are changes. One of the first pages in WW has a one paragraph introduction for each author accompanied by a reasonably sized likeness. So some changes are discernable to a naked eye, provided you have the first edition on hand to compare. The WW's authors claim to have expanded the Extras at the ends of the chapters, have inserted many references for further reading, and have corrected some of the one hundred sixty three mistakes left over in the first edition.

The new edition of ONAG offers an especially written prologue and an epilogue with an outline of the more important developments since the first edition. ONAG, however still ends with the same

### Theorem 100

This is the last theorem in this book.

whose proof is said to be obvious. As before, the book begins with Chapter 0 and, as before, the book is in two = {zero, one | } parts. Part 0 covers the notion of number, part one = {zero | } covers games. Some games are numbers, some are not. The games in question are played by two players -- usually Left and Right -- who make alternate moves. (WW has also material on one person games -- puzzles.) Games are described by positions. For each position P, rules of the game determine positions PL available to Left (Left options) and positions PR available to Right (Right options). Conversely, every position is completely defined by the options available to the players, which is concisely expressed as P = {PL | PR}.

The simplest game of all, the Endgame, has both option sets empty and is denoted 0 = {|}. In the normal play, the player with no options whose turn it is to move is declared a loser. So that in the game 0, the second player to move is a winner. In the game {0|}, Left has a legal move which ends the game, whereas Right has no move at all. In the game {|0}, the situation is reversed. Further notations that reflect the number of move advantages clearly favor Left. Thus, 1 = {0|} and -1 = {|0}. Regardless of who starts, Left wins the game 1, while Right always wins the game -1.

Naturally, 2 = {0,1|}, 3 = {0,1,2|}, and so on, and similarly for negative integers: -2 = {|0,-1}, etc. In general, a game is negative, positive, or zero, depending on whether Left, Right, or the second player has a winning strategy. Some games are neither. For example, the game * = {0|0} is a clear win for the first player. It's said to be fuzzy or confused with 0, but should not be confused with the subject of Fuzzy Set Theory.

The theory and practice of mathematical games often force the players to play several games simultaneously. This can be done in several ways (ONAG, Chapter 14). The most common is taking their disjunctive sum: the player to move selects a component game, and then makes a move legal in that game. For any game P, P + 0 = P. We may also check that * + * = 0. Indeed, a move by one of the players leads to * = {0|0}, which is a win for the other player. As another example, 1 + (-1) = {0|} + {|0} = 0, since a move by either player leaves the other player with a single winning move. In general, negation is defined inductively as

-P = {-PR | -PL},

which effectively reverses Left's and Right's options. Further, consider the game {0|1}, which is a clear win for Left and is thus positive, and the sum {0|1} + {0|1} + {|0}.

Any move by Left leads to {0|1} + {|0} with two options for Right. The winning option is to play the first game in the sum which leads to {0|} + {|0}, which is 0.

A first move by Right leaves two options for Left: {0|1} + {0|1} and {0|1} + {|0}. The winning strategy is to choose the first option, which leads to a positive (a win for Left) game {0|1}.

This means that {0|1} + {0|1} + {|0} = 0, and meaningfully {0|1} = 1/2. In a similar fashion, 1/4 = {0|1/2} and 3/4 = {1/2|1}. Other integers and dyadic fractions are similarly defined in a finite number of steps.

Games can be compared. P > Q, provided the sum P + (-Q) is positive. Numbers are defined inductively as those games P whose options are numbers with an added condition that no left option is greater than or equal to any right option. As there are no options to compare with, 0 is a number, as are all integers defined above and the dyadic fractions at whose creation we just hinted. The adopted notations reflect on the value associated with a game. Thus, for example, the game 1 is greater than the game 0.

A left option in a game is said to be dominated by any greater (or equal) left option. A right option is dominated by any smaller (or equal) right option. It can be shown that dominated options can be removed without affecting the game's value. In particular, the integer definitions are simplified to

n + 1 = {n|} and -n-1 = {|-n}.

It can also be shown that (2p + 1)/2n+1 = {p/2n | (p + 1)/2n}.

Other numbers (and games) are constructed out of dyadic rationals in an infinite number of steps similarly to Dedekind's cuts. For example, since 1/3 = 1/4 + 1/16 + 1/64 + ... and also 1/3 = 1/2 - 1/8 - 1/32 - 1/128 - ..., 1/3 is defined as

1/3 = {1/4, 1/4 + 1/16,1/4 + 1/16 + 1/64, ... | 1/2, 1/2 - 1/8, 1/2 - 1/8 - 1/32, ...}

In the same breath, we also get ω = {0, 1, 2, 3, ...|}. And, with this, more numbers like ω + 1 = {0, 1, 2, 3, ..., ω|}, or in fact ω + 1 = {ω|}, ω + 2 = {ω + 1|}, and so on. At the other end of the spectrum, 1/ω = {0|1, 1/2, 1/4, 1/8, ...}, {0|1/ω} = 1/2ω, ...

Further on are obtained marvels like ω - 1 = {0, 1, 2, 3, ...|ω} and w - 2 = {0, 1, 2, 3, ...|ω, ω - 1}, etc. and ω/2 = {0, 1, 2, 3, ...|ω, ω - 1, ω - 2, ...}, Öω = {0, 1, 2, ...|ω, ω/2, ω/4, ...}.

Little wonder the term surreal numbers coined by D. Knuth stuck around. Surreal numbers have been written about by M. Gardner and the term has been officially adopted in the second edition of ONAG.

So some games are numbers, while others are not. An additional classification distinguishes between partisan and impartial games. In the latter, exactly the same options are available to the two players. Examples of impartial games include Nim and its many dependents and incarnations: Scoring, Nimble, Northcott's game, Plainim, and more. Appearances notwithstanding, numbers (as defined above) do not appear as values of impartial games. Furthermore, numbers are also looked at condescendingly as options in the partisan games. The reason is that, in general, a number (in its simplified form) lies between its left and right options. So each player makes himself worse off by moving into a number. In WW, this fact appears as The Number Avoidance Theorem: DON'T MOVE IN A NUMBER UNLESS THERE'S NOTHING ELSE TO DO. In ONAG, numbers are simply regarded as the stopping positions. Once there, simply award the payoff to Left if the number is positive and to Right if its negative. Naturally, if a number is to be reached, Left will try to get its value as large as possible, Right will try to have it small.

But there is a value in trying. Practice. Beat your friends until they learned the game's secrets. Here's one example.

### Contorted Fractions

You are given several fractions that can be modified according to certain rules:

1. The number replacing a given one must have strictly smaller denominator, or,
2. If the denominator is already 1, it must have numerator strictly smaller in absolute value than that of the original number.

There are two players: Left and Right. A replacement is only legal for Left if it decreases the number, legal for Right only if it increases the number. You choose to be either Right or Left and may force your computer to go first by pressing You move button. All numbers in the game are modified by clicking a little off their center line. Clicking on the right increases the number, clicking on the left decreases it. To perform a move, select a fraction, adjust it to the desired value and press the I move button.

The game has two parameters. #Numbers is the number of fractions in a game. Max is the absolute maximum number that may appear in the numerator or denominator of a game.

### This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at https://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.

This game has a curious theory. The numbers that appear in the game are related to the game's value somewhat indirectly. First of all, it's clear that the game is the disjunctive sum of simpler games each consisting of a single fraction. Each of these, depending on the sign, are a one move win to either Left or Right. When several games are played simultaneously, Left will try to decrease the value of a fraction as little as possible, Right will try to increase its value as little as possible.

From position '2/5' Left can move to positions '1/3', '1/4', '-1/2', '0', '-2', etc., and Right can move to positions '1/2', '2/3', '3/4', '1', '10', etc. According to the above piece of wisdom, Left should choose '1/3', Right should choose '1/2'. Symbolically:

'2/5' = {'1/3' | '1/2'}.

What the players are looking for in that game, is the nearest approximation to a rational number by fractions with smaller denominators. These are given by the number's parents on the Stern-Brocot tree. Truly, solving this problem provides a student of fractions with plenty of practice.

A more sophisticated student may surmise that, as the parents are replaced by their parents, the binary encoding and continued fractions come into the play. Each Contorted Fractions game has only two undominated positions. Therefore, its value is necessarily a dyadic number. For a single fraction x, what is the value of the position 'x'? The answer is given by juxtaposing the binary encoding of x on the Stern-Brocot tree and what is known as Berlekamp's rule for interpreting Hackenbush strings (WW, pp. 77-78) or sign-expansions (ONAG, p. 31).

As an example, '(1 + Ö5)/2' = 5/3. Now a note for those who would like to pursue the matter further. In the first edition of ONAG, there is a remark on page 84 that refers to a note on page 96:

Note to p. 84: Some analytic properties of the function discussed on pp. 83-86 are established by J. G. Mauldon in Quart. J. Math. Oxford Ser., 17 (1966), p.261.

In the second edition, we read instead (p. 84) that the function is traditionally called "Minkowski's Question-Mark Function," and has interesting analytic properties. Talk about changes.

Writing about M. C. Escher [Carnival, p. 102] M. Gardner remarked:

When I first reproduced an Escher picture for my column for April, 1961 (and Scientific American ran one of his bird tessellations for cover), I purchased from Escher only one print, a woodcut. For mere \$40 to \$60 each I could have bought scores of pictures that now would each be worth thousands. But who could then have anticipated the astonishing growth of Escher's fame?"

In recent years I had similar regrets about several missed opportunities to purchase the first editions of WW and ONAG in 1970-80s. I am happy to own the books now. I am sure that, by supplying the demand, A. and K. Peters will see to it that the books will not fetch much more than their present cost. However, their worth lies elsewhere. The books show the side of mathematics usually missed by math textbooks. As the WW's authors wrote in the preface:

It is not a book on recreational mathematics because there's too much serious mathematics in it. On the other hand, for us, as for our predecessors Rouse Ball, Dudeney, Martin Gardner, Kraitchik, Sam Loyd, Lucas, Tom O'Beirne and Fred. Schuh, mathematics itself is a recreation.

I believe that to become a successful subject, this is how mathematics must be taught to young children -- as a recreation. For a curious and an attentive teacher, the books, especially WW, go a long way to suggest how is this possible. It's about time that mathematical games be given a serious consideration by curriculum developers.

### References

1. E. R. Berlekamp, J. H. Conway, R. K. Guy, Winning Ways for Your Mathematical Plays, Volume 1, A K Peters, 2001
2. J. H. Conway, On Numbers And Games, A K Peters, 2001
3. M. Gardner, Mathematical Carnival, Vintage Books, 1977
4. M. Gardner, Penrose Tiles to Trapdoor Ciphers, W. H. Freeman and Company, 1989
5. D. E. Knuth, Surreal Numbers, Addison-Wesley, 1974