Swine in a Line

Last month I launched a venture similar to Mathematical Enchantments: a YouTube channel called Barefoot Math. The first few videos are about a game I invented called Swine in a Line. The rules are easy to state but the winning strategy is not easy to find, and the challenge I posed is to find that strategy. In the videos, and in this essay, I explain the strategy and I explain how a person might figure it out. It’s a story about how numbers, and the ways we represent them, can turn out to be relevant in surprising ways. I’ll also sketch how the game relates to a hot topic called the abelian sandpile model. Finally, I’ll connect the Swine in a Line game to James Tanton’s exciting way to make pre-college math vivid through his device of “Exploding Dots”, which will be the subject of Global Math Week later this year.

THE RULES

The easiest way for you to learn the rules is to watch the first Barefoot Math video.

 

 

 

 

 

 

 

 

 

But here are the rules written out for those of you who can’t (or don’t want to) watch the video:

The game starts with nine pens, some containing a pig and some not. Two players take turns putting pigs into pens. When it’s your turn you can either put a pig into an empty pen, in which case your turn ends then and there, or you can put a pig into a pen that already has a pig in it, in which case something interesting happens: one of the pigs in the pen jumps one pen to the left, and the other jumps one pen to the right. This doesn’t count as a separate turn; it’s just a consequence of the player’s choice to put a pig into a pen that already had a pig in it. If the jumps cause another pen to have two pigs in it, then those pigs jump as well. As long as there’s a pen with two or pigs in it somewhere on the board, the player has to keep doing these one-pig-goes-left, one-pig-goes-right moves. There’s an exception for the pens on the two ends: When a pig jumps to the left from the pen on the far left, or jumps to the right from the pen on the far right, then that pig just goes back to wandering in the field. The chain reaction continues until every pen has at most one pig in it.

After all the consequences of your move have played themselves out and the pigs have jumped their last jump, it’s time for your opponent to make a move, which (if your opponent chooses to put a pig in a pen that’s already occupied) will result in another chain reaction which also will eventually settle down. And then you make another move, which may or may not cause a chain reaction. And so on.

This process goes on until someone makes a move that leads to there being exactly one pig in each pen, and then the player who made that move wins.

It’s helpful to distinguish between stable configurations (in which every pen contains at most one pig) and unstable unconfigurations (in which at least one pen contains more than one pig). When the configuration is unstable, stabilization (“left, right”) must be carried out until stability is achieved, and only then does the other player get to move.

In the video, I showed a chain reaction that settled down and confidently asserted that in every situation where you put a pig in an occupied pen, the resulting chain reaction will eventually settle down. A reader of a skeptical cast of mind might be inclined to wonder how I can be so sure that stability is eventually achieved. Isn’t it possible that a chain reaction might go on forever? If you’ve played the game a dozen times, and you’ve seen how these chain reactions die out, you might be pretty convinced that an infinite loop can’t happen. But conviction based on experience is different from the sort of satisfying certitude mathematical reasoning can give us. See Endnote #1, which gives arguments to satisfy the rightfully skeptical.

Likewise, you might worry that the players will take turns forever without either of them achieving victory. Couldn’t this be one of those pointless games where neither player can win but each can prevent the other from winning? See Endnote #2 for more on this.

THE TRICK

The next video offered a clue about the nature of the strategy for winning the game. The numbers that mark the pens aren’t just handy labels — they’re part of the winning strategy.

 

 

 

 

 

 

 

 

 

 

The key to winning is to attend to the sum of the values of the pigs, where the value of each pig is the number written above its pen.

The idea of a token having a value that depends on its position is a powerful one. It forms the basis of the Hindu-Arabic way of writing numbers, and in particular, the calculation device called an abacus. When I used that word, the image that probably sprang into your mind was the Chinese-Japanese abacus, in which beads slide along rods, but older kinds of abacus (such as the Roman abacus) used counters in grooves, and are more similar to Swine in a Line inasmuch as the abacus counters aren’t constrained to stay in one groove.

The pigs have their own positional system, where the value of a pen is the number I’ve written above the pen. So if an unstable configuration has a pig in pen 2, two pigs in pen 7, and a pig in pen 9, the value of the configuration is 2 plus 7 plus 7 plus 9, or 25. (Pigs that are out in the field don’t contribute to the value of a configuration; if you like, you can say that they have value 0.)

