## Mathematics in Games, Part 2

Last month I wrote a post on the importance of context when teaching and learning mathematics, especially as it applies to games.  My primary point was that the mathematics needs to be embedded in the gaming experience in order for the math to stick in the player’s head.  Games that pull the player out of the primary gaming experience to solve math problems do not teach the mathematics as effectively as they could.  They also reinforce a sense that mathematics isn’t relevant.

As it turns out, I’ve written two games that feature a great deal of mathematics: A Beauty Cold and Austere and Junior Arithmancer.  In this post I’ll talk about how I wove math into these two games – what I think I did right as well as what I think I did wrong.

First, ABCA and JA are both parsed-based interactive fiction (IF).  This is an old genre of computer game, dating back to the 1970s.  The player’s experience with the game is mediated almost entirely through text, rather than graphics.  Playing parser-based IF is a lot like reading an interactive book, where you type in what you want the player to do.  For example, if you happen to find yourself in a room with, say, a battery-powered brass lamp, you could type

GET LAMP

and the game would transfer the lamp to your inventory, while giving you a response such as

Taken.

So, there’s one aspect of ABCA and JA that’s different from a lot of math edutainment games: They’re both text-based rather than graphics-based.  In the late 2010s, that will unfortunately limit the appeal of the games.  On the other hand, that also means that I can create the games myself and distribute them for free, without having to depend on and pay artists, graphic designers, and others.  (Not that I have anything against artists or graphic designers; it’s just that I don’t have the time or money to direct a major software project involving multiple people.)

In A Beauty Cold and Austere you play the role of a college student taking a survey course in conceptual mathematics.  You’ve blown off the course all semester and are now facing an oral final exam in the morning.  Tired of studying, you fall asleep – and you dream your way through the history of mathematical thought.  The gameplay involves solving a series of (mostly) mathematically-related puzzles.  By the time you’ve completed the game you’ve demonstrated an understanding of a variety of areas of mathematics – such as algebra, geometry, calculus, and probability – and are able to pass your final exam with ease.

(MAJOR SPOILERS FOR ABCA COMING UP.)

For example, at one point in the game you find yourself in the Library of Alexandria.

On the wall are carved numbers from 1 to 100, in ten rows of ten each.  It looks like you could push any of the numbers.  Next to the numbers is a switch, with two settings: “Remove Number” and “Remove Larger Multiples of the Number.”  The switch is currently set to “Remove Number,” although you could easily move it to the other setting by flipping the switch.  The numbers currently look like this:

1   2   3   4   5   6   7   8   9  10

11  12  13  14  15  16  17  18  19  20

21  22  23  24  25  26  27  28  29  30

31  32  33  34  35  36  37  38  39  40

41  42  43  44  45  46  47  48  49  50

51  52  53  54  55  56  57  58  59  60

61  62  63  64  65  66  67  68  69  70

71  72  73  74  75  76  77  78  79  80

81  82  83  84  85  86  87  88  89  90

91  92  93  94  95  96  97  98  99  100

At the bottom is a challenge from the librarian: “To access the map room, leave just the primes between 1 and 100 by pushing only five numbers.”

More mathematically-inclined players will recognize that you need to use the Sieve of Eratosthenes to proceed here.  But you don’t need to have seen the Sieve to solve the puzzle.  In fact, I’ve watched more than one player quickly realize that setting the switch to “Remove larger multiples” and then pushing 2 will remove almost half of the numbers.  From there, it’s not too hard to figure out what else needs to be done – especially since the game dynamically updates the puzzle to let you know what’s left.

Which is part of the point, really.  ABCA isn’t trying to give players arithmetic or algebra practice; it’s trying to get people to engage with and explore mathematical ideas.  So it needs to be accessible to people who haven’t seen a lot of advanced mathematics.

I guess that last paragraph was a bit of a digression from my theme of embedding mathematics in the game world.  But it gets at another aspect of designing a game that features mathematics: The mathematics in the game should itself be interactive – not static.  The player should be able to try things and have the game respond in ways that encourage the player to keep playing with the mathematical ideas.  It shouldn’t be about merely coming up with the right answer to a math question.

I think the number puzzle here is a pretty good example of embedding mathematics in a game.  Its weakness is that it is a “set puzzle”: While it doesn’t commit the error of pulling the player out of the game, it is mostly stand-alone in terms of the gameplay.  However, set puzzles are a common feature of parser-based interactive fiction, so the player is expecting them.  In addition, Eratosthenes was actually the head librarian at the Library of Alexandria, so it makes sense for the player, while standing in his office, to encounter a challenge that uses his Sieve.

In truth, several of the math puzzles in ABCA are set puzzles.  I tried to place them in spaces that made sense, though: The main probability set puzzle is in a casino, for example, and a graph theory puzzle is reinterpreted as riding a laser bike through a collection of roads and intersections.  And some of the puzzles, such as the calculus/roller coaster puzzle, require information or objects from elsewhere and so are not completely self-contained.  I think it’s fine to include several set puzzles in a math-heavy game, but the designer should try as much as possible to integrate them into the game world.

The most embedded puzzle – and thus arguably one of the best in the game – is the meta-puzzle at the very top level of the game’s geography.  When you first enter the dream you find yourself standing at a point.  Your actions very quickly turn this into a number line.  Then, as you progress further through the game and learn more mathematics, this region of the game adds more features – such as a zero, negative numbers, and a few more aspects that I’ll let the reader discover for herself.  This top level thus ends up mirroring the development of mathematics that the player is discovering throughout the game.  It’s also the source of some of the puzzles the player needs to solve.

There’s more to puzzle design than embeddedness, though.  There’s also interactivity and engagement.  I’ve heard some refer to this as “juicyness.”  The idea is that a puzzle should give some kind of interesting response to everything reasonable the player tries.  In other words, the game shouldn’t just spit back a generic failure message to everything except the expected right solution.  In addition to this kind of responsiveness, multiple solutions to a puzzle can also help achieve juicyness.

The puzzle where I think ABCA achieves juicyness the most is probably the sequences-and-series machine.  This one is very much a set puzzle in terms of the player’s first encounter with it.  However, the machine is attached to a path that responds to the different settings of the machine’s various dials and levers.  Each combination of settings reproduces a different sequence or infinite series of real numbers, and the path changes to lead to the limit of the sequence or the sum of the series.  Some of the sequences and series converge and some don’t, and those that don’t fail to do so in different ways.  All of these are modeled by the path.  There is a particular “right” path outcome in terms of advancing the game, but there are multiple setting combinations that produce it – corresponding, of course, to the sequences and series that actually lead to that right outcome.  But the player can fool around with the machine as much as he wants, seeing what the different settings do.  Thus this particular puzzle achieves juicyness by featuring both multiple solutions and plenty of responses to “failure” attempts.  And in terms of the mathematics, it’s a lot more interesting to think about convergence and divergence in the context of a game world that you’re exploring than it is when you’re manipulating symbols as part of your calculus homework.  (Well, more interesting for most people.)

There are several puzzles in ABCA that I think are weaker, though.  These generally involve fetching the right item for or answering questions posed by a particular character.  These include the scenes with Cauchy and Weierstrass, with Hypatia, and with Newton, as well as the puzzle involving logarithms.  The Hypatia one in particular could have been better, as at least for the others the player must make a connection between the mathematics they developed and either the objects in the game or the answers to their questions.

But, overall, I’m pleased with A Beauty Cold and Austere.  There are definitely things I could have done better, but I think it’s a good game in its genre of massive puzzlefest, parsed-based interactive fiction.

This post has already gotten long enough, so I suppose I’ll save my comments on Junior Arithmancer for next month.

## Mathematics in Games, Part 1

When my wife and I were buying our first house many years ago our real estate agent Rita quickly found out that I was a math professor.  She gave a response I have heard frequently over the years: “I’m not very good at math.”  At some point during the process it came time to calculate our monthly mortgage payment.  Rita handed me a calculator and said that I could come up with the answer better than she could.  I had been teaching the amortization formula for determining mortgage payments in a class that semester, so I took the calculator and gave it a try.  After several keystrokes I handed the calculator back to Rita with the answer.  She looked at it and said, “That’s not right!”

Question: Who should you believe here?  The math professor, or the real estate agent who said she wasn’t very good at math?

