## Category Archives: Integer Sequences

Thanks to Gary Antonick of Numberplay for inviting me to contribute once more, with a problem on cutting a pizza that is somewhat related to my previous post on dividing the plane.

Rather than give any spoilers for that problem, I’ll offer a few other related problems.

Venn diagrams are traditionally drawn with circles.  With 0 circles, you have 1 region.  With 1 circle, 2 regions.  With 2 circles, 4 regions.  Why do we stop with 3 circles, 8 regions?

I’ve seen some interesting Venn diagrams for 5 sets. Most of them use ellipses:

while others use triangles, while some use …polyominoes?  Let’s see, 5 sets will need 32 regions – is that the most we can make using ellipses?  Using triangles?  Why do I see these diagrams with 5 sets and not with 6 or more?  You can make Venn diagrams with more than 5 sets, but they look pretty weird! Although when colored properly, these Venn diagrams can be quite beautiful.

The next post in this series will answer the questions about how many regions can be created using these various shapes and pose some new ones.  Several of these images are from a great article about symmetric Venn diagrams – I’m more concerned here about counting the number of possible regions, like in the Numberplay column, rather than in ensuring that we have a Venn diagram (where every possible intersection of sets exists exactly once).

Several years ago, I think in 2002, there was a Mandelbrot contest problem that asked for the largest number of regions in the plane that could be generated by two triangles.  The answer turns out to be 8, and it’s interesting to think about why there can’t be more.

Naturally, this got me wondering about the integer sequence: what is the largest number of regions in the plane you can generate using two n-gons?  At first this problem seems very simple: 8, 10, 12, 14, …

But after a little while, I realized it went 8, 18, ?, 38, ?, …, where the number of regions for two 2n-gons is easy to compute.  You can probably figure out what I was assuming that wasn’t actually a requirement.

For odd numbers of sides, things are much more complicated.  In fact, to this day I’m still not sure of the answer.  I have a drawing that I think gives the maximum number of regions, but I haven’t been able to prove that there isn’t a better drawing out there somewhere.  Anyone have any ideas for me?

Problems like this one are appealing to me because they are easy to play with but hard to finish.  There are more elementary ones (like regions created by lines), classics (like regions in space determined by planes, as in Polya’s famous video), interesting side notes (ever wonder why we only draw Venn diagrams with 3 circles and not with 4?  Have you seen diagrams with 4 sets — and noticed that they don’t use circles?), and difficult ones like the case of two odd-sided polygons.

Maybe this would make a good topic for a future Numberplay column.

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!