Cut The Knot!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
The simplest game of all, the Endgame, has both option sets empty and is denoted
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
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 = {-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
Any move by Left leads to
A first move by Right leaves two options for Left:
This means that {0|1} + {0|1} + {|0} = 0, and meaningfully
Games can be compared. P > Q, provided the sum
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
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/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
Further on are obtained marvels like
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:
- The number replacing a given one must have strictly smaller denominator, or,
- 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 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
- E. R. Berlekamp, J. H. Conway, R. K. Guy, Winning Ways for Your Mathematical Plays, Volume 1, A K Peters, 2001
- J. H. Conway, On Numbers And Games, A K Peters, 2001
- M. Gardner, Mathematical Carnival, Vintage Books, 1977
- M. Gardner, Penrose Tiles to Trapdoor Ciphers, W. H. Freeman and Company, 1989
- D. E. Knuth, Surreal Numbers, Addison-Wesley, 1974
|Contact| |Front page| |Contents| |Algebra|
Copyright © 1996-2018 Alexander Bogomolny
72103938