Well, the math professor knew who you should believe: the real estate agent.  Sure, I had been teaching the amortization formula, but it’s a complicated formula.  I might have forgotten a small detail when put on the spot like that, or I might have hit a couple of buttons in the wrong order, or I might have been unaware of how an unfamiliar calculator handles order of operations.  There are lots of little things that all had to go exactly right in order for me to produce the right answer.

Let me drive home the point: Rita, the self-professed “not good at math” real-estate agent, was the more trustworthy expert on a math-heavy question concerning home buying than the math professor.

I think when people say “I’m not good at math” what they mean is that they are not good at the kinds of symbolic manipulation (mainly, arithmetic and algebra) that generally comprise a course in mathematics at the elementary school and junior high levels.  But mathematics isn’t just symbolic manipulation.  For example, it also includes estimation, as Rita displayed in my story here.  And I think that there are plenty of people – like Rita – who say they’re not good at math but who have, in certain domains, developed strong mathematical skills through experience.

Keith Devlin tells a story with a similar moral in his Mathematics Education for a New Era: Video Games as a Medium for Learning.  He talks about a research study undertaken with some young children (between 8 and 14 years of age) selling fruit in a street market in Brazil.  When asked, while working in the market, to do complicated arithmetic calculations to determine the price of several coconuts, the children got the answer correct 98% of the time.  (And they did this in their heads – often making use of some rather clever arithmetic shortcuts in the process!)  When presented, in their homes, with verbal word problems dealing with market stall sales transactions, the children got the answer correct 74% of the time.  However, when asked to solve written symbolic arithmetic problems that were mathematically identical to the market sales problems they only got the answer correct 37% of the time.

I tell these two stories as lead-ins to something I’ve been thinking about lately: Context often matters when it comes to doing mathematics.  And I think it matters with respect to teaching mathematics.

One thing I’ve been interested in the past couple of years is teaching mathematics through games.  My impression of most games that I’ve seen that really attempt to do this is that they repeatedly pull the player out of the context of the game in order to solve a series of math problems.  For example, the online game Prodigy (which my oldest son was really into during first grade) does this.  Prodigy is an RPG (role-playing game) aimed at elementary school kids.  As a player, you explore the game world and battle a series of monsters, earning experience and better equipment, as well as leveling up and acquiring new skills.  The math part appears in that every time you attempt an attack, the game throws a math problem at you.  In order to complete the attack successfully, you must solve the problem.  One thing the game does really well here is to ramp up the difficulty level with the player, so as you gain more experience you’re presented with harder and harder math problems.

However, having to solve a math problem has nothing internally to do with the game world you’re exploring in Prodigy.  As a result, you lose some of the sense of immersion in the game every time you attempt an attack.  In addition, the math problems are externally-imposed obstacles that you must overcome in order to get back to the real fun of the game.  I fear that an unintended side effect of games like Prodigy is to reinforce kids’ sense that math is an obstacle – a chore.  I also fear that they reinforce the impression that math is irrelevant to what really matters.

I also wonder how well the mathematics that a Prodigy player is supposedly learning is really sticking with him or her.  The questions are multiple-choice, for one.  (This is probably a good move from a gameplay standpoint, but this format doesn’t really require the player to think through the problems.)  Even more troubling is the fact that the mathematics is so separate from the rest of the game.  The more we can connect a new concept with things we already know (i.e., the more we can place new knowledge in a context, like with my real estate agent and those Brazilian kids), the more we retain it.  Contrariwise, new knowledge thrown at us that is not embedded in any larger context doesn’t tend to remain with us.

I really don’t mean to hit Prodigy too hard here.  I do think it’s one of the better kids’ math games I’ve seen.  Also, my son had a lot of fun playing it, and I’m glad he was spending time with it rather than some of the other games out there.  But I want to think about how we can do even better at embedding mathematics in games.

I have written a couple of my own games that feature mathematics – A Beauty Cold and Austere and Junior Arithmancer.  They’re text-based and feature no graphics, so that makes their appeal somewhat limited compared to a game like Prodigy.  Perhaps in my next post I’ll talk about what I think I did right in those games, mathematically-speaking.

Posted in games, teaching | 1 Comment

## Proof of the Fundamental Theorem of Arithmetic

The Fundamental Theorem of Arithmetic states the following:

Every integer greater than 1 can be represented uniquely as the product of prime numbers.

Another way to put this is that every integer has a unique factorization.  For example, 60 factors into $2^2 \cdot 3 \cdot 5$, and there is only one way to do this factorization using prime numbers.  (Rearranging the order of the numbers doesn’t count as a different factorization.)

In this post we’ll prove the Fundamental Theorem of Arithmetic.  There are two parts: (1) Proving that every integer greater than 1 can be represented as the product of prime numbers (i.e., existence), and (2) Proving that this representation is unique (i.e., uniqueness).

Reminder: A prime number is a positive integer that is divisible by exactly two positive integers: itself and 1.

First, Existence.  Suppose, by way of contradiction, that there is some positive integer that cannot be represented as the product of primes.  Then there is a smallest such number N.  If N cannot be represented as a product of primes then N cannot itself be prime.  Thus there exist two positive integers a and b, with $1 < a \leq b < N$, such that $N = ab$.  Since a and b are both positive integers smaller than N they must each be the product of primes, where $a = p_1 p_2 \cdots p_m$, $b = q_1 q_2 \cdots q_n$, and $p_i$ and $q_j$ are primes for each i and j.  But then $N = p_1 p_2 \cdots p_m q_1 q_2 \cdots q_n$ and thus also is the product of primes.

Second, Uniqueness.  For this we need a lemma that isn’t hard to prove:

Lemma: If a prime p divides an integer $ab$, then divides a or p divides b.

Now, let N be a positive integer.  Suppose there exist two ways to represent N as the product of primes,

$N = p_1 p_2 \cdots p_m = q_1 q_2 \cdots q_n$,

where $p_i$ and $q_j$ are primes for each i and j.  Assume, without loss of generality, that these representations are ordered, so that $p_i \leq p_{i+1}$ and $q_i \leq q_{i+1}$ for all i for which these inequalities are defined.

Suppose $p_1 p_2 \cdots p_m = q_1 q_2 \cdots q_m$ and $n > m$.  Then  $N = p_1 p_2 \cdots p_m < q_1 q_2 \cdots q_n = N$, a contradiction.  Similarly, if  $p_1 p_2 \cdots p_n = q_1 q_2 \cdots q_n$ and $m > n$, we have a contradiction.

Now, let i be the first index for which $p_i \neq q_i$.  If i exists then $i \leq \min\{m,n\}$, by the argument in the previous paragraph.  We can assume, without loss of generality, that $p_i < q_i$.  We have that $p_1 p_2 \cdots p_{i-1} = q_1 q_2 \cdots q_{i-1}$.  Since $p_1 p_2 \cdots p_m = q_1 q_2 \cdots q_n$, we also have $p_i \cdots p_m = q_i \cdots q_n$.  By the lemma, $p_i$ divides $q_j$ for some j, $i \leq j \leq n$.  But each of the $q_j$ values is prime and so is only divisible by 1 and itself.  Since $p_i < q_i \leq q_j$, we have a contradiction.

Thus there is no index i for which $p_i \neq q_i$.  Our argument two paragraphs above shows that we can’t have this and $m < n$ or $m > n$.  Thus $m = n$, and so the two representations, $p_1 p_2 \cdots p_m$ and $q_1 q_2 \cdots q_n$, are identical.

## Equivalence of Two Binomial Sums

This month’s post entails proving the following equivalence:

Identity 1: $\displaystyle \sum_{k=r}^n \binom{k-1}{r-1} p^r (1-p)^{k-r} = \sum_{k=r}^n \binom{n}{k} p^k (1-p)^{n-k}.$

Despite the fact that these two sums are over the same range and are equal for all values of n they are not equal term-by-term.

If you think about the two sides probabilistically, it’s not too hard to prove that they are equal.  For example, $\binom{k-1}{r-1} p^r (1-p)^{k-r}$ is the probability of obtaining the rth head on the kth flip when repeatedly flipping a fair coin.  Thus the left side of Identity 1 is the probability of flipping a fair coin times and obtaining at least r heads.  Similarly, $\binom{n}{k} p^k (1-p)^{n-k}$ is the probability of obtaining exactly k heads when flipping a fair coin n times.  Thus the right side of Identity 1 is also the probability of flipping a fair coin times and obtaining at least r heads.  Therefore, the two sides must be equal.

