9,10,11 |
| :---: | :---: | :---: |
|  | Induction (other) |  |
|  | Invariants |  |
|  | Pairing and Grouping; Bijections |  |

Authors: Bogdanov I.i., von der Flaass D.

On a plane, a square is drawn with its sides horizontal and vertical. Several segments parallel to the sides are drawn inside it, such that no two segments lie on the same line and do not intersect at a point that is internal for both segments. It turns out that the segments divide the square into rectangles, and every vertical line that intersects the square and does not contain any of the segments of the partition intersects exactly \( k \) rectangles of the partition, while every horizontal line that intersects the square and does not contain any of the segments of the partition intersects exactly \( l \) rectangles. What could be the number of rectangles in the partition?
Let's take a vertical line $h$ passing through the left side of the square and move it to the right. Consider the moment when it passes through some segment of the partition $J$ (by the condition, such a segment at this moment is only one; let $a$ rectangles adjoin it from the left and $b$ from the right). The number of rectangles that intersect $h$ at this moment decreases by $a$ and increases by $b$; and since it should not change, then

$a=b$. We can reason in different ways from here.

The first way. By induction on $k$, we will prove that the number of rectangles is $k l$. The base case ($k=1$) is obvious. Consider all the rectangles of the partition that adjoin the bottom side of the square; there are $l$ of them, because a horizontal line passing close enough to this side intersects only them. We will divide them into groups of consecutive rectangles of equal height (see the left figure). The upper boundary of each such group is one segment.

Consider one such group with the upper segment $I$. Note that the vertical segments bounding this group continue above $I$. Indeed, otherwise, say, the upper end of the left vertical segment $J$ lies on $I$; then one rectangle adjoins $J$ from the right, and more than one from the left (since $J$ is a boundary for the group). As shown above, this is impossible.
![](https://cdn.mathpix.com/cropped/2024_05_06_08342b966a7aba566077g-09.jpg?height=314&width=1260&top_left_y=2057&top_left_x=408)

Remove this group and "extend" the rectangles lying above $I$ to the bottom side of the square. Since the same number of rectangles adjoin $I$ from above and below, any horizontal line will still intersect $l$ rectangles.

Perform this operation with each group (see the right figure). We will remove exactly $l$ rectangles; in this case, each vertical line will intersect one rectangle less than before, that is, $k-1$ rectangles. By the induction hypothesis, the total number of rectangles will become $(k-1) l$, and thus, before the reconstruction, it was $(k-1) l + l = k l$.

The second way. Consider any rectangle of the partition $P$ and a vertical line $v$ intersecting it (not containing a segment of the partition). Let $v$ intersect $i-1$ rectangles of the partition lying above $P$; in this case, we will say that $P$ has a vertical number $i$ on the line $v$. Similarly, we define

Consider any horizontal segment of the partition $I$ and move the vertical line $v$ intersecting $I$ from left to right. Consider the moment when $v$ contains some segment of the partition (lying above or below $I$). As shown at the beginning of the previous solution, the same number of rectangles adjoin this segment from the left and right. Therefore, the vertical number of any rectangle $P$ adjoining $I$ does not change at this moment; moreover, the numbers of adjacent rectangles adjoining $I$ from the same side are equal, and for those adjoining from different sides, it differs by 1. Thus, each rectangle $P$ has the same number on all vertical lines containing it. Similar statements are true for horizontal numbers.

Now fix a number $i$ and consider all rectangles $P_{1}, \ldots, P_{t}$ having a vertical number $i$ (they are numbered according to the abscissas of their left boundaries from left to right). We will move the vertical line $v$ from the left side of the square to the right. At each moment (except those when it contains a segment of the partition), $v$ intersects exactly one of the rectangles $P_{s}$; therefore, the right side of the next rectangle $P_{s}$ lies on the same line as the left side of the following rectangle $P_{s+1}$ (see the figure). Then these rectangles adjoin the same vertical segment of the partition from different sides, so the horizontal number of the rectangle $P_{s+1}$ is 1 more than the horizontal number of $P_{s}$. It is clear, finally, that the horizontal numbers of the rectangles $P_{1}$ and $P_{t}$ are 1 and $l$; thus, $t=l$.

![](https://cdn.mathpix.com/cropped/2024_05_06_08342b966a7aba566077g-10.jpg?height=340&width=560&top_left_y=802&top_left_x=749)

Thus, for each of the $k$ vertical numbers, there are exactly $l$ rectangles with such a number; therefore, the total number of rectangles is $k l$.

## Answer

$k l$.