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.
Uncover A Few 
7 Comments
Hmm, I see one assumption that I started with, but letting go of it didn’t get me over 10 regions.
Maybe looking at some kind of diagram representing all the different kinds of quadrilaterals will give you a clue.
I was about to be frustrated because I had drawn what I was sure was a maximal arrangement with 4-gons, but it only made 17 regions. Then I realized that you’re counting the outside as a region as well… a fact that should have been obvious to me, except that I didn’t draw the triangles, and miscounted the regions they formed in my head.
This is a spectacular question. Do you know if the answer is known?
I’m sure the answer is known for even n, but for odd n, at least as far as I know, it’s an open question. I’ve asked more math olympiad types than professional geometers, though. But the response I always get is “Oh, of course, it’s easy … you can’t get more than (this many) and … wait, I can’t see how to actually get that many.” So there’s a fairly narrow range between what you can easily construct and what you can prove as an upper bound, but I haven’t filled that gap yet by either constructing something better (which I think won’t happen) or by proving you can’t (which I haven’t figured out how to do yet).
Also, my father pointed out that you can actually get 20 regions, not 18, depending perhaps on your definition of “4-gon”.
Clearly, the idea is to maximize the number of intersections between sides of the polygons. (Euler’s formula shows that the number of regions is linear in the number of intersections.) For the 2n case, it is possible to set things up so that every pair of edges intersects, leading to a total of (2n)^2 + 2 regions. Indeed, n^2 + 2 is an upper bound on the number of regions for n odd or even, and is achievable for n even.
It seems, though I cannot prove it off the top of my head, that if you have a 2n+1-gon in the plane then it is impossible to find a straight line that intersects all of the edges. This would reduce the upper bound derived in the last paragraph.
Need to think about this more…
Oops — it turns out it is obvious that you cannot intersect all of the sides of a 2n+1-gon with a straight line… This can be shown by looking at what side of the line each vertex of the polygon is on as we follow the vertices in order. Since they start and end on the same side, and there are an odd number of them, at some point we must have a side that doesn’t cross the line.
Still need to think about this — very cool problem, Josh.
Hi Dave! Thanks for coming by.
Your second comment leads to the best upper bound I’ve seen so far, and yet some playing around leaves me convinced that even that bound can’t be reached. But by how much do we miss?