ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 107780
Темы:    [ Геометрия на клетчатой бумаге ]
[ Разрезания на части, обладающие специальными свойствами ]
[ Арифметическая прогрессия ]
Сложность: 4
Классы: 7,8,9
В корзину
Прислать комментарий

Условие

Прямоугольник размером 1×k при всяком натуральном k будем называть полоской. При каких натуральных n прямоугольник размером 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.

\epsfbox{1995/ol95093-1.mps}

Это неравенство выполняется, потому что 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.

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

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

1 2 3 ... n - 2 n - 1 n
n n - 1 n - 2 ... 3 2 1

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

Источники и прецеденты использования

олимпиада
Название Московская математическая олимпиада
год
Номер 58
Год 1995
вариант
Класс 9
задача
Номер 3

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .