ЗАДАЧИ
problems.ru |
О проекте
|
Об авторах
|
Справочник
Каталог по темам | по источникам | |
|
Задача 109667
УсловиеКлетчатая фигура Ф обладает таким свойством: при любом заполнении клеток прямоугольника m×n числами, сумма которых положительна, фигуру Ф можно так расположить в прямоугольнике, чтобы сумма чисел в клетках прямоугольника, накрытых фигурой Ф, была положительна (фигуру Ф можно поворачивать). Докажите, что данный прямоугольник может быть покрыт фигурой Ф в несколько слоев. РешениеПусть Ф1, ..., Фk – все возможные расположения фигуры Ф в прямоугольнике. Утверждение задачи можно переформулировать так: можно взять фигуры Фi такой неотрицательной толщины di (i = 1, ..., k, di рационально), что суммарная толщина всех фигур Фi над каждой клеткой прямоугольника будет равна 1.Предположим, что это утверждение неверно. Введём обозначения: индексом j (j = 1, ..., mn) будем нумеровать клетки прямоугольника, индексом i (i = 1, ..., L) – положения фигуры Ф на прямоугольнике. Положим Pij = 1, если j-я клетка закрыта фигурой Фi, Pij = 0, если не закрыта. Тогда набору чисел {di} соответствует набор чисел характеризующих уклонение покрытия прямоугольника фигурами от равномерного. По предположению θj ≠ 0. Выберем числа di ≥ 0 так, чтобы величина уклонения была минимальна (ниже мы докажем, что такой набор существует). Заменим одно число di на Di = di + x, x ≥ – di. Тогда ηj = θj – xPij, следовательно, то есть η² = y(x) = ax² – 2bix + c. Здесь – число клеток в фигуре Ф, c = θ². По выбору набора {di} квадратный трехчлен y(x), заданный на множестве x ≥ – di, принимает наименьшее значение при x = 0. При di > 0 это значит, что bi = 0, а при di = 0 – что bi ≤ 0. Итак, при любом i. Поставим число θj в j-ю клетку прямоугольника. При этом сумма чисел, закрываемых фигурой Фi, неположительна, а сумма всех чисел в прямоугольнике положительна, так как она равна Действительно, так как bi = 0 при di > 0. Это противоречит условию. Докажем теперь, что величину θ можно минимизировать. Источники и прецеденты использования |
© 2004-...
МЦНМО
(о копирайте)
|
Пишите нам
|