The Paintball Party Problem and the Habit of Symmetry

As the show-runner of my nine-year-old son’s birthday party, I expected to face lots of problems. I just didn’t expect any of them to be math problems.

There were eight boys at that party, including my son and his close buddy, and while those two would’ve been happy to be on the same team in every four-on-four game, my wife wisely suggested that I set things up so that each boy would be on my son’s team the same number of times. In fact, it would be ideal if, over the course of the party, each boy could be each other boy’s team-mate the same number of times. Then no one would have cause to call “No fair!” the way nine-year-olds often do.

RANDOMNESS AND QUASIRANDOMNESS

One approach to fairness is randomness. What if, for each game, I divide the boys randomly into two teams of four? Then in any given game my son and his buddy would have a 3-out-of-7 chance of being on the same team (because, out of the 7 kids who aren’t my son, 3 would get to be on my son’s team). So if the boys played seven games, and the teams were chosen randomly, the expected number of times my son and his buddy would be on the same team would be 7 times 3/7, or 3. Ditto for any two boys at the party: if the teams were chosen randomly for each game, the two boys could expect on average to be on the same team three times. And seven games was just about the number of games the boys would have time to play in their three-hour window (allowing for time to eat pizza and birthday cake).

The problem with the random approach is that even though it’s good on average, it’s sometimes bad. If I’d chosen teams randomly, there’s about a 2% chance that my son and his buddy would never get to play on the same team. And there’s an even larger chance that there’d be some two boys who never got to be on the same team. If this had happened, there’s a good chance that by the end of the party the kids would have been calling “No fair!”.

There’s a theme in mathematics called “quasirandomness“; when we do things quasirandomly, we try to reproduce the average-case behavior of random processes in a sure-fire way, without resorting to chance. As a devotee of quasirandomness, I wondered: Can I design a seven-game schedule for eight boys so that any two boys play on the same team exactly three times?

You might want to try this problem on your own before you read further.

“GEOMETRY, GEOMETRY, GEOMETRY!”

Fig. 1. We represent the eight boys by the eight vertices of a cube. The left panel assigns labels to the vertices; the right panel shows the vertices’ coordinates.

Because of my training as a mathematician, the fact that the number of boys at the party was 8, or 2-cubed, screamed “Use geometry!” at me: it’s natural to assign, to each of the 8 boys, one of the 8 corners of an imaginary cube, as in Figure 1, and then proceed using geometrical ideas. (The left panel shows the points labeled A through H; the right panel shows the coordinates of the points.) The new, geometrified problem is to divide the 8 vertices of a cube into two sets of 4 in seven different ways, so that for any two vertices of the cube, P and Q, the points P and Q are in the same set of 4 exactly three times. It’s helpful to think of painting the vertices blue and red, with 4 vertices of each color, as in Figure 2. We want to find seven such colorings, so that each pair of vertices P and Q get assigned the same color three times (from now on, when I say “three times” I mean exactly three times).

Fig. 2. Three ways to divide the eight vertices into two sets of four.

We could start by slicing the cube with cuts parallel to faces of the cube. The six faces give three ways to cut, so we get the three colorings shown in Figure 2. I represent my son by the origin A=(0,0,0). A point will be colored blue if the corresponding child is on the same team as the birthday boy; the points corresponding to the remaining kids are colored red. In the first coloring shown in Figure 2, the point (x,y,z) is blue or red according to whether x is 0 or 1; in the second coloring, (x,y,z) is blue or red according to whether y is 0 or 1; and in the third coloring, (x,y,z) is blue or red according to whether z is 0 or 1.

This is a good start, but how should we continue? We need to find four other ways to paint the vertices of the cube (4 blue,  4 red), so that when the seven colorings are taken together, every pair of points P,Q get the same color three times. Where will those other colorings come from?

FINITE FIELDS

Here’s where I pulled finite fields out of my mental utility closet. Finite fields are mathematical systems that mimic some aspects of ordinary arithmetic, but with a key difference: There are only finitely many numbers. The simplest finite field (and the only one I’ll discuss today) is the finite field with two elements. This field is often written as GF(2) (where “GF” stands for “Galois field”); it consists of two elements, written as 0 and 1, satisfying the properties shown in these tables:

The equation 1+1=0 may seem strange , but the arithmetic of GF(2) makes sense if you think of 0 as meaning “even” and 1 as meaning “odd”. Then “1+1=0” just means that the sum of two odd integers is an even integer.

