Задача 109667

Темы:    [ Геометрия на клетчатой бумаге ] [ Числовые таблицы и их свойства ] [ Исследование квадратного трехчлена ] [ Подсчет двумя способами ] [ Целочисленные и целозначные многочлены ] [ Непрерывность и компактность ]

Сложность: 6 Классы: 10,11

Условие

Автор: Канель-Белов А.Я.

Клетчатая фигура Ф обладает таким свойством: при любом заполнении клеток прямоугольника m×n числами, сумма которых положительна, фигуру Ф можно так расположить в прямоугольнике, чтобы сумма чисел в клетках прямоугольника, накрытых фигурой Ф, была положительна (фигуру Ф можно поворачивать). Докажите, что данный прямоугольник может быть покрыт фигурой Ф в несколько слоев.

Решение

  Пусть Ф₁, ..., Ф_k – все возможные расположения фигуры Ф в прямоугольнике. Утверждение задачи можно переформулировать так: можно взять фигуры Ф_i такой неотрицательной толщины d_i  (i = 1, ..., k,  d_i рационально), что суммарная толщина всех фигур Ф_i над каждой клеткой прямоугольника будет равна 1.
  Предположим, что это утверждение неверно.
  Введём обозначения: индексом  j  (j = 1, ..., mn)  будем нумеровать клетки прямоугольника, индексом  i  (i = 1, ..., L)  – положения фигуры Ф на прямоугольнике. Положим  P_ij = 1,  если  j-я клетка закрыта фигурой Ф_i,  P_ij = 0,  если не закрыта. Тогда набору чисел {d_i} соответствует набор чисел     характеризующих уклонение покрытия прямоугольника фигурами от равномерного. По предположению  θ_j ≠ 0.
  Выберем числа  d_i ≥ 0  так, чтобы величина уклонения     была минимальна (ниже мы докажем, что такой набор существует).
  Заменим одно число d_i на  D_i = d_i + x,  x ≥ – d_i.  Тогда  η_j = θ_j – xP_ij, следовательно,  
то есть  η² = y(x) = ax² – 2b_ix + c.  Здесь     – число клеток в фигуре Ф,  c = θ².  По выбору набора {d_i} квадратный трехчлен y(x), заданный на множестве  x ≥ – d_i,  принимает наименьшее значение при  x = 0.  При  d_i > 0  это значит, что  b_i = 0,  а при
d_i = 0  – что  b_i ≤ 0.  Итак,     при любом i.
  Поставим число θ_j в  j-ю клетку прямоугольника. При этом сумма     чисел, закрываемых фигурой Ф_i, неположительна, а сумма     всех чисел в прямоугольнике положительна, так как она равна     Действительно,     так как  b_i = 0  при  d_i > 0.  Это противоречит условию.

  Докажем теперь, что величину θ можно минимизировать.
   
где  M_ik ≥ 0,  а a – число клеток в фигуре Ф. Отсюда следует, что, если  d_i > 2  для некоторого i, то  θ² ≥ a((d_i – 1)² – 1) + mn > mn,  в то время как  θ² = mn,  если все  d_i = 0.  Итак, достаточно рассмотреть функцию θ² на множестве  0 ≤ d₁, ..., d_mn ≤ 2,  то есть на mn-мерном кубе. Непрерывная функция достигает своего наименьшего значения на кубе. Так как это многочлен второй степени с целыми коэффициенты, то координаты этой точки минимума – решение линейной системы уравнений с целыми коэффициентами, то есть рациональны.

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

олимпиада
Название	Всероссийская олимпиада по математике
год
Год	1998
Этап
Вариант	5
Класс
Класс	11
задача
Номер	98.5.11.8