On the 3-Rectangles Problem

A mathematician is a machine for turning coffee into theorems —Paul Ërdos, 1913–1996

Introduction

The problem below corresponds to the $28$th item on the Mega Test, and it's the two-dimensional counterpart of a much more difficult "three-dimensional puzzle" on the same test (which we will cover in due course). A few years ago, I encountered a version of this problem on (the test is no longer available, and the site has since changed). Instead of asking for the maximum number of areas formed by three rectangles, it asked about the case of four rectangles. One might assume that the test I took would not reveal any answers after completion, as some questions were similar to those of tests.

However, they did provide answers. For that particular problem, they included a diagram showing an arrangement that supposedly maximized the number of regions, along with a humorous comment about needing a to see all of them. To this day, I remain unsure whether the authors of the test considered their explanation sufficient or if it was merely a hint to avoid fully disclosing the method behind the answer. In any case, it may come as a surprise to them, but they did not actually prove their answer. What they provided was a possible configuration that yielded a certain number of areas, but they did not demonstrate that it was the optimal solution.

An analogy may drive the point home; imagine you devise a particular geometrical arrangement, and a skeptic comes along, casting doubt on the possibility of another, more efficient arrangement. The only way you can answer the skeptic and prevent the start of an endless cycle of questions and responses is if you can prove that no other configuration could possibly yield more regions. Let us not commit the same error; keep in mind, while attempting the following puzzle, the question, "How do I know this is the case?"

A Rectangular Puzzle

If three mutually are drawn on a flat surface, what is the maximum number of completely bounded areas that can thereby be formed, considering only the sides of the rectangles as bounds and counting only the areas that are not further subdivided? (The figure below illustrates two intersecting rectangles together with three completely bounded areas.)$^{1}$

Solution

Fig.1 Three intersecting rectangles (squares) formed by rotating two of them by $15°$ and $60°$ about their common center, yielding a maximum of $25$ areas. The is marked as a dashed reference at $0°$.

For me at least, it's more natural to consider a related and perhaps more important question: Into how many parts at most can two-dimensional space be divided by $n$ rectangles? Because it is clear that the author of the test has drawn inspiration from classical questions in , such as determining the maximum number of regions into which $n$ circles can divide the plane. But instead of circles, he has modified the problem to involve rectangles.$^{2}$

In an earlier series, we saw that the maximum number of areas into which the plane can be divided by $n$ lines is achieved if the lines are in (every two of them intersect, no two of them are parallel, and no three of them are concurrent), thereby maximizing the number of points of intersection. We will apply the same topological principle, but this time to the sides of the rectangles.

$n$ rectangles will divide the flat surface into a maximum number of areas if any two rectangles intersect (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, and no three of them are concurrent$^{3}$). However, before plunging right into the recursion, we shall prove that two rectangles can at most intersect in $8$ points.

We fix rectangles $A$ and $B$. Each side (a ) of $A$ is a straight segment crossing the $B$; a straight segment can meet the boundary of a convex polygon in at most two points (enter and exit). Since $A$ has $4$ sides, the boundary of $A$ meets the boundary of $A$ in at most $4\times2=8$ points. So any pair of rectangles contributes at most $8$ intersection points.

Now, suppose that $k$ of the rectangles have already been drawn in the plane; let us draw the $(k+1)$$^{th}$ rectangle and see by how much it increases the number of regions/areas into which the plane is divided. The $(k+1)$$^{th}$ rectangle intersects each of the $k$ rectangles in $8$ points; these $8k$ points divide the boundary of the $(k+1)$$^{th}$ rectangle into $8k$ arcs, each being a connected path along its boundary between two consecutive intersection points. Each of these arcs divides the regions formed by the first $k$ rectangles into two parts. Since one rectangle divides the plane into two regions, the total number of parts after drawing the $n$$^{th}$ rectangle is,

$$2+8+16+24+32+...+8(n-1)$$

$$=2+8(1+2+3+4+...+(n-1))$$

$$=2+8\frac{n(n-1)}{2}=4n^{2}-4n+2$$

To obtain our final answer, we only need to substitute $n=3$ into our formula and subtract $1$ to account for the , which is the complement of the union of all rectangle areas (i.e., "the area that does not belong to any rectangle"). Thus,

$$(4n^{2}-4n+2)-1=(4\cdot3^{2}-4\cdot3 + 2)-1=25$$

1. Adapted from Hoeflin, R. K. (1985, April). Problem 28 in The Mega Test. Omni, 7(4), p. 129.

2. Although the problem could technically be interpreted as drawing the rectangles on a finite flat surface, we will still get the same result because we are only counting areas whose sole bounds are the sides of the rectangles, discarding the complement of the union of all rectangles, regardless of whether this complement is finite or infinite.

3. Such sets of rectangles always exist; in fact, it is possible to draw infinitely many rectangles in the plane in such a way that any two of them intersect in $8$ points, but no three of them are concurrent. For example, construct $n$ intersecting rectangles of the same size by fixing a base rectangle (the unrotated rectangle), then superimpose $n-1$ congruent rectangles with the base rectangle, and successively rotate each of these about their common center (i.e., the center of the unrotated rectangle) by increasing non-multiples of $90°$ (see Fig.1). This family clearly has the desired properties.

Omni IQ Puzzles

Search This Blog