This kind of arithmetic plays a role in the design of error-correcting codes and the design of experiments and other things as well. Part of the power of finite-field arithmetic is that it gives rise to its own kind of geometry. Recall that points in ordinary three-dimensional Euclidean geometry can be represented by triples (x,y,z), where x, y, and z belong to “the real field” R — the set of ordinary real numbers, equipped with the usual operations of arithmetic. (Mathematicians usually write the field of real numbers as “ℝ“, using a nifty special font, but WordPress has trouble with it so I’ll just use an ordinary “R”.)

Mathematicians call three-dimensional Euclidean space R³, pronounced “R-three”. In R³ we have infinitely many points. But using GF(2) in place of R we can create a funny kind of geometry in which there are only eight points: the triples (0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), and (1,1,1). We call this three-dimensional “space” GF(2)³.

What’s a “plane” in GF(2)³? Well, let’s remember what a plane in R³ is: it’s the set of triples (x,y,z) of elements of R satisfying some particular linear equation ax+by+cz=d, where a, b, c, and d are elements of R, with a, b, and c not all equal to 0. So, trusting analogy as our guide, we define a plane in GF(2)³ to be the set of triples (x,y,z) of elements of GF(2) satisfying some particular linear equation ax+by+cz=d, where a, b, c, and d are elements of GF(2), with a, b, and c not all equal to 0. For instance, the equation 1x+0y+0z=1 (or equivalently x=1) determines the plane in GF(2)³ consisting of the four points (1,0,0), (1,0,1), (1,1,0), and (1,1,1). These are precisely the red points in the coloring shown in Figure 1(a).

PLANES WITH ONLY FOUR POINTS

In the finite geometry GF(2)³, there are exactly fourteen planes, given by the fourteen ways of choosing a, b, c, and d in the field GF(2), with a, b, and c not all equal to 0. The planes that go through the point (0,0,0) correspond to the equations x=0, y=0, z=0, x+y=0, y+z=0, x+z=0, and x+y+z=0. The planes that don’t go through the point (0,0,0) are given by the same equations, but with the right hand side replaced by 1. The panels of Figure 3 show the blue-red colorings given by the expressions x+y (panel (a)), y+z (panel (b)), and x+z (panel (c)); points are painted blue or red according to whether the expression has the value 0 or 1 in GF(2). Figure 4 shows the blue-red coloring given by the expression x+y+z. (If you prefer to do your arithmetic in the set of ordinary real numbers, you can describe these colorings in terms of odd and even numbers. For instance, in Figure 4, the point (x,y,z) is blue or red according to whether x+y+z is even or odd. The blue points lie on the planes x+y+z=0 and x+y+z=2, while the red points lie on the planes x+y+z=1 and x+y+z=3.)

Fig. 3. Three more ways to divide the eight vertices.

Fig. 4. The final way to divide the eight vertices.

I learned about spaces over GF(2) when I took a course in coding theory with Elwyn Berlekamp in the 1980s, or maybe even before that, so in the back of my mind I knew that this was the right sort of thing to look at for my paintball problem: I needed seven ways to divide the eight boys into two teams of four boys each, so they could correspond to the seven pairs of parallel planes in GF(2)³.

The colorings shown in Figures 2, 3, and 4 give me the schedule shown in Figure 5 (where I use the letters A through H to represent the players just as I used them to represent the corresponding points). If you came up with this same solution, or something like it, without knowing about GF(2)³, take a bow!

Fig. 5. The schedule constructed from Figures 2, 3, and 4.

But our work isn’t done yet. How do we know that this design has the required property of fairness? That is, how do we know that each pair of boys get to play on the same team exactly three times? Or, putting it in terms of painting the corners of a cube: How do we know each pair of points get to be the same color exactly three times?

“SYMMETRY, SYMMETRY, SYMMETRY!”

Here’s where I want to return to the utility-closet metaphor and supplement it a bit. When I was sharing some of my preliminary ideas about this essay with Henri Picciotto and James Tanton, they were both dismayed by the use I made of my utility closet metaphor, and the way I planned to use the paintball party problem as an example of the unexpected usefulness of mathematical ideas. After all, during the three-decade stretch that elapsed between my taking Berlekamp’s course and my micromanaging my son’s paintball party, I got to use GF(2)³ in daily life exactly zero times. So sure, I can talk about how handy it was to have a mental picture of GF(2)³ sitting around in my hippocampus. But if most of what we math educators do is furnish our students’ brains with ideas that they won’t use for decades, shouldn’t we hand in our chalk and find a different line of work?

