Nuclear Pennies Game: Analysis

And now, for the promised analysis of the Nuclear Pennies Game!

First, recall the rules of the game: there is a semi-infinite (i.e. with a beginning but no end) strip of squares, each of which can contain a stack of any number of pennies (or no pennies at all). You are allowed to “split” a penny by replacing it with two pennies, one in the square on either side. This rule can also be run in reverse; two pennies separated by exactly one space can be “fused” into a single penny on the middle square.

We saw how to get from a single penny on square #7 to a single penny on square #1. However, I claimed that it is impossible to move a single penny from square #7 to square #2. Let me show you why.

We’re going to start by doing something that might seem a bit odd, but you’ll see why soon enough. We’re going to label the nth square with $x^n$ . Like this:

(Remember, $x^0 = 1$ .) Now, we will think of the number of pennies on a given square as being multiplied by the appropriate power of x. That way, every configuration of pennies is represented by a polynomial. For example, if there are three pennies in square #0, two pennies in square #2, and one penny in square #5, we would represent that by the polynomial $3 + 2x^2 + x^5$ .

Now, here’s the key idea: we want to pick a value for x so that two polynomials have equal values if they represent penny configurations that you can convert between while only making legal splitting and fusing moves. If we can do that, all you need to do to see whether it is possible to move from one configuration to another is to write down their polynomials, plug in the magical value of x, and see if they are the same!

So, how can we find this magical value of x? Well, let’s suppose we start with a single penny on square #1. That would be represented by the polynomial $x$ . By the splitting rule, we can replace this with a penny on square #0 and a penny on square #2, giving us the polynomial $1 + x^2$ . We want these polynomials to have the same value, since we can convert between them with a legal move, so we must have $x = 1 + x^2$ . Now, what if we had started with a penny on, say, square #4 and applied the splitting rule? In that case we would have $x^4 = x^3 + x^5$ … but that’s really the same thing as $x = 1 + x^2$ , since we can just divide both sides by $x^3$ (assuming that x is not zero). The same goes for any starting location, so the equation $x = 1 + x^2$ covers all possible applications of the splitting rule. What about the fusion rule? Well, remember, the fusion rule is really just the splitting rule backwards, so it gives us the exact same equation.

So, both rules can be summed up by this single equation: $x = 1 + x^2$ . All we have to do is solve it to find our magical value of x. Well, using the quadratic formula, that’s not hard: we get $x = 1/2 + i\sqrt{3}/2$ . Aha, a complex number, just as I promised!

Now, if it were possible to move a single penny from square #7 to square #2, then we would have $x^7 = x^2$ , which is the same as $x^5 = 1$ . Well, is that true? It turns out that it isn’t, as you can verify for yourself — so, moving a single penny from square #7 to square #2 isn’t possible! In fact, the smallest power of x for which $x^n = 1$ is 6. x, in fact, is one of the complex sixth roots of 1. So if you want to start with a single penny and move it somewhere else, you can only move it by six squares at a time!

The Nuclear Pennies game is originally from Dan Piponi at A Neighborhood of Infinity (from whom I also stole a lot of the nice pictures), who based it on the ideas in the paper Seven Trees in One, by Andreas Blass. The mathematically intrepid might want to try reading some of the original paper, which is really quite excellent — but the content of the paper is way deeper than what I’ve written about here, so don’t be discouraged if you don’t understand a lot of it (I don’t understand the entire second half of the paper!). Just trying to give credit where credit is due.

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →

3 Responses to Nuclear Pennies Game: Analysis

George Bell says:

November 5, 2007 at 1:28 pm

It seems to me the same argument proves something more general, suppose you begin with ANY number of pennies on a single square. Then you ask the question, can I make moves that place all the pennies again in a single pile, anywhere else? The answer is that you can only do this at a square which is a multiple of 6 away from the original, and the number of pennies in the final pile must be the same as that in the original.

Also I don’t quite see any reason for making the board semi-infinite, why not just make the board infinite in both directions, and use negative powers of x. At least then you never have to worry about “running into the edge of the board”.

Did Andreas Blass come up with this game? I have scanned through the paper, and I didn’t see a specific mention of the game, although it is there in abstraction. Or did Dan Piponi (A Neighborhood of Infinity author) come up with the game?
Brent says:

November 5, 2007 at 3:41 pm

George, you’re absolutely right, it does prove that more general result! There are a lot of details I left out — including that one — trusting my readers to come to their own conclusions. =)

Dan Piponi came up with the game; however, as you saw, he based it on the ideas in Blass’s paper.

For the purposes of the Nuclear Pennies game, you’re absolutely right, you could do exactly as you suggest: make the board infinite in both directions and use negative powers of x in the analysis. This is actually an interesting point, and it means that my analysis above actually has a small technicality which I’ve swept under the rug: I showed that $x^6 = 1$ , but if you interpret this in terms of board positions, you’ll see that this actually isn’t true, because the left edge of the board means you can’t move out of the “1” position (i.e. a single penny in square #0)!

Blass’s paper is really about binary trees: a binary tree is a structure which is either empty, or has a single node with two children which are binary trees. If we represent the set of all binary trees by the letter T, we have $T = 1 + T^2$ — that is, the set of binary trees T contains the empty tree (1) along with all possible pairs of binary trees (T^2). You can see how this corresponds to the fission/fusion rules and the equation $x = 1 + x^2$ . However, in the context of binary trees (and sets/types in general), negative powers of T are meaningless, which is why the nuclear pennies board is only semi-infinite — that way it is a useful tool for understanding isomorphisms of trees! I don’t know if that makes sense but if you’re interested, I would suggest reading the beginning of Blass’s paper.
Steve Gilberg says:

November 5, 2007 at 4:51 pm

“There are a lot of details I left out — including that one — trusting my readers to come to their own conclusions. =)”

You’re like a kind older brother at an Easter egg hunt deliberately missing an egg for a younger sibling to find.