A while back I was also interested in trying to prove algebraically that the two sides are equal.  This turned out to be harder than it looked, and I thought I would record my derivation here.  It’s a bit heavy on the algebra, I’m afraid.  The overall goal will be to isolate the coefficient of $p^m$ on both sides of Identity 1, as each of the sides can be thought of as a polynomial in p.  If these are equal then the identities must be equal.

The left side first.  Expand $(1-p)^{k-r}$ using the binomial theorem to get

$\displaystyle \sum_{k=r}^n \binom{k-1}{r-1} p^r (1-p)^{k-r} = p^r \sum_{k=r}^n \binom{k-1}{r-1} \sum_{j=0}^{k-r} \binom{k-r}{j} (-p)^j$.

Now, which terms in this double sum contain a $p^m$ term?  Those in which $j = m-r$.  Thus the coefficient of $p^m$ in this double sum is

$\displaystyle \sum_{k=r}^n \binom{k-1}{r-1} \binom{k-r}{m-r} (-1)^{m-r} = \sum_{k=m}^n \binom{k-1}{r-1} \binom{k-r}{m-r} (-1)^{m-r}$

$\displaystyle = (-1)^{m-r} \sum_{k=m}^n \frac{r}{k} \binom{k}{r} \binom{k-r}{m-r}, \text{ by the absorption identity}$

$\displaystyle = (-1)^{m-r} r \sum_{k=m}^n \frac{1}{k} \binom{k}{m} \binom{m}{r}, \text{ by trinomial revision}$

$\displaystyle = (-1)^{m-r} r \binom{m}{r} \sum_{k=m}^n \binom{k}{m} \frac{1}{k}$

$\displaystyle = (-1)^{m-r} r \binom{m}{r} \sum_{k=m}^n \binom{k-1}{m-1} \frac{1}{m}, \text{ by the absorption identity (again)}$

$\displaystyle = (-1)^{m-r} \frac{r}{m} \binom{m}{r} \sum_{k=m-1}^{n-1} \binom{k}{m-1}$

$\displaystyle = (-1)^{m-r} \binom{m-1}{r-1} \binom{n}{m}, \text{ by, once more, the absorption identity, plus the hockey stick identity}.$

Now for the right side of Identity 1.  Expand $(1-p)^{n-k}$ using the binomial theorem to get

$\displaystyle \sum_{k=r}^n \binom{n}{k} p^k (1-p)^{n-k} = \sum_{k=r}^n \binom{n}{k} p^k \sum_{j=0}^{n-k} \binom{n-k}{j} (-p)^j$.

As before, which terms in this contain a $p^m$ term?  Those in which $j = m-k$.  Thus the coefficient of $p^m$ in this double sum is

$\displaystyle \sum_{k=r}^n \binom{n}{k} \binom{n-k}{m-k} (-1)^{m-k} = \sum_{k=r}^m \binom{n}{k} \binom{n-k}{m-k} (-1)^{m-k}$

$\displaystyle = \sum_{k=r}^m \binom{n}{m} \binom{m}{k} (-1)^{m-k}, \text{ by trinomial revision}$

$\displaystyle = \binom{n}{m} \sum_{k=0}^{m-r} \binom{m}{m-k} (-1)^k, \text{ reindexing the sum}$

$\displaystyle = \binom{n}{m} \sum_{k=0}^{m-r} \binom{m}{k} (-1)^k$

$\displaystyle = \binom{n}{m} (-1)^{m-r} \binom{m-1}{r-1},$

where the last expression comes from the formula for the partial alternating row sum of the binomial coefficients.

## A Sum of Ratios of Binomial Coefficients

In this post we evaluate the sum $\displaystyle \sum_{k=0}^m \frac{\binom{m}{k}}{\binom{n}{k}}$.  Then we’ll generalize it and evaluate $\displaystyle \sum_{k=0}^m \frac{\binom{m}{k}\binom{k}{r}}{\binom{n}{k}}$.

The key tools we need for the first sum are the trinomial revision identity, $\binom{n}{m} \binom{m}{k} = \binom{n}{k} \binom{n-k}{m-k}$, and the parallel summation identity, $\sum_{k=0}^m \binom{n+k}{k} = \binom{n+m+1}{m}$.  Using trinomial revision, we have

