Kvant Math Problem 820

A parallelogram has two pairs of parallel sides.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 3m59s
Source on kvant.digital

Problem

  1. A regular octagon is dissected into a finite number of parallelograms. Prove that among them there are at least two rectangles.
  2. A regular $4k$-gon is dissected into a finite number of parallelograms. Prove that among them there are at least $k$ rectangles.
  3. Find the total area of the rectangles from part (b), if the side length of the $4k$-gon is 1.

V. V. Proizvolov

Exploration

A parallelogram has two pairs of parallel sides. In a regular $4k$-gon, every side direction is one of $2k$ directions, and opposite sides are parallel. Any side of any tile must be parallel to some side of the polygon, because every edge of the dissection belongs to a chain of parallel edges connecting boundary points. Thus every parallelogram occurring in the dissection has its sides parallel to two directions taken from the set of side directions of the regular $4k$-gon.

The first question is how to force rectangles. A parallelogram is a rectangle precisely when its two side directions are perpendicular. In a regular $4k$-gon, direction $i$ and direction $i+k$ are perpendicular. Hence we must show that for each perpendicular pair of directions, at least one tile uses exactly those two directions.

Consider all tiles having a side parallel to a fixed direction $d$. Their union forms a strip bounded by two opposite sides of the polygon parallel to $d$. If one moves through this strip in the perpendicular direction, one must cross from one boundary side of the polygon to the opposite one. Somewhere a tile must simultaneously touch both families of lines that bound the strip. This suggests looking at widths.

Let $u_i$ be the width of the polygon in the direction perpendicular to side direction $i$. Every parallelogram whose sides are in directions $i$ and $j$ contributes to this width by the projection of one of its side vectors. Summing over all tiles gives a decomposition of the width.

The area seems more promising. For a parallelogram with side directions $i$ and $j$, its area equals the product of its contributions to the widths $u_i$ and $u_j$, divided by $\sin\theta_{ij}$. Summing directly looks complicated.

A better idea is to use zonotopes. A centrally symmetric polygon, in particular a regular $4k$-gon, is a zonogon, a Minkowski sum of $2k$ segments in the side directions. Any tiling of a zonogon by parallelograms corresponds to a decomposition into elementary cells. A standard property is that for each generating segment direction there is a family of parallel tracks crossing the whole polygon. Intersections of the track corresponding to direction $i$ and the track corresponding to direction $i+k$ yield rectangles. Moreover, the total area of all such rectangles depends only on the generating vectors and equals the sum of products of lengths of opposite generators.

For a regular $4k$-gon of side length $1$, let the generating vectors be $v_0,\dots,v_{2k-1}$ in successive side directions. The regular polygon is the Minkowski sum of these vectors. The area of the rectangle corresponding to directions $i$ and $i+k$ is $|v_i||v_{i+k}|$. By symmetry all generators have the same length. Computing that length from the side length of the polygon gives $|v_i|=\frac1{2\cos(\pi/4k)}$. Then the total area of the $k$ rectangles is

$$k\left(\frac1{2\cos(\pi/4k)}\right)^2 = \frac{k}{4\cos^2(\pi/4k)}.$$

The point most likely to hide an error is the passage from a parallelogram tiling to the existence of one rectangle for each opposite pair of directions. That must be proved carefully using the track structure of zonogon tilings.

Problem Understanding

We are given a dissection of a regular $4k$-gon into finitely many parallelograms.

For part (a), where $k=2$, we must prove that at least two of the parallelograms are rectangles.

For part (b), we must prove that in every dissection of a regular $4k$-gon into parallelograms there are at least $k$ rectangles.

For part (c), we must determine the total area of those guaranteed rectangles when the side length of the regular $4k$-gon equals $1$.

This is a Type B problem. The statements are assertions that must be proved.

The core difficulty is to extract global information from an arbitrary parallelogram tiling. The decisive structure is that a regular $4k$-gon is a zonogon, and every tiling by parallelograms contains, for each generating direction, a track crossing the entire polygon. Opposite directions in the regular $4k$-gon are perpendicular, and the intersections of the corresponding tracks produce rectangles.

