Информация о задаче

Задача 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.

Комментарии. 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 и посчитаем сумму всех чисел в таблице:

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