So I’ll now hastily extend my metaphorical treatment of tools and tool-use in a way that I think Henri and James will like better. There are some tools in my house that I use once every few months, or years, and others that I haven’t used yet but keep around because I might want to use them someday; it’s handy to know where they are. Then there are tools like eating utensils that I don’t even call tools because I use them so often. And then there are my eyeglasses, which I use pretty much constantly and which shape the way I see the world. These last two kinds of tools, or rather their math-education analogues, are the ones good teachers impart. And one such profound mind-tool is the concept of symmetry.

Without the concept of symmetry, it would be laborious to check that the schedule shown in Figure 5 has the desired property. There are 28 pairs of boys at the party, and for each pair, I’d need to check that they play together exactly 3 times. That’s a fair bit of work!

One way to reduce the number of cases that require checking is to use the ordinary symmetries of a cube sitting in R³. For instance, let’s consider three-fold rotational symmetry of the cube about the axis going through the points A and H. (Here’s a link to a video showing what such a rotation looks like. If you’ve got a pet cube, Rubik’s or otherwise, hold it at opposite corners between your two index fingers and then give it a spin with your thumb.) For any point (x,y,z), a 120-degree rotation about this axis sends (x,y,z) to (y,z,x), a second rotation brings it to (z,x,y), and a third rotation brings it back to (x,y,z). The seventh coloring (in Figure 4) isn’t affected by these rotations. The other colorings are permuted by these rotations: rotation turns each of the six colorings into one of the other six. This symmetry cuts down on the number of cases we need to check. If player B (represented by the point (x,y,z)=(0,0,1)) and player D (represented by (u,v,w)=(0,1,1)) play on the same team three times, then the same must be true for player C (represented by (y,z,x)=(0,1,0)) and player G (represented by (v,w,u)=(1,1,0)), and similar reasoning shows that the same must be true for players E and F. This style of reasoning using symmetry has its roots in common sense, but it takes some getting used to; that’s part of what one picks up in courses in abstract algebra.

Using just rotation about the line going through A and H, we can reduce the number of cases that need to be checked from 28 down to just 10. If we use more symmetries of the cube, we can bring that down to just 3. Wearing symmetry-spectacles, we can see that we just need to check that our same-color-exactly-three-times condition holds for a single pair of points that share an edge of the cube (such as A and B), for a single pair of points that share a diagonal of one of the cube’s faces (such as A and D), and for a single pair of points that are diametrically opposite each other (such as A and H).

That (approximately) ten-fold saving of labor is pretty neat, isn’t it? But it’s not what I actually did. That’s because I know about some symmetries that aren’t present in R³, but are present in GF(2)³. As I explain in the Endnotes, there’s a symmetry operation on GF(2)³ that carries the points A and B to the points A and D, respectively, and there’s another symmetry operation on GF(2)³ that carries the points A and D to the points A and H, respectively. The upshot is that we need only check one case. As long as for a single pair of points, say A and H, we check that those points get assigned the same color exactly three times, we’ll be able to conclude that for any pair of points P and Q, P and Q get assigned the same color three times.

CHECKING NO CASES AT ALL: THE FINAL TRICK

That twenty-seven-fold saving of labor is even neater, isn’t it? But it’s still not what I actually did. Once we know that the answer to the question “How many times do P and Q get the same color?” is the same for all P and Q, and once we show that the average value of that answer (as we vary P and Q) must be 3, we can conclude that in each and every case, the answer must be 3, as we wanted to show! Thanks to symmetry, and an averaging argument, there are zero cases to check.

Why must that average be 3? Here’s one way to think about it. For each of the 28 pairs of boys at the party, make a row on a piece of paper, and every time those two boys play on the same team, put a tick mark in that row. For instance, suppose that in the first game we pit A, B, C, and D against E, F, G, and H. Then we put tick-marks in rows AB, AC, AD, BC, BD, and CD as well as rows EF, EG, EH, FG, FH, and GH — twelve tick marks in all. Over the course of seven games, the number of tick marks in our tally-chart will be seven times twelve, or 84. So the average number of tick-marks per row is 84 (the total number of tick-marks) divided by 28 (the number of rows), which is exactly 3.

So, summarizing: if we know that each row has the same number of tick marks as every other, and if we know that the average number of tick-marks per row is 3, then every row must have exactly 3 tick marks. That is, each boy gets to be on the same team as each other boy exactly 3 times.

That’s what I did, and that’s how I came up with the schedule that I presented to my son. It took me under five minutes, if you leave out the time I spent learning abstract algebra and coding theory thirty-plus years earlier.

