Kvant Math Problem 450
Normalize the width of the bottom rectangle to $1$, and let the common height of all rectangles be fixed.
Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 12m12s
Source on kvant.digital
Problem
A system of rectangles with $n$ floors (Fig. 2) is constructed as follows. Starting from the bottom rectangle, which forms the first floor, the top side of each rectangle is divided in the ratio $1 : 2 : 3$; on the three resulting segments, rectangles of the same height as the original are built, and this process continues up to the top floor. From the resulting set of rectangles, a subset is selected consisting of pairwise non-congruent rectangles (one such subset in the figure is shown in red). Prove that there exists a vertical line intersecting no more than two of the selected rectangles.
Insert illustration
A. Kleptsyn
Exploration
Normalize the width of the bottom rectangle to $1$, and let the common height of all rectangles be fixed.
Each rectangle corresponds to a word in the symbols $1,2,3$. When a rectangle of width $w$ produces the next floor, its three children have widths
$$\frac{w}{6},\qquad \frac{2w}{6},\qquad \frac{3w}{6}.$$
Hence every rectangle width is obtained by multiplying several factors chosen from
$$\frac16,\quad \frac13,\quad \frac12 .$$
The geometric problem can be translated into a problem about intervals on the horizontal axis. A rectangle is intersected by a vertical line $x=\text{const}$ precisely when $x$ belongs to the horizontal projection of that rectangle. Thus, if we regard each selected rectangle as its horizontal interval, the number of selected rectangles met by a vertical line equals the number of selected intervals containing the corresponding point.
The task becomes: show that among the selected intervals there is a point of the base segment contained in at most two of them.
Problem Understanding
Since all rectangles have the same height, two rectangles are congruent exactly when they have the same width.
Suppose a rectangle lies on floor $k+1$. If during the $k$ construction steps the factors $\frac12,\frac13,\frac16$ are used respectively $a,b,c$ times, then
$$a+b+c=k$$
and its width equals
$$\left(\frac12\right)^a \left(\frac13\right)^b \left(\frac16\right)^c = \frac1{2^{a+c}3^{b+c}}.$$
Set
$$i=a+c,\qquad j=b+c.$$
Then every rectangle width has the form
$$\frac1{2^i3^j}.$$
Conversely, for every pair of nonnegative integers $(i,j)$ with
$$\max(i,j)\le n-1,$$
there exists a rectangle of width $\frac1{2^i3^j}$ in the first $n$ floors. Indeed, taking $k=\max(i,j)$ and $c=i+j-k\ge0$, one obtains suitable nonnegative integers $a=i-c$, $b=j-c$.
Thus the possible congruence classes are in one-to-one correspondence with the pairs
$$(i,j),\qquad 0\le i,j\le n-1,$$
and the width of the corresponding class is
$$\frac1{2^i3^j}.$$
Because the chosen rectangles are pairwise non-congruent, at most one selected rectangle can belong to each such class.
Proof
Let $S$ be the set of selected rectangles. For a point $x$ of the base segment $[0,1]$, denote by $m(x)$ the number of selected rectangles whose horizontal projections contain $x$. Then $m(x)$ is exactly the number of selected rectangles intersected by the vertical line through $x$.
Integrating $m(x)$ over $[0,1]$ gives
$$\int_0^1 m(x),dx = \sum_{R\in S} \operatorname{width}(R),$$
because each rectangle contributes the length of its horizontal projection.
Since at most one rectangle is selected from each congruence class,
$$\sum_{R\in S} \operatorname{width}(R) \le \sum_{i=0}^{n-1}\sum_{j=0}^{n-1} \frac1{2^i3^j}.$$
The double sum factors:
$$\sum_{i=0}^{n-1}\sum_{j=0}^{n-1} \frac1{2^i3^j} = \left(\sum_{i=0}^{n-1}\frac1{2^i}\right) \left(\sum_{j=0}^{n-1}\frac1{3^j}\right).$$
Using the geometric-series formulas,
$$\sum_{i=0}^{n-1}\frac1{2^i} = 2-2^{1-n} <2,$$
and
$$\sum_{j=0}^{n-1}\frac1{3^j} = \frac32\left(1-3^{-n}\right) <\frac32.$$
Therefore
$$\int_0^1 m(x),dx < 2\cdot\frac32 = 3.$$
The average value of $m(x)$ on $[0,1]$ is thus strictly less than $3$. If every point $x$ satisfied $m(x)\ge3$, then the integral would be at least $3$, which is impossible. Hence there exists a point $x_0\in[0,1]$ with
$$m(x_0)<3.$$
Since $m(x_0)$ is an integer,
$$m(x_0)\le2.$$
The vertical line through $x_0$ intersects at most two selected rectangles.
This is exactly the required statement. ∎