$\displaystyle \sum_{k=0}^m \frac{\binom{m}{k}}{\binom{n}{k}} = \sum_{k=0}^m \frac{\binom{n-k}{m-k}}{\binom{n}{m}} = \frac{1}{\binom{n}{m}} \sum_{k=0}^m \binom{n-k}{m-k}$.

We can evaluate the remaining sum using parallel summation, but we need to pull a variable switch first.  Replace k with $m-k$ and then apply parallel summation to obtain

$\displaystyle \frac{1}{\binom{n}{m}} \sum_{k=0}^m \binom{n-m+k}{k} = \frac{\binom{n+1}{m}}{\binom{n}{m}}$.

We thus have the identity

$\displaystyle \sum_{k=0}^m \frac{\binom{m}{k}}{\binom{n}{k}} = \frac{\binom{n+1}{m}}{\binom{n}{m}} = \frac{n+1}{n+1-m},$

where the last step follows thanks to some algebra simplification with factorials.

To evaluate the second sum we’ll need an identity that’s like an upper-index version of Vandermonde’s convolution: $\sum_{k=-m}^{n} \binom{m+k}{r} \binom{n-k}{s} = \binom{m+n+1}{r+s+1}$.  Otherwise, the derivation for the second sum proceeds just as the first one does up through the point where we replace k with $m-k$.  Continuing from there and applying the upper Vandermonde identity, we have

$\displaystyle \sum_{k=0}^m \frac{\binom{m}{k}\binom{k}{r}}{\binom{n}{k}} = \frac{1}{\binom{n}{m}} \sum_{k=0}^m \binom{n-m+k}{k} \binom{m-k}{r} = \frac{1}{\binom{n}{m}} \sum_{k=0}^m \binom{n-m+k}{n-m} \binom{m-k}{r} = \frac{1}{\binom{n}{m}} \binom{n+1}{n-m+r+1}.$

We can rewrite this and perform some more algebra simplification to get our generalization:

$\displaystyle \sum_{k=0}^m \frac{\binom{m}{k}\binom{k}{r}}{\binom{n}{k}} = \frac{\binom{n+1}{m-r}}{\binom{n}{m}} = \frac{n+1}{m^{\underline{r}} (n+1-m)^{\underline{r+1}}}.$

## An Alternating Convolution Identity via Sign-Reversing Involutions

This month’s post is on the combinatorial proof technique of sign-reversing involutions.  It’s a really clever idea that can often be applied to identities that feature alternating sums.  We’ll illustrate the technique on the following identity.

$\displaystyle \sum_{k=0}^m \binom{n}{k} \binom{n}{m-k} (-1)^k = (-1)^{m/2} \binom{n}{m/2} [ m \text{ is even}]$.

(Here, we use the Iverson bracket notation $[A]$, where $[A]$ is 1 if A is true and 0 if A is false.)

This identity is interesting because there’s a lot going on here.  For one, it’s an alternating version of the famous Vandermonde identity.  But what’s happening with the right side?  Why is it zero when m is odd, and why does the parity of $m/2$ matter?  The sign-reversing involution technique will help us make sense of all of that.

First, $\binom{n}{k} \binom{n}{m-k}$ can be thought of in terms of counting ordered pairs $(A,B)$, each of which is a subset of $\{1, 2, \ldots, n\}$.  However, the choice of $(A,B)$ is subject to the restriction that $|A| = k$ and $|B| = m-k$.  The alternating sum on the left side of the identity is taken over all such pairs such that $|A| + |B| = m$, where the parity of a particular $(A,B)$ is the parity of $|A|$.

We now have a combinatorial interpretation of the left side.  Now, let’s define the sign-reversing involution.  Given $(A,B)$, let x denote the largest element in the symmetric difference $A \oplus B$ of A and B; i.e., $A \oplus B = (A-B) \cup (B-A)$.  Let