If you find yourself thinking that I’m clever, you’re missing the point. It’s not that I’m smart; thousands of mathematicians would have come up with the same idea, following more or less the same route, because of the training we receive. (If you want to credit me with anything, credit me with keeping a clear head amid the noise and tumult of a paintball franchise, so that I could apply what I’d learned years earlier.) Mathematical education, especially when continued beyond high school and college into graduate school years and beyond, does many things to our brains, but one of the deepest-rooted habits it instills in us is an instinct for looking for symmetry amidst complexity. In some ways this habit of symmetry can become a “habit” in the more insidious sense of the term: an addiction to symmetry can blind one to all the ways in which things that appear to be symmetrical might not be. (Here’s an Alan McKay quote on this point: “Like the ski resort full of girls looking for husbands and husbands looking for girls, the situation is not as symmetrical as it might seem. “) Fortunately, in the world of mathematics, as opposed to the real world, this reductive approach pays off far more often than it leads one astray.

VARYING THE PROBLEM

Another contributor to my success was luck. If there had been 6 boys, or 10 boys, or 14 boys, or indeed any even number of boys not divisible by 4 (leaving aside the easily solved case of 2 boys), then it can be shown that there’s no way to come up with a game schedule like the one I constructed, with the number of games being 1 less than the number of boys. It turns out that it’s enough to focus on just three of the boys (any three will do). For instance, if you have ten boys play nine 5-on-5 games, you can’t have three boys A, B, and C such that A and B are team-mates four times, A and C are team-mates four times, A and B are team-mates four times. For a challenge, try to prove this! It takes just a little bit of algebra and a little bit of number-theory.

What about 12 boys, or 16, or 20, etc.? In the case of 12 boys, there’s a very special solution based on  the sporadic finite simple group M₁₁ (see Dima Pasechnik’s comments at the MathOverflow thread I started when I was preparing this article); I certainly wouldn’t have been able to come up with that schedule during the first few minutes of the paintball party! With 16 boys, you can adapt my solution to the 8-boy problem, using GF(2)⁴ instead of GF(2)³. As for larger numbers of boys, it’s believed that the problem can be solved whenever the number of boys is divisible by 4, but this has not been proved. It’s equivalent to one of the oldest unsolved problems in the theory of combinatorial designs, the Hadamard matrix conjecture.

Although my solution was mathematically elegant, it left something to be desired. For one thing, there was another 8-boy birthday party at the paintball franchise at the same time, and the boys in my party wanted to go 8-on-8! Also, the schedule I devised (not quite the same as Figure 5, though similar in design) had my son and his buddy playing on the same team for the first three games, and on opposing teams thereafter; by the time we got to game seven, they were eager to be on the same team again, even though my schedule said that they’d already used up their three chances to play together. (“No fair!”) A better schedule would have spread things out more evenly. This is a topic I plan to return to in a future essay, where I’ll bring discrepancy theory to bear on the problem of designing schedules like this.

Still, the party was a success — so much so that my son’s buddy decided that for his next birthday, he wanted a paintball party too. He invited my son. The kid’s father took a different approach to the fairness problem than I had: at the start of each game, he randomly lined the kids up, counted off “One, two, one, two, …”, and assigned them to teams accordingly. Can you guess which solution my son preferred? Yep; he liked the other dad’s solution a lot better. Quasirandomness is a great source of challenging mathematics problems, but sometimes plain old randomness is the way to go. Perhaps the voice I should have heeded was Thoreau’s: “Simplicity, simplicity, simplicity!”

Next month (May 17): Did Fermat Prove His Last Theorem?: The Curious Incident of the Boasting Frenchman.

Thanks to Elwyn Berlekamp, Veit Elser, Sandi Gubin, Christian Lawson-Perfect, Joe Malkevitch, Henri Picciotto and James Tanton.

ENDNOTES

Purists might say that there’s a slight difference between GF(2)³ and Euclidean 3-space; the former comes equipped with a choice of origin and coordinate axes, while the latter does not. (It’s a picky difference, but one that matters in some contexts.) In a similar way, some people distinguish between GF(2)³ and AG(3,2) (“the three-dimensional affine geometry over the two-element field”); the former is the “coordinatized” version of the latter.