Why should this contrived way of assigning value to configurations be useful? It’s because the sum of the values of the pigs (or rather, the last digit of that sum) is what physicists would call a conserved quantity. More specifically, when you do the “left, right” stabilization operation that sends one pig to the left and another pig to the right, the last digit of the value of the configuration doesn’t change; that is, the value of the (unstable) configuration that you see before you do the stabilization is the same as the value of the configuration that you see after you do the stabilization. (See Endnote #3.) It doesn’t matter how many “left, right” operations are required to turn an unstable configuration into a stable one; after the chain reaction ends, the last digit of the value is the same as it was before the whole chain reaction started.

Probing complexity in search of hidden patterns — things like conserved quantities — is a chief activity of mathematicians working at the frontiers. Hidden patterns are handholds that help us ascend to heights that our puny human brains were never evolved to take us to. In this particular instance, the last digit of the sum of the locations of the pigs is the key to winning the game.

 

 

 

There’s a style of writing about math puzzles that imitates the style of stage magicians, and strives to elicit feelings of awe through a canny balance between what is revealed and what is not. If I were presenting Swine in a Line in that style, I’d present the idea of looking at the last digit of the sum of the positions of the pigs in the manner of a magician pulling a rabbit out of a hat, as a decontextualized object of wonder. (I’m not entirely innocent of engaging in this style of exposition; I call the idea a “trick”.) Two things bother me about this approach. The first is that we miss out on the opportunity to point out unifying principles of mathematics, such as the conserved quantities that often underlie complicated processes. But my deeper complaint is that when solutions to puzzles are waved in front of an audience’s face like a card at the climax of a conjurer’s trick (“Is this your card, sir?”), the unfortunate take-home for some readers may be you can’t do math, at least at the highest levels, because a real mathematician would just see things like this instantly.

THE PATH

Mathematicians by and large aren’t people who see things like this instantly (though sometimes they do solve a problem with impressive rapidity if it resembles one they’ve seen before). Mathematicians are people who like solving problems, and have the persistence to work on problems that take time to solve, and have collected a tool-kit of methods that have helped them solve problems in the past. Some mathematicians distinguish between methods and tricks. A method is a tool that solves more than one problem, while a trick is a tool that applies to only one. Under this definition, I’d say that there are no tricks in math, and part of the discipline of getting good at math is to study every trick you encounter until you see the method hiding inside it.

That’s the philosophy I adopted in making the fourth video. I wanted to demystify the process of solving the puzzle by showing how, through persistent probing, one might arrive at the solution.

 

 

 

 

I cheated a little, because I said things like “If you experiment a bit, you’ll find that the only winning move is to put a pig into pen 7” (when pens 3 and 4 are empty and every other pen has one pig in it). How do we know this? Ideally there’d be a way to drill down on assertions like this to get more details about what that process of experimentation would look like. And that process would itself have sub-components you’d want to be able to drill down on. The resulting video would be extremely long.

Maybe the right way to demystify mathematical problem solving is to show actual people doing it. That’s the approach that Mike Lawler takes in his Family Math sequence of videos. I urge you to check out the videos Mike made, showing how his kids tackled the problem in their own way; see the links at the end.

THE SOURCE

Part of what inspired me to come up with this game was a Numberphile video on a topic close to my heart: the abelian sandpile model.

 

 

The abelian sandpile model is a game played with tokens, real or imagined, that you slide around on a diagram, from one location to another. That’s admittedly vague, but the Numberphile video makes the rules clearer. In the video, mathematician Luis David Garcia-Puente uses numbers instead of tokens, but you should think of an array like this:

3 3 3
3 4 3
3 3 3

as representing a picture like this:

The rules of the “game” are that when a location has four or more tokens (or chips or counters or whatever you want to call them), you must dispatch a chip to each of the four neighboring locations (with special provisions for what happens to chips that get off the edge of the board). This is called “firing”. For the picture I just drew, there are four chips in the middle, so when we fire those chips (some would say: “when we fire in the middle”), we get this:

Except now that we have some new locations that need to be stabilized. This is just like Swine in a Line, except that it’s two-dimensional instead of one-dimensional.

The Numberphile video talks about the curious arithmetic you get when you do the abelian sandpile model on a square board. Garcia-Puente focusses on a 3-by-3 square. It’s natural to generalize from squares to rectangles, and then to specialize from rectangles-in-general to rectangles of height 1. In particular, if the board is 1 by 9, then the sandpile group is just modular arithmetic with the modulus 10, otherwise known as “just look at the last digit” arithmetic or “clock arithmetic if there were ten hour-marks instead of twelve” arithmetic; the topic is familiar to many people as a side-tour in their pre-college mathematical education. This link between the sandpile model and school math seemed like too good a connection to let languish in obscurity. I wanted to spread the word.

That’s how I came up with Swine in a Line. I wanted a game that would hinge on the fact that the sandpile group for a 1-by-9 rectangle is mod 10 arithmetic. I knew what the winning strategy was going to be; all that remained was to invent the rules of play.

THE PROJECT

Modular arithmetic is good fun, but as I mentioned, it’s usually presented as a side trip on the road that leads up to college mathematics. More central are things like decimals and polynomials and whatnot. You might suppose that playing games with tokens has little to teach us about these more advanced topics. But you would be wrong, and mathematician James Tanton has made it his goal to show you just how far you can go with these games. He’s the mathematician/teacher/educator who came up with the Exploding Dots approach to arithmetic and algebra.

I’ll let Tanton explain Exploding Dots himself, since he does it so well in his videos (see the links at the end). In the last of my Swine in a Line videos, I discuss a variant of the game (the “one goes left, one goes out” version) that ties in with the binary system of representing numbers used by most computers and some humans. In this version, we have a different way of dealing with overcrowded pens. When a pen has two pigs in it, one goes left and one goes back out into the field. This variant has a “sudden death” rule: if the game ever reaches a configuration in which there are two pigs in the leftmost pen, the player responsible for making that happen loses instantly. The winning strategy hinges on a mathematical/visual pun: an arrangement of pigs can be read as a binary number if the presence of a pig is recorded as a 1 and the absence of a pig is recorded as a 0.

 

That’s the “one goes left, one goes out” variant of Swine in a Line (as opposed to the original “one goes left, one goes right” version). We could also play a “one goes left, nine go out” variant: as soon as there are ten or more pigs in a pen, one goes to the left and nine go back into the field. This would lead us to the ordinary base ten way of representing numbers.

THE MORAL

What I hope you take away from this essay is a sense that there’s an interestingly tangled relationship between games, numbers, and the devices we use for representing and manipulating numbers. The abacus was introduced as a way to represent and manipulate numbers for purposes of counting. On the other hand, we can play games with an abacus (the Swine in a Line games) that don’t immediately seem to be about numbers at all, but if we play with those games for long enough, we come to see that underlying the chaos of one configuration giving rise to another, and then another, there is a pattern, and this pattern is most naturally expressed in the language of number.

Thanks to John Golden, Sandi Gubin, David Jacobi, Mike Lawler, Shecky Riemann, James Tanton, and Glen Whitney.

Next month: Prof. Engel’s Marvelously Improbable Machines.

ENDNOTES

#1: One way to see that the stabilization process can’t loop is to use monovariants. Unlike invariants (another name for conserved quantities), which can’t change at all, monovariants can change, but only in one direction. An example of a monovariant is the number of pigs on the board: during stabilization, pigs can leave the board but they can’t be added to it, so the number of pigs is monovariant: it can decrease but it can’t increase.

Less obviously, during those periods of time when no pigs are leaving the board, the “spread” of the set of pigs on the board (as measured by the population variance of the set of locations) can only increase. This last sentence may seem obscure, so let me drop statistical language and use a related but algebraically simpler monovariant: the sums of the squares of the locations of the pigs. When we replace two pigs in location k by a pig in location k-1 and a pig in location k+1, the sum of the squares of the locations of the pigs goes up by exactly 2. (Check it: (k-1)² + (k+1)² = 2k² + 2.)

As the firings occur, the sum-of-squares monovariant keeps increasing by 2, but this can’t go on forever (for one thing, if there are m pigs currently on the board, the sums of the squares of the pigs can’t exceed m times 9²). So at some point, either there’ll be no more firings possible or a pig will go off the board. At that instant, the sum-of-squares monovariant will not necessarily be larger than it was before, but the more basic number-of-pigs monovariant will decrease.

I think you see where this is going: the number of pigs can’t keep dropping indefinitely (after all, it can’t be negative), so sooner or later the whole process has to stop. That means that it can’t get into an infinite loop.

#2: How do we know the game will ever end? Well, it doesn’t have to! If the two players want, they could keep making bad moves, even when victory is just one move away. But it can be shown that one player has a way to force the game to end, with himself or herself as the victor. See Endnote #6 for more about this.

#3: Why doesn’t the last digit change when all the firings happen? Let’s say we have two pigs in the kth pen, where k is somewhere in the range from 1 to 9. There are three cases to consider.

When the doubly-occupied pen is away from the ends, so that k is 2, 3, 4, 5, 6, 7, or 8, then the “left, right” operation reduces the value of one pig by exactly 1 and increases the value of the other pig by exactly the same amount, so that the sum of the values of the pigs doesn’t change.

There are also two end cases to consider. When k is 1, and we have two pigs in pen number 1, the pig that moves to the right gains 1 unit of value while the pig that moves back to the field loses 1 unit of value. Again, total value is conserved.

The most interesting case is when k is 9.  When we have two pigs in pen number 9, with combined value 18, sending one pig to the left and the other pig back into the field changes the combined value of the pigs from 18 to 8. The sum changes, but its last digit stays the same.

#4: When we play Swine in a Line with n pigs and n pens, the governing form of arithmetic is mod n+1 arithmetic. You may wonder, where does the “plus one” come from?

A good way to think about this comes from sandpile group theory. In this theory, you should imagine ten locations arranged in a circle, not nine in a line. One of these locations is special: it’s called “the sink”. But to say more would take us on too big a detour into the theory.

#5: One issue that I swept under the rug is whether order matters, when it comes to carrying out stabilization. If there are several pens that contain more than one pig, you have a choice regarding which pen to deal with first. Does this element of choice matter? Or is the outcome of stabilization pre-ordained, regardless of how you get there?

The latter is the case, but this isn’t obvious! To see that it’s not obvious, you might try playing around with “reverse chip-firing”: when you see a pig in pen k-1 and a pig in pen k+1, you’re allowed to move them together into pen k, and you can do this for any value of k, but that’s the only sort of move you’re allowed. You can check that if you start with pigs in pen 1 through 4 (one pig apiece), the freedom that you appear to have is illusory (it doesn’t matter whether you start by moving two pigs into pen 2 or by moving two pigs into pen 3); when you’ve run out of possible reverse chip-firing moves, you’ll find two pigs in pen 2 and two pigs in pen 3. However, you can also check that if you start with pigs in pen 1 through 5 (one pig apiece), there are different end-states you can get to by doing reverse chip-firing moves.

We say that chip-firing exhibits the phenomenon of confluence, but reverse chip-firing does not. Someday I’ll tell you why chip-firing is confluent, but that’s a story for another occasion.

#6: If you play a solitaire version of the original “one goes left, one goes right” version of Swine in a Line, things eventually get boring, even if you deliberately make goofy moves to amuse yourself. After a while, you’ll get to a stable configuration in which there is at most one vacancy on the board, and once you’ve reached a configuration like that, you’ll never again see a configuration with more than one vacancy on the board. That is, configurations with two or more vacancies are what we call transient; you may see them for a while, but don’t get used to them, because eventually you’ll stop seeing them and then never see them again. On the other hand, stable configurations with one vacancy (or no vacancies at all) keep turning up over and over again; these are configurations that we call recurrent. The story of transience and recurrence, like the story of confluence, is a good story, but it’s not today’s story.

Once the game reaches a recurrent stable state (which, according to general results about sandpiles, must happen sooner or later), the board either has no vacancies (which means that someone just won) or has exactly one vacancy (in which case the next player has a win).

You could play a game in which the goal is not to achieve the “full” state (with no vacancies), but to avoid creating recurrent states (with at most one vacancy). This turns out to be the same as Swine in a Line, but the idea of avoiding recurrent states (as opposed to achieving a full state) generalizes better to other kinds of boards (such as the 3-by-3 board discussed in the Numberphile video).

#7: In the Numberphile video, Garcia-Puente spends a lot of time talking about “zeroes” that are not 0. These are recurrent configurations with the magical property that when you add them to any recurrent configuration C, and then do all the requisite firings to make the result stable again, you get configuration C again. In the case of the original version of Swine in a Line, the “zero” configuration is a configuration in which the middle pen is empty and every other pen contains one pig. If you add this stable configuration to itself you get the unstable configuration in which the middle pen is empty and every other pen contains two pigs. You can check that if you stabilize this configuration, you end up with the configuration in which the middle pen is empty and every other pen contains one pig. Congratulations; you’ve just verified that zero plus zero equals zero in this particular sandpile group!

#8: Here’s a game with pigs that I haven’t solved yet: We have n pigs and n pens. The moves are just like the first version of Swine in a Line (one pig goes left, one pig goes right), but we add to this the sudden death condition that I introduced in the “one goes left, one goes out” variant of the game: if there are two pigs in the leftmost pen, the game ends. (If there are two pigs in the rightmost pen, the game continues in the usual way: one goes left, one goes back into the field.) Can anyone figure out the theory behind this game?

REFERENCES

Brady Haran’s video on sandpiles, featuring Luis David Garcia-Puente: https://www.youtube.com/watch?v=1MtEUErz7Gg

Mike Lawler’s videos on Swine in a Line: part 1, part 2, and part 3.

James Tanton has made many videos about Expoloding Dots, but here’s a good one to start with. Also, here’s the homepage of the Global Math Project.