$\displaystyle \phi(A,B) = \begin{cases} (A-\{x\}, B \cup \{x\}), & x \in A; \\ (A \cup \{x\}, B - \{x\}, & x \in B.\end{cases}$

Note that $\phi$ takes an ordered pair $(A,B)$ such that $A, B \subseteq \{1, 2, \ldots, n\}$ and $|A| + |B| = m$ and maps it to another such ordered pair.  Moving the largest element x in the symmetric difference of A and B to the other set changes the number of elements in A by one and thus the parity of $|A|$.  This means $\phi$ is sign-reversing.  In addition, $\phi(A,B)$ has the same largest element x in its symmetric difference that $(A,B)$ does; thus applying $\phi$ to $\phi(A,B)$ just sends x back to its original set.  Thus $\phi(\phi(A,B)) = (A,B)$, which makes $\phi$ an involution.

These two properties mean that $\phi$ associates an ordered pair $(A,B)$ of the kind we’re examining with another ordered pair that has a different parity.  Each of these pairs cancels out its associated pair in terms of evaluating the alternating sum on the left side of the identity we’re trying to prove.  Since every pair $(A,B)$ has an associated pair that cancels it out, we have that the right side of our identity is the number of pairs $(A,B)$ for which $\phi$ is not defined.  Let’s count those leftover pairs now.

The only way for $\phi$ to be undefined is for the largest element x in $A \oplus B$ to not exist.  But that can only happen if $A-B = \emptyset = B-A$; in other words, $A = B$.  In this case, though, since $|A| + |B| = m$, we have $|A| = |B| = m/2$.  Thus when m is odd, there are no pairs $(A,B)$ on which $\phi$ is undefined; hence the right side of the identity is 0 when m is odd.  When m is even, there are $\binom{n}{m/2}$ ways to choose the elements of A, and since $B = A$, this choice also determines B.  Since for all of these pairs A has $m/2$ elements, the parity of these leftover elements is the parity of $m/2$.

In general, this is how a sign-reversing involution argument works: Find a combinatorial interpretation of the terms in the left side of the alternating sum, then find a sign-reversing involution that maps entities with odd parity to entities with even parity and vice versa.  Counting the entities that are left over – i.e., those not paired up by the involution – will yield the right side of the identity.

For more sign-reversing involution arguments, see this post and this post.  Chapter 6 of Benjamin and Quinn’s Proofs that Really Count [1] and Chapter 5 of Aigner’s A Course in Enumeration [2] have examples as well.

(For what it’s worth, the identity can be proved more easily using generating functions, but I don’t think that approach gives as much insight into why the identity is true.)

References

1.  Arthur T. Benjamin and Jennifer J. Quinn.  Proofs that Really Count.  MAA, 2003.
2. Martin Aigner.  A Course in Enumeration.  Springer, 2010.

## A Mathematical Riddle

This past weekend I attended the wedding of a former student, Jake Linenthal.  On the dinner tables at the reception were sheets of paper containing a Mad Libs-style story of how Jake and his wife Abby got engaged, as well as a wedding riddle.  The riddle went something like this:

An evil king has captured the bride and groom for a wedding that is about to take place.  The king says that he will not let the wedding go on unless you can complete a task for him.  First, he blindfolds you.  Then he hands you a standard deck of 52 cards and tells you that 10 of the cards are face up and the rest are face down.  Finally, he says that you have to divide the 52 cards into two stacks such that each stack has the same number of face-up cards.  You cannot remove the blindfold, you cannot tell whether a card is face up or face down simply by touching it, and the cards are indestructible.

At first I could not see how it would be possible to complete such a task.  There simply didn’t seem to be enough to work with here.

Then, after realizing that the rules do allow you to turn cards over, and working through an example where you have a deck of four cards with two of them face up, I found the solution.

Solution: Divide the deck into a stack of 42 cards and a stack of 10 cards.  Then turn over every card in the 10-card stack.

Why does this work?  You know that 10 cards are face up.  Suppose x of the face-up cards are in the stack of 42 cards.  That means that the stack of 10 cards has $10-x$ cards that are face up and x cards that are face down.  Turning over every card in the 10-card stack then gives you $10-x$ cards that are face down and x cards that are face up.  With x face-up cards in the 42-card stack and x face-up cards in the 10-card stack, you’ve completed the king’s task and saved the wedding.

The form of the solution means that we can easily generalize the problem.  Suppose you have an n-card deck in which m cards are face up, and you have to divide all the cards into two stacks with the same number of face-up cards in each.  Then the solution is to (1) Divide the cards into a stack of $n-m$ cards and a stack of m cards, and then (2) Turn over every card in the stack of m cards.

Interestingly enough, with this solution you won’t know how many face-up cards are in each stack.  But, fortunately, the task doesn’t require that.