A friend of mine had GF(2)³ (and other, higher-dimensional spaces based on GF(2)) forced upon her in college by a brilliant but inconsiderate teacher who said something like “I’m supposed to teach you linear algebra, but I’ve been doing it the same way for years and I’m getting bored with my old approach, so I’m going to teach it to you over the two-element field.” It’s good for teachers to change what they do, but not at the expense of their students! Linear algebra of the ordinary kind (“linear algebra over the field of real numbers”), properly taught, is full of pictures. When you move to finite fields, some of the ideas carry over, but the pictures mostly don’t, and that’s bound to make life harder for the learners. More importantly, linear algebra of the ordinary kind is much more broadly useful than the kind that this eccentric professor taught. I consider this sort of teaching an abuse of the leeway that professors are given in universities. Still, linear algebra in GF(2)³ comes in handy for the paintball problem.

The symmetry operation on GF(2)³ that carries the points A=(0,0,0) and B=(0,0,1) to the points A=(0,0,0) and D=(0,1,1) respectively is the shear mapping that more generally sends the point (x,y,z) to the point (x,y+z,z).  How do we know that it permutes the seven colorings? Because, being a linear transformation, it sends planes to planes, and the fourteen planes given by our seven colorings are all the planes that there are in GF(2)³! So symmetry tells us that if A and B satisfy the exactly-three-games condition, so must A and D. Likewise, the shear mapping of GF(2)³ that sends (x,y,z) to (x+z,y,z) provides us with a way to see that if A and D satisfy the exactly-three-games condition, so must A and H. Together, these two shear transformations show that there’s only a single case to check, rather than three.

If you throw away (0,0,0) from GF(2)³, so that the space has only 7 points instead of 8 and each plane that formerly went through (0,0,0) has only 3 points instead of 4, and rename these mutilated planes “lines”, you get Fano’s 2-dimensional finite projective geometry, mentioned in my essay on lotteries. For more on finite geometries, see the essay by Joe Malkevich.

As an alternative to GF(2)³ or the cube, you can use periodic colorings of the infinite cubic lattice Z³. Z³ is the set of all triples (a,b,c) where a, b, and c are integers, and the blue-red colorings we allow are those with the property that for all integers a, b, and c, the color of (a,b,c) is the same as the color of (a+2,b,c) and (a,b+2,c) and (a,b,c+2). Such a coloring is just a coloring of (0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), and (1,1,1), repeating ad infinitum. A conceptual advantage of this picture is that you can imagine applying a shear transformation to turn one coloring into another. For instance, if you extend Figure 2(a) by repetition to a coloring of all of Z³ and then shear each point (a,b,c) to the point (a+c,b,c) (keeping its coloring intact), you’ll obtain the coloring in Figure 3(c); and if you then apply the same shearing transformation a second time, it’ll turn the coloring in Figure 3(c) back to the coloring in Figure 2(a).

Here’s a caveat about my glib earlier remark that “There are only finitely many numbers” in a finite field. It’s a bit of a stretch to call the elements of finite fields “numbers”. Elements of GF(q) can be thought of as the integers mod q when q is prime, and they can be represented by 0, 1, 2, …, q–1; but when q is a prime raised to the 2nd power or higher, describing the elements of GF(q) is more complicated, and the word “number” isn’t apt.

As for the problem about the ten boys: Let w be the number of times A, B, and C are all team-mates, let x be the number of times A and B play on the same team against C, let y be the number of times A and C play on the same team against B, and let z be the number of times A plays against both B and C. Then the total number of times A and B are team-mates is w+x, the total number of times A and C are team-mates is w+y, and the total number of times B and C are team-mates is w+z. So, if each of the boys in the threesome is a team-mate with each of the other boys in the threesome four times, we must have w+x=4, w+y=4, and w+z=4. Adding the three equations, we get 3w+x+y+z=12. On the other hand, the total number of games played is 9, so w+x+y+z=9. Subtracting this last equation from 3w+x+y+z=12 we get 2w=3, which is impossible, since w is a whole number. The same argument works if ten is replaced by any even positive integer that’s not divisible by four — except for the number two. Do you see where the proof of impossibility breaks down when there are two players?

Here’s something I don’t know: If the number of players is an even number not divisible by four, is there a fair schedule in which the number of games played is not the number of players minus 1, but twice that? (For example, if there are ten boys, we’ve seen that there is no 9-game schedule in which each boy is each other boy’s team-mate exactly 4 times, but is there an 18-game schedule in which each boy is each other boy’s team-mate exactly 8 times?) I posed this problem on MathOverflow, but nobody solved it. Maybe you will!

REFERENCES

E.R. Berlekamp and F.K. Hwang, 1972, Constructions for Balanced Howell Rotations for Bridge Tournaments”, Journal of Combinatorial Theory, volume 12, pages 159–165.