XXVIII - II - Task 6

What is the maximum number of parts that the edges of $ n $ squares can divide a plane into?
The common part of the boundaries of two squares is either a finite set of points (and in this case, there are at most $8$ points, since each side of one square can intersect the boundary of the other square in at most two points), or it contains a segment (and in this case, it is a segment, the union of two segments - parallel or perpendicular, or is the union of a segment and a point - see Fig. 11). In each case, this common part consists of at most eight connected parts, each of which is a point, a segment, or the union of two segments with a common end.
Let there be $n$ squares $K_1, K_2, \ldots, K_n$ on the plane, where $n$ is some natural number. Suppose the boundaries of these squares divide the plane into $a_n$ parts. We now draw the $(n + 1)$-th square $K_{n+1}$. The boundary of each of the $n$ given squares $K_i$ defines on the boundary of the square $K_{n+1}$ a figure $F_i$ composed of at most eight connected parts. The figure $F = F_1 \cup F_2 \cup \ldots \cup F_n$ thus consists of at most $8n$ connected parts (which are points, segments, or unions of segments with common ends). Therefore, the difference between the boundary of the square $K_{n+1}$ and the figure $F$ consists of at most $8n$ connected parts, which are segments or unions of segments. Each such part of the boundary of the square $K_{n+1}$ divides into two parts one of the parts of the plane obtained after drawing the squares $K_1, K_2, \ldots, K_n$. Therefore, the number $a_{n+1}$ of parts into which the boundaries of the squares $K_1, K_2, \ldots, K_n, K_{n+1}$ divide the plane satisfies

We obviously have $a_1 = 2$, since the boundary of one square divides the plane into two parts. Therefore, from formula (1), by easy induction, it follows that for any natural number $k$,

where $a_k$ is the number of parts into which the boundaries of some $k$ squares divide the plane. Transforming the right-hand side of this formula, we get

or, finally,

We will now prove that for any natural number $n$ there exist $n$ squares whose boundaries divide the plane into $(2n - 1)^2 + 1$ parts, i.e., equality holds in formula (2). Consider, for example, any $n + 1$ squares $K_1, K_2, \ldots, K_n, K_{n+1}$ inscribed in a fixed circle $O$. Note that there is no point that belongs simultaneously to the boundaries of three of the considered squares. The sides of these squares have the same lengths and are chords of the given circle. And through no point inside the circle (different from its center) do three chords of the same length pass.
On the arc of the circle $O$ connecting two consecutive vertices $A$ and $B$ of the square $K_{n+1}$, there lies exactly one vertex of the square $K_j$ for $1 \leq j \leq n$. Therefore, any side $\overline{AB}$ of the square $K_{n+1}$ intersects the boundary of the square $K_j$ in two points, and the boundary of the square $K_{n+1}$ intersects the boundary of the square $K_j$ in eight points. From the initial remark, it follows that for $j = 1, 2, \ldots, n$, we obtain pairwise disjoint eight-point sets in the intersection of the boundary of the square $K_j$ with the boundary of the square $K_{n+1}$. Thus, on the boundary of the square $K_{n+1}$, we have $8n$ points belonging to the union of the boundaries of the squares $K_1, K_2, \ldots, K_n$. These points determine $8n$ connected figures on the boundary of the square $K_{n+1}$, which are segments or unions of segments with a common end. Each of these figures divides into two parts one of the parts of the plane obtained after drawing the squares $K_1, K_2, \ldots, K_n$. Therefore, we have the relationship $a_{n+1} = a_n + 8n$. Hence, given $a_1 = 2$, by easy induction, it follows, similarly as before, that for any natural number $k$ and $k$ squares inscribed in a fixed circle, the formula

We have thus proved that the maximum number of parts into which the boundaries of $n$ squares can divide the plane is equal to $(2n - 1)^2 + 1$.
Note 1. In the given solution, we did not use the assumption that the considered figures are squares in an essential way. If they were rectangles or even any convex quadrilaterals, the reasoning would proceed in the same way. Therefore, the maximum number of parts into which the boundaries of $n$ convex quadrilaterals can divide the plane is equal to $(2n - 1)^2 + 1$. However, for concave quadrilaterals, this number is larger.
Note 2. One can analogously prove that the maximum number of parts into which the boundaries of $n$ triangles can divide the plane is equal to $3n^2 - 3n + 2$. We leave the detailed proof to the reader as an exercise.