Conway’s Game of Coinage

It was a long time before I talked to Professor Emeritus John Boardman. I’d seen him walking in the halls before, sure. Wisps of white hair ran across the top of his high forehead, and he walked with a stoop. Sometimes his eyes appeared pried too far open, as if he were struggling to look ahead despite the downward incline of his head. He had a habit of incessantly clearing his throat, even as he walked, and even as he sat in his office; his office was adjacent to the math help room and I often looked up from an undergrad’s work only to notice the familiar sound again. I’d never seen anyone else talk to him, either.

This changed one evening as we all sat down for dinner in a sparsely patronzied restaurant after an invited speaker’s seminar talk. There were about six or seven of us at the table, and the others quickly became distracted in conversation. Professor Boardman, alone at the end of the table, sat to my left.

The first thing I noticed was his sharp, almost Russell-esque British accent. I had had no idea he was British. His voice was so quiet and thickly accented I had to strain to hear it. None of the others could hear him, and our conversation became separate from theirs. I could scarcely believe he was speaking! I don’t remember how the conversation started.

Professor Boardman told me that he had gone to Cambridge in the 1960s, where he had been a fellow graduate student of John Conway. Conway is most famous for Conway’s Game of Life, a “game” played on a grid in which complex patterns unfold in unpredictable ways. Conway, as it turns out, invented many games during his student days, many of which are much less known. As I struggled to hear Boardman’s voice in the dim restaurant, I was shocked to hear unfold the details of many other games, all different and just as entertaining.

In one game, called the Probability Merchant, a merchant fields customers who present probabilities between zero and one. Though each such request can be met with some collection of heads and tails events whose probability approximates the desired one, the merchant’s task is to design a (possibly unfair, or uneven) coin — which Conway called “the most efficient coin” — for which these requests can be met using as few flips on average as possible. (The solution coin is not fair!) In Auditory Numbers, an initial number leads to a sequence of replacements via a rule in which numbers are spoken out loud: 1227 becomes 112217 which becomes 21221117, and so on. Remarkably, Conway determined that given any such sequence, the ratios between successive numbers converge to a fixed number, and that, astonishingly, this asymptotic ratio does not depend on the number you start with!

I’ve since learned that many, in fact hundreds, of mathematical games are collected and described in a massive four-volume book written by Conway and the mathematicians Elwyn Berlekamp and Richard Guy, Winning Ways for your Mathematical Plays [1].

One game Professor Boardman described to me particularly stuck out. This game, I’ve also since learned, is called Sylver Coinage, named by Conway after the mathematician James Joseph Sylvester, who, long ago, studied a certain basic fact pertaining to the game — and who, incidentally, founded the John Hopkins mathematics department as its first professor.

Here’s how Sylver Coinage is played. Players take turns playing a positive integer, effectively minting a “coin” with that number as its value. The stipulation is that each coin must not be payable in change using coins which have already been played. The minting of the coin (1) ends the game, of course, and the player who plays (1) loses. For example:

  • Ben: (2)
  • Josh: (3)
  • Ben: (1)

Ben has learned that playing a (2) on the first move is a poor idea. Josh can, after all, immediately play a (3). This is bad news for Ben. In fact, every positive integer other than 1 can be paid out using a combination of (2)s and (3)s. (If it’s even, it’s trivially payable by (2)s; if it’s odd and greater than 1, subtract three from it and pay the rest using (2)s.) Playing a (3) on the first move would be a poor idea for the same reason.

Let’s try again:

  • Ben: (5)
  • Josh: (4)
  • Ben: (6)
  • Josh: (7)

This again, though, is bad news for Ben. In fact, all numbers greater than 7 are payable using the coins (4), (5), (6), and (7). This leaves (2) and (3) available, but we’ve already seen that both of these end in defeat.

Sylver Coinage has been analyzed extensively. Hutchings has proved that winning continuations exist when the first player begins with a prime greater than or equal to 5, though it’s not known what these winning strategies are. Winning responses are known to a handful of losing openings. [W, Vol.3, p. 609]

I’ll spare the reader the details of the analysis, directing him instead to Winning Ways. I will, however, prove one fact, one which I found very striking that evening at the restaurant, and the first one which Conway proved during his days at Cambridge: Every game ends after finitely many steps. This is a very fascinating, and pretty fact. I’ve come up with a somewhat detailed proof; this supplements the outline Conway gives in his book [W, Vol. 3, p. 611].

I’ll start with some preliminaries. What is the relationship between the quantities payable by a collection of coins and those payable by these coins’ greatest common divisor? Denote by (c1), …, (cn) the values of some collection of coins, and let dn denote these coins’ greatest common divisor. (I’ll generally place coin values in parentheses.) Of course, any value payable by some combination of the coins (c1), …, (cn) can be paid for in copies of their greatest common divisor dn. This is true because since dn divides each of (c1), …, (cn), it must also divide all of their combinations. (For example, given coins (6) and (10), the combination 2·(6) + 1·(10) = 22 can be paid for using 11 copies of their greatest common divisor, 2.)

Can any multiple of the greatest common divisor be paid for using the original coins? This reverse question is true if we permit negative coefficients. (The coins (6) and (10)’s greatest common divisor 2 can be paid for, if we allow the partially negative combination 2(6) – 1(10).) The game forbids negative coefficients, though, and when we restrict to non-negative ones certain values will become unpayable. (The number 2 obviously can’t be paid using non-negative combinations of (6) and (10). Neither can 12, for that matter, even though it’s bigger than both 6 and 10, although the partially negative combination 3(10) – 3(6) exists, of course.)