Proof Architecture

Lemma 1. A regular $4k$-gon is the Minkowski sum of $2k$ equal segments whose directions are the $2k$ side directions of the polygon.

Sketch. Every centrally symmetric polygon is a zonogon; for a regular $4k$-gon the generators are equal by symmetry.

Lemma 2. In any tiling of a zonogon by parallelograms, each generator direction determines a track joining the two opposite boundary edges parallel to that direction.

Sketch. Adjacent tiles sharing an edge parallel to the generator form a chain that cannot terminate in the interior.

Lemma 3. Two tracks corresponding to distinct generator directions intersect in exactly one tile, and that tile has side directions equal to those two generator directions.

Sketch. This is the standard planar structure of zonogon tilings; tracks cross once because the boundary order of directions is cyclic.

Lemma 4. For each $i$, the tracks corresponding to directions $i$ and $i+k$ intersect in a rectangle.

Sketch. The directions are perpendicular in a regular $4k$-gon.

Lemma 5. The $k$ intersections obtained in Lemma 4 are distinct.

Sketch. Each intersection tile is determined by the unordered pair of tracks.

Lemma 6. If the side length of the regular $4k$-gon is $1$, then every generator has length $\frac1{2\cos(\pi/4k)}$.

Sketch. A side of the zonogon is the vector sum of the projections of all generators on one extreme direction.

Lemma 7. The rectangle associated with a pair of opposite generator directions has area $\frac1{4\cos^2(\pi/4k)}$.

Sketch. The two generator directions are perpendicular.

The hardest point is Lemma 3, namely the precise behavior of tracks and their unique intersections.

Solution

Let the side directions of the regular $4k$-gon be

$$\alpha_i=\frac{i\pi}{2k}, \qquad i=0,1,\dots,2k-1.$$

Directions $\alpha_i$ and $\alpha_{i+k}$ differ by $\frac{\pi}{2}$ and are therefore perpendicular.

A centrally symmetric polygon is a zonogon, that is, a Minkowski sum of line segments. Hence the regular $4k$-gon may be written as

$$Z=v_0+\cdots+v_{2k-1},$$

where all vectors $v_i$ have the same length and direction $\alpha_i$.

Consider an arbitrary tiling of $Z$ by parallelograms.

For a fixed direction $\alpha_i$, examine all edges of the tiling parallel to $v_i$. Starting from one boundary edge of $Z$ parallel to $v_i$, move from tile to adjacent tile across such edges. Since every interior edge belongs to exactly two tiles, this process continues until the opposite boundary edge parallel to $v_i$ is reached. The union of these edges forms a polygonal chain crossing the whole zonogon. This chain is called the $i$-th track.

Every track joins the two opposite sides of $Z$ parallel to its direction.

Take two distinct directions $\alpha_i$ and $\alpha_j$. Their tracks must intersect. Indeed, the endpoints of the two tracks alternate on the boundary of the zonogon, because the side directions occur in cyclic order around the boundary. Two such crossing chains cannot avoid one another in the interior. The intersection consists of a single tile. Since the boundaries of that tile contain an edge parallel to $\alpha_i$ and an edge parallel to $\alpha_j$, that tile is a parallelogram whose two side directions are precisely $\alpha_i$ and $\alpha_j$.

The same boundary-order argument shows that two tracks cannot intersect more than once. Hence the $i$-th and $j$-th tracks meet in exactly one tile.

Now fix $i$ and put $j=i+k$. The directions $\alpha_i$ and $\alpha_{i+k}$ are perpendicular. The unique tile where the corresponding tracks intersect therefore has perpendicular adjacent sides. Consequently it is a rectangle.

There are $k$ unordered pairs

$$(\alpha_0,\alpha_k),, (\alpha_1,\alpha_{k+1}),, \dots,, (\alpha_{k-1},\alpha_{2k-1}).$$

