|
|
 |
Условие
На плоскости нарисован квадрат, стороны которого горизонтальны и вертикальны. В нём проведены несколько отрезков, параллельных сторонам, причём никакие два отрезка не лежат на одной прямой и не пересекаются по точке, внутренней для обоих отрезков. Оказалось, что отрезки разбили квадрат на прямоугольники, причём каждая вертикальная прямая, пересекающая квадрат и не содержащая отрезков разбиения, пересекает ровно k прямоугольников разбиения, а каждая горизонтальная прямая, пересекающая квадрат и не содержащая отрезков разбиения – ровно l прямоугольников. Каким могло оказаться количество прямоугольников разбиения?
Решение
Возьмём вертикальную прямую h, проходящую через левую сторону квадрата, и будем двигать её вправо. Рассмотрим момент, когда она проходит через какой-нибудь отрезок разбиения J (по условию, такой отрезок в этот момент только один; пусть к нему прилегают a прямоугольников слева и b справа). Количество прямоугольников, которые пересекает h, в этот момент уменьшается на a и увеличивается на b; а поскольку оно не должно изменяться, то
a = b. Далее можно рассуждать по-разному.
Первый способ. Индукцией по k докажем, что количество прямоугольников равно kl. База (k = 1) очевидна.
Рассмотрим все прямоугольники разбиения, прилегающие к нижней стороне квадрата; их l штук, ибо горизонтальная прямая, проходящая достаточно близко к этой стороне, пересекает только их. Разобьём их на группы стоящих подряд прямоугольников равной высоты (см. рис. слева). У каждой такой группы верхней границей является один отрезок.
Рассмотрим одну такую группу с верхним отрезком I. Заметим, что вертикальные отрезки, ограничивающие эту группу, продолжаются выше, чем I. Действительно, иначе, скажем, верхний конец левого вертикального отрезка J лежит на I; тогда справа к J примыкает один прямоугольник, а слева – больше одного (ибо J – граничный для группы). Как показано выше, это невозможно.
Выкинем эту группу и "продлим" прямоугольники, лежащие сверху от I, до нижней стороны квадрата. Поскольку сверху и снизу к I прилегало равное количество прямоугольников, любая горизонтальная прямая по-прежнему будет пересекать l прямоугольников.
Проделаем эту операцию с каждой группой (см. рис. справа). Мы выкинем ровно l прямоугольников; при этом каждая вертикальная прямая будет пересекать на один прямоугольник меньше, нежели раньше, то есть k – 1 прямоугольник. По предположению индукции, общее количество прямоугольников станет равно (k – 1)l, а значит, до перестройки оно было равно (k – 1)l + l = kl.
Второй способ. Рассмотрим любой прямоугольник разбиения P и пересекающую его вертикальную прямую v (не содержащую отрезка разбиения). Пусть v пересекает i – 1 прямоугольников разбиения, лежащих выше P; в этом случае будем говорить, что P имеет вертикальный номер i на прямой v. Аналогично определим горизонтальный номер прямоугольника P на горизонтальной прямой, пересекающей его.
Рассмотрим некоторый горизонтальный отрезок разбиения I и будем двигать вертикальную прямую v, пересекающую I, слева направо. Рассмотрим момент, когда v содержит какой-то отрезок разбиения (лежащий выше или ниже I). Как показано в начале предыдущего решения, слева и справа к этому отрезку примыкает одинаковое количество прямоугольников. Значит, вертикальный номер любого прямоугольника P, примыкающего к I, в этот момент не меняется; более того, номера соседних прямоугольников, прилегающих к I с одной стороны, равны, а для прилегающих с разных сторон он отличается на 1. Итак, каждый прямоугольник P имеет один и тот же номер на всех вертикальных прямых, его содержащих. Аналогичные утверждения верны и для горизонтальных номеров.
Зафиксируем теперь число i и рассмотрим все прямоугольники P1, ..., Pt, имеющие вертикальный номер i (они занумерованы согласно абсциссам их левых границ слева направо). Будем двигать вертикальную прямую v от левой стороны квадрата к правой. В каждый момент (кроме тех, когда она содержит отрезок разбиения) v пересекает ровно один из прямоугольников Ps; значит, правая сторона очередного прямоугольника Ps лежит на той же прямой, что и левая сторона следующего прямоугольника Ps+1 (см. рис.). Тогда эти прямоугольники примыкают с разных сторон к одному и тому же вертикальному отрезку разбиения, поэтому горизонтальный номер прямоугольника Ps+1 на 1 больше, чем горизонтальный номер Ps. Ясно, наконец, что горизонтальные номера прямоугольников P1 и Px равны 1 и l; значит, t = l.
Итак, для каждого из k вертикальных номеров есть ровно l прямоугольников с таким номером; поэтому общее число прямоугольников равно kl.
Ответ
kl.
Замечания
Условия, наложенные на отрезки разбиения, существенны, как показывают примеры на следующем рисунке.
