Skip navigation

Tag Archives: number theory

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!

%d bloggers like this: