Yesterday was Halloween at the San Francisco math circle, and our current theme there is set theory.  So we worked on the problem of assigning infinitely many candy bars, numbered 1, 2, 3, and so on, to infinitely many people, who were conveniently dressed in costumes with the same list of numbers.  That’s an easy start: give candy bar number 1 to person wearing costume 1, and so on.

Now what do you do when one more person shows up wearing costume number 0?

The usual answer is that person 1 hands their candy bar to 0, and person 2 hands their candy bar to 1, and so on.  There are plenty of “lateral thinking” kinds of answers you’ll get from students, like everyone donating a microscopic crumb of their candy bar to make one for the new person (which, of course, would create much too big of a bar when you’re done!).  But these sixth graders came up with their own take on this idea: person 10 hands their bar to person 0, person 110 hands theirs to person 10, and so on.  Now we see how we can do this without making everyone swap candy bars!  In fact it’s “exponentially few” instead of the usual linear solution.

Then we wondered what might happen if there was another infinite party at my neighbor’s house across the street.  Conveniently, they also had one person in costume for each positive integer.  But they had a big problem: the first party’s purchase of infinitely many candy bars left all the store shelves empty. What are they going to do?

Eventually, with a lot more leading than I had hoped to do, we arrived at the idea of passing out the candy bars so that if the people are numbered like this:

``` Party 1:  1  2  3  4  5  6  7  8  9 ...
Party 2:  1  2  3  4  5  6  7  8  9 ...```

then we could assign the candy bars like this:

``` Party 1:  1  3  5  7  9 11 13 15 17 ...
Party 2:  2  4  6  8 10 12 14 16 18 ...```

But what if there aren’t just two parties, but infinitely many?  The houses on my street are also numbered 1, 2, 3, …

I think the usual solution to that problem is to pass out the candy bars “diagonally”, like this:

``` Party 1:  1  3  6  10  15 ...
Party 2:  2  5  9  14 ...
Party 3:  4  8 13 ...
Party 4:  7 12 ...
Party 5: 11 ...```

But my students had a better idea.  They wanted to repeat the process that you use for 2 parties.  Now, I had some concerns about this.  For instance, if you try to accommodate the second infinite party by repeating the process we used when person 0 showed up, it won’t work out very well.  If you repeat that process infinitely many times, there isn’t a number to tell you which candy bar you’ll end up with when it’s all done.  But one sixth grader told me that we could use this process to combine party 1 and 2, and then 2 and 3, and then 3 and 4, and so on, and that way nobody would have to wait infinitely many steps to get their proper candy bar.  After thinking about it for a little while, I was convinced that she was correct.  We would start out with party 1 and party 2 as above, with the odd and even numbers, and then the even numbers in turn would get split among party 2 and party 3, with party 3 getting the multiples of four, and then those would in turn be shared between party 3 and party 4, and so on. We end up with this:

``` Party 1:  1  3  5  7  9 ...
Party 2:  2  6 10 14 ...
Party 3:  4 12 20 ...
Party 4:  8 24 ...
Party 5: 16 ...```

and now you can see that at the top of each column we have the odd numbers, and then we double the number for each step down, so no matter what costume you’re wearing and what party you’re at, you can figure out what candy bar you get.  And, knowing what power of 2 divides your candy bar number, and what odd number is left after dividing it out, we can figure out exactly who you are and which party you’re attending.  So, each person gets one candy bar, and everyone is happy.  Also, this turns out to be an “exponential” solution instead of the usual “quadratic” one.  Is the quadratic really simpler?  I certainly could write down a formula for the candy bar number for person #k at party #n much more easily with this exponential situation than I could in the quadratic (diagonal) one.

Of course, after finding this I wondered if it was already well-known, and maybe it’s not as a solution to the Cantor problem.  I think her idea, iterating the solution for two parties instead of coming up with something new for the infinite case, is brilliant and much more intuitive to understand than the usual diagonal trick.  This arrangement of the integers is already known: among other things, it’s in the Encyclopedia of Integer Sequences. But this particular application of it is still pretty nice!

By the way, since this is my first post, you might want to visit the about page for this blog.  Let me know if you have any suggestions for design, layout, theme, or any of that; I don’t know much about graphic design.  I also welcome any interesting math problems you might be interested in having me write about. And, welcome!

1. This arrangement of the positive integers, based on the highest power of two that is a divisor also comes up in an unusual induction proof of the Fundamental Theorem of Algebra. The induction is – guess what – on the highest power of two that divides the degree of the polynomial.

This is the form of the FTA to prove: Each non-constant polynomial with real coefficients has a complex root.
So, the base case includes all odd-degree polynomials. Linear polynomials, cubics, quintics, and so on, with real coefficients have a real root by applying the Intermediate Value Theorem.

The induction hypothesis is that each non-constant polynomial with real coefficients, of degree divisible by at most 2^k, has at least one complex root.

What’s bizarre is that the reduction is from a degree n polynomial to several degree C(n,2) polynomials. So, a degree 4 polynomial would be reduced to some degree C(4,2) = 6 polynomials, and a degree 6 polynomial would be reduced to some degree C(6,2) = 15 polynomials (which lands us in the base case). So, even though the sequence 4, 6, 15 increases, the high power of 2 that divides into them is decreasing!

2. When I did a similar problem with my math circle a couple of years ago, one student suggested assigning candy bars 2, 2^2, 2^3, 2^4 … to the people from the first party, candy bars 3, 3^2, 3^3, 3^4, … to the people from the second party, and so on using powers of prime numbers. Of course, this leaves a lot of candy bars left over.

The other solution I’ve seen is to interweave (alternate) the digits: so person number 985710 from party number 2245 would get candy bar number 908052721405, and so on. This works best if the people and the parties and the candy bars are numbered starting with 0.

• I really like that first solution, Linda.

I recently had a student come up with a faulty answer that I thought was beautiful: when trying to match fractions to the integers, just erase the fraction sign. So 1/2 gets mapped to 12. The students thought it was great, until someone figured out that 13/4 and 1/34 would both get mapped to the same place. One student came up with the somewhat elaborate fix of writing all the fractions in base 9, and using the 9 in place of the division bar. I think your second interweaving solution gives us an even more elegant solution, though.

Great post, Josh, and great to have you blogging.