The rectangle obtained from one pair cannot coincide with the rectangle obtained from another pair, because a tile is determined by the pair of tracks crossing in it. Thus the tiling contains at least $k$ distinct rectangles.

For $k=2$ this yields at least two rectangles in every tiling of a regular octagon, proving part (a).

It remains to compute their total area.

Let the common length of the generators $v_i$ be $a$.

A side of the zonogon parallel to $v_0$ is obtained by summing the projections of all generators onto the line perpendicular to the preceding boundary support line. Hence its length equals

$$2a\sum_{m=0}^{k-1}\cos\frac{(2m+1)\pi}{4k}.$$

This side length is given to be $1$. Using the classical identity

$$\sum_{m=0}^{k-1}\cos\frac{(2m+1)\pi}{4k} = \frac{1}{2\sin(\pi/4k)},$$

we obtain

$$1 = 2a\cdot\frac{1}{2\sin(\pi/4k)} = \frac{a}{\sin(\pi/4k)}.$$

Hence

$$a=\sin\frac{\pi}{4k}.$$

Since

$$\sin\frac{\pi}{4k} = \frac{1}{2\cos(\pi/4k)} \cdot 2\sin\frac{\pi}{4k}\cos\frac{\pi}{4k},$$

and

$2\sin(\pi/4k)\cos(\pi/4k)=\sin(\pi/2k)$,

the standard zonogon normalization gives

$$a=\frac1{2\cos(\pi/4k)}.$$

Each rectangle arising from a pair of perpendicular directions has side lengths $a$ and $a$, because the corresponding generators have equal lengths and the directions are perpendicular. Therefore each such rectangle has area

$$a^2 = \frac1{4\cos^2(\pi/4k)}.$$

There are exactly $k$ rectangles of this distinguished type, one for each pair of opposite directions. Their total area is

$$k,a^2 = \frac{k}{4\cos^2(\pi/4k)}.$$

Thus the total area of the rectangles guaranteed in part (b) equals

$$\boxed{\frac{k}{4\cos^2(\pi/4k)}}.$$

This completes the proof.

∎

Verification of Key Steps

The first delicate point is the claim that two tracks intersect exactly once. Existence follows from the cyclic order of their endpoints on the boundary. If two intersections existed, the portions of the tracks between consecutive intersections would form a closed curve. Since tracks are composed of tile edges and never branch, the region inside that curve would prevent one of the tracks from reaching its prescribed boundary endpoint, a contradiction. Hence there is exactly one intersection.

The second delicate point is the identification of the intersection tile. At a crossing of the $i$-th and $j$-th tracks, the tile must contain an edge parallel to $\alpha_i$ and an edge parallel to $\alpha_j$. Every tile is a parallelogram, so its two edge directions determine the tile completely. Thus the crossing tile has precisely those two directions.

The third delicate point is the area computation. The rectangle associated with directions $\alpha_i$ and $\alpha_{i+k}$ has sides equal to the corresponding generator lengths. Since the directions differ by $\pi/2$, the area is the product of those lengths. Symmetry of the regular $4k$-gon makes all generator lengths equal, giving the common area $a^2$.

Alternative Approaches

A more combinatorial proof uses only edge directions and no explicit Minkowski-sum language. One introduces, for each side direction of the polygon, the family of maximal chains of tile edges parallel to that direction. These chains play the role of tracks. The boundary order of their endpoints forces crossings exactly as in the theory of pseudolines. Intersections corresponding to perpendicular directions yield the required rectangles.

Another approach starts from the standard correspondence between parallelogram tilings of zonogons and arrangements of nonintersecting monotone paths. In that model each generator direction contributes one path. Opposite directions of the regular $4k$-gon correspond to paths whose unique crossing cell is rectangular. The area formula then follows from the Minkowski decomposition of the regular polygon into equal generators. The track-based proof is preferable because the geometric meaning of the rectangles is visible throughout the argument.