Given coins (c1), …, (cn) on the table, it almost makes sense to think of dn as a “virtual coin”. Our above discussion shows that this replacement isn’t perfect. Though any combination of coins can be replaced by some multiple of their greatest common divisor, the reverse isn’t true provided that we demand coefficients be non-negative. The tough part will be the exact nature of this restriction. When we restrict to non-negative combinations, how many numbers go off the table? The answer will be only finitely many. This will be key to our proof.

Lemma (Sylvester). Given relatively prime numbers a and b, any number c greater than or equal to (a – 1)(b – 1) can be paid for using non-negative combinations of the coins (a) and (b).

Because a and b are coprime, as y ranges through 0, …, – 1 the remainders of the successive differences (c – yb) mod a attain the full range of values 0, …, a – 1 (though generally not in order). Choosing the y’ for which the remainder is 0, we have (c – y’b) = xa, and thus c = xay’b. Clearly y’ is non-negative, and furthermore

xa = c – y’b ≥ (a – 1)(b – 1) – (a – 1)(b) = –a + 1

which shows that x ≥ 0. (A symmetric proof can be achieved by subtracting copies of a.)

levelsets

Intersections of these level sets with the integer grid correspond to non-negative combinations of coins.

There’s another proof I’ve come up with, which illustrates this fact somewhat geometrically, though it establishes only the more modest bound ab. The idea is to realize that if we set up the function f(x,y) = ax + by, associating to each point (x,y) its value f(x,y) corresponds to associating to each combination consisting of x (a)s and y (b)s the total value of the combined coins. The catch is that the coordinates x and y need not be non-negative integers; studying when exactly they are will be key for our proof.

Indeed, call the first quadrant the locus where both coordinates are non-negative, and the integer grid the locus where both coordinates are integers.

Each level set f(x,y) = c of this function corresponds to all the various ways of producing c using combinations of (a) and (b). A combination using non-negative integers, now, is nothing more than an intersection of such a level set with an integer grid point in the first quadrant. For which c do such intersections exist?

Such intersections certainly exist for the level set f(x,y) = ab, namely at the points (x,y) = (b, 0) and (x,y) = (0, a). Moreover, on any fixed level set grid points are always to be found at this same distance apart from each other. Indeed, any integer representation can be transformed to another by replacing a (b)s with b (a)s, or by, in other words, traversing along the level set a distance of √a² + b².

Finally, for any c ≥ ab, the intersection of the level set f(x,y) = c with the first quadrant has length greater than or equal to √a² + b². An integer point on this segment can’t help but exist.

Theorem  (Conway). Any game of Sylver Coinage will end in finitely many steps.

The idea is to extend Sylvester’s lemma to the case of n not-necessarily-coprime coins, demonstrating that, for any fixed finite collection of coins, only finitely many multiples of these coins’ greatest common divisor can’t be paid for using combinations of these coins. This shows that only finitely many coins can be played before the standing greatest common divisor drops. This itself can occur, finally, only finitely many times.

Let (c1) be the value of the first coin played. Trivially, only finitely many (in fact zero) of d1‘s multiples cannot be paid for using c1.

In fact, suppose that after turn n, among the positive multiples of the greatest common divisor dn of the coins (c1), …, (cn) played thus far, only finitely many cannot be paid for using the coins (c1), …, (cn) themselves. Consider a new coin played, (cn+1). I’ll handle two cases:

cn+1 is divisible by dn. In this case, the greatest common divisor dn+1 = dn, and the set of multiples of dn unpayable by (c1), …, (cn) strictly contains the set of multiples of dn+1 unpayable by (c1), …, (cn+1). Because we assumed the former number finite, the latter number is too, and in fact it’s smaller.

cn+1 is not divisible by dn. In this case, by an associative property the greatest common divisor dn+1 of (c1), …, (cn+1) can be written as the greatest common divisor of the two numbers dn and cn+1. By the inductive hypothesis, we may suppose that there’s some finite kn such that every multiple kdn of dn satisfying k ≥ kn can be paid for in (c1), …, (cn). I claim that defining kn+1 = lcm(dn,cn+1)/dn+1 + kndn/dn+1, any multiple kdn+1 of dn+1 satisfying k ≥ kn+1 can be paid for in (c1), …, (cn+1). Take any such k. Then kdn+1 – kndn ≥ lcm(dn,cn+1), and by (the weakened form of) Sylvester’s lemma (with everything scaled by dn+1), the left hand quantity is expressible in (virtual) coins qdn+1 – kndnxdn + ycn+1 with xy non-negative. Adding kndn to both sides, we produce an expression for the desired quantity kdn+1 = (x+kn)dnycn+1, where, in particular, the coefficient (x+kn) of dn satisfies xkn ≥ kn. By the inductive hypothesis, (x+kn)dn has an expression in the coins (c1), …, (cn). This gives an expression for kdn+1 in the coins (c1), …, (cn+1). This completes the inductive step.

Consider the sequence of greatest common divisors d1, …, dn, …. The proof shows that though the value need not drop each time, it may remain constant at most finitely many times in a row before dropping. Let e1, …, en … denote the sequence of distinct greatest common divisors. We have a chain of strict divisibilities

en | … e2 | e1

where the symbol | means “strictly divides”. Such a chain can only continue for finite length, because each number’s prime factorization is finite, and must eventually end in (1). This completes the proof.

All this brings to mind a comment made during a talk by the Stanford mathematician Persi Diaconis, who has become famous for finding deep connections between, on the one hand, the probabilities that certain numbers will appear during the carrying process associated with adding integers and, on the other, the dynamics of shuffling cards. Diaconis became interested in this topic while reading a recreational mathematics magazine. “Find a topic you’re truly interested in, however unassuming it seems,” Diaconis said. “Then go with it.”

  1. Winning Ways for your Mathematical Plays, with bibliographic information on all 4 volumes.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s