Олимпиадная задача Чеканова: Разрезание прямоугольника 1995×n на различные полоски

  Идея решения: возьмем максимальную полоску (равную максимальной стороне прямоугольника). Остальные полоски будем объединять в пары, дающие в сумме максимальную полоску. Если мы заполнили прямоугольник, то задача решена; в противном случае рассуждение с площадями показывает, что прямоугольник нельзя разрезать на различные полоски. Рассмотрим два случая: n$\le$1995 и n > 1995.

Случай n$\le$1995. Если n$\le$998, то разрежем прямоугольник на n полосок длиной 1995. Первую сохраним, вторую разрежем на две полоски длиной 1 и 1994, третью — на две полоски длиной 2 и 1993 и т. д. Последняя полоска

1×1995 будет разрезана на части 1×(n - 1) и 1×(1996 - n). У нас получились полоски с длинами:

1, 2,..., n - 1, 1996 - n,(1996 - n) + 1,..., 1994, 1995.

Ясно, что первыеn- 1 полосок различны, остальные полоски тоже различны. Однако, чтобы среди первыхn- 1 полосок не было полосок, равных одной из остальных полосок, необходимо (и достаточно), чтобыn- 1 < 1996 -n.

Это неравенство выполняется, потому что n$\le$998. Такое разрезание для прямоугольника 5×9 изображено на рис.

Покажем, что при 998 < n$\le$1995 разрезать прямоугольник требуемым образом не удастся. Действительно, самая длинная полоска, которая помещается в нашем прямоугольнике, — 1×1995. Значит, даже если мы используем все 1995 возможных полосок, их суммарная площадь будет

1 + 2 + 3 + ... + 1994 + 1995 = $\displaystyle {\frac{1995\cdot1996}{2}}$

(см. комментарий), а площадь прямоугольника равна 1995n. Значит, должно выполняться неравенство:

1995n$\displaystyle \le$$\displaystyle {\frac{1995\cdot1996}{2}}$,

но это означает, чтоn$\le$998. Случай n > 1995 аналогичен. Разрежем прямоугольник на 1995 полосок длиной n. Первую сохраним, вторую разрежем на две полоски длиной 1 и n - 1 и т. д. Получатся полоски с длинами

1, 2,..., 1994, n - 1994,(n - 1994) + 1,..., n.

Они будут различными, если1994 <n- 1994, т. е.n$\ge$3989. Чтобы доказать необходимость этого условия, снова сравним площади. Так как суммарная площадь полосок не превосходит${\frac{n(n+1)}{2}}$, получаем неравенство

1995n$\displaystyle \le$$\displaystyle {\frac{n(n+1)}{2}}$,

Отсюдаn$\ge$2 ^. 1995 - 1 = 3989. Комментарии. 1^o. Прямоугольник n×m c n$\ge$m можно разрезать на полоски различной длины тогда и только тогда, когда n$\ge$2m - 1.

2^o. Мы воспользовались формулой 1 + 2 + ... + n = ${\frac{n(n+1)}{2}}$. Эта формула может быть доказана по индукции. Кроме того, она является частным случаем формулы для суммы арифметической прогрессии. Тем не менее, приведем элегантное доказательство этой формулы. Обозначим 1 + 2 + ... + n = X и посчитаем сумму всех чисел в таблице:

Так как сумма в каждом столбце равна n + 1, а столбцов n, сумма всех чисел в таблице равна n(n + 1). С другой стороны, сумма в каждой из строк равна X, так что сумма всех чисел в таблице равна 2X. Итак, 2X = n(n + 1), откуда и следует наше утверждение.