Circles, Triangles, and the Maximum Number of Regions

Strange as it may sound, the power of mathematics rests on its evasion of all unnecessary thought and on its wonderful saving of mental operations. —, 1838–1916

Introduction

Some look deceptively simple. Draw a few curves or straight lines, let them intersect as much as possible, and count the regions they create. However, once we impose a restriction, once we ask for the maximum possible number of regions, things begin to look a bit dizzy.

Here, once again, we meet a Hoeflinian puzzle, but this time it comes straight from the Titan Test, which was supposed to be even harder than the Mega Test. In another post, we solved a very similar puzzle in nature, involving three mutually intersecting rectangles. That problem already showed us that counting regions is not quite as straightforward as it might first appear: maximizing areas requires a special kind of topological thinking, a bit different than what one is accustomed to in a typical geometric problem.

The shapes themselves are almost incidental. What really matters is the structure produced by their intersections: which curves meet, where they meet, how those intersections divide the plane, and which resulting regions satisfy the conditions of the problem.

This is what makes these puzzles so interesting. Our usual geometric instincts tend to focus on lengths, angles, areas, and other quantities that can be measured. Here, however, we are being asked to look at a figure in a rather different way. We have to think about its topological structure—about connectivity, boundaries, intersections, and subdivisions—while still exploiting the geometric freedom available to us and, interestingly enough, we leverage our understanding of the Euclidean axioms all the time. The present problem takes this idea a step further.

Five Shapes, Countless Possibilities

Three mutually intersecting circles (as illustrated below) can yield a maximum of seven completely bounded areas, counting only areas that are not further subdivided. What is the maximum number of completely bounded areas not further subdivided that can be obtained using plus two triangles?

Fig. 1 From Uncommonly Difficult IQ Tests. By Darryl Miyaguchi.

Solution

We begin with the fact that three circles can yield up to seven completely bounded areas. Then, let us draw the first triangle and see by how much the number of bounded regions/areas increases. To maximize the number of regions, all of the triangles are assumed to be in general position $^{1}$. A triangle may intersect each circle in up to $6$ points (each of its three sides can cross the circle twice, as each side "enters" the circle and "exits" it).

The first triangle therefore intersects each of the $3$ circles in $6$ points; these $3\times6=18$ points divide the triangle into $18$ arcs, i.e., connected paths along its boundary between two consecutive intersection points. Each of these arcs divides one of the regions formed by the given $3$ circles in two. Consequently, the number of new bounded regions so far is $7+18=25$. By similar reasoning, the second triangle intersects the $3$ circles in $18$ points and the first triangle in $6$ points (each side of one triangle “enters” and “exits” another triangle). As a result, the new grand total number of bounded regions is $25+(18+6)=25+24=49$, which is the maximum possible number of areas achievable. Such a set of circles and triangles is nonempty, as illustrated below$^{2}$

Fig. 2. Two of the circles are colored for better appreciation. To make this construction easier, start with the triangles and then draw the circles following the above specifications. You may need a magnifying glass to count all of the regions!

We may generalize the preceding argument to an $n$ number of triangles as follows: Suppose that $k$ of the triangles have already been drawn in the plane such that they intersect each other in general position and they intersect the three circles also in general position; let us draw the $(k+1)$$^{th}$ triangle and see by how much it increases the number of bounded regions/areas into which the plane is divided. The $(k+1)$$^{th}$ triangle intersects each of the $k$ triangles in $6$ points; these $6k$ points divide the boundary of the $(k+1)$$^{th}$ triangle into $6k$ arcs. Each of these arcs divides the regions formed by the first $k$ triangles into two parts.

Moreover, the $(k+1)$$^{th}$ triangle intersects the three circles in $18$ points, further dividing this triangle into $18$ additional arcs, each of which divides one of the regions formed by the given $3$ circles in two. Hence, the total number of newly added bounded regions is $6k+18$. Since we begin with seven regions, the total number of parts after drawing the $n$$^{th}$ triangle is

$$7+(6+12+18+...+6(n-1))+(\underbrace{18+18+18+...+18}_{n\:\text{times}})$$

$$=7+6(1+2+3+...+n-1)+18n=7+ 6\cdot\frac{(n-1)n}{2}+18n$$

$$=7+3n^{2}-3n+18n=7+3n^{2}+15n=3n^{2}+15n+7$$

If we substitute $2$ for $n$, we obtain

$$3\cdot(2)^{2}+15\cdot2+7=3\cdot4+30+7=12+30+7=49$$

Which is the same answer. You can check that the formula agrees with the case $n=1$ as calculated in the first argument.

Notes

1. That is, if no two of them are tangent, no two sides are parallel or coincident, and none of them lies entirely within or outside another, no three of them are concurrent, and any intersecting circle-triangle pair fulfills the aforementioned conditions when applicable. Note that the circles are already in general position.

2. In principle, such sets of figures always exist. It is possible to draw an infinite number of $n$ triangles and three circles with the desired properties. For instance, construct $n$ intersecting equilateral triangles of the same size by fixing a base triangle (the unrotated triangle), then superimpose $n-1$ congruent triangles with the base triangle, and successively rotate each of these about their common center (i.e., the center of the base triangle) by increasing non-multiples of $\frac{2\pi}{3}$. Finally, draw three circles such that each intersects each triangle in $6$ points and meets each other in $2$ points, and no two circles intersect at the same point in a given triangle.

References

1. From Hoeflin, R. K. (1990, April). Problem 34 in the Titan Test. Retrieved September 7, from http://miyaguchi.4sigma.org/hoeflin/titan/titan.html

Omni IQ Puzzles

Search This Blog