|
|
 |
Условие
Клетчатая фигура Ф обладает таким свойством: при любом заполнении клеток прямоугольника 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. Это противоречит условию.
Докажем теперь, что величину θ можно минимизировать.
где Mik ≥ 0, а a – число клеток в фигуре Ф. Отсюда следует, что, если di > 2 для некоторого i, то θ² ≥ a((di – 1)² – 1) + mn > mn, в то время как θ² = mn, если все di = 0. Итак, достаточно рассмотреть функцию θ² на множестве 0 ≤ d1, ..., dmn ≤ 2, то есть на mn-мерном кубе. Непрерывная функция достигает своего наименьшего значения на кубе. Так как это многочлен второй степени с целыми коэффициенты, то координаты этой точки минимума – решение линейной системы уравнений с целыми коэффициентами, то есть рациональны.
