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

Проект МЦНМО
при участии
школы 57
Задача 109667
Темы:    [ Геометрия на клетчатой бумаге ]
[ Числовые таблицы и их свойства ]
[ Исследование квадратного трехчлена ]
[ Подсчет двумя способами ]
[ Целочисленные и целозначные многочлены ]
[ Непрерывность и компактность ]
Сложность: 6
Классы: 10,11
В корзину
Прислать комментарий

Условие

Клетчатая фигура Ф обладает таким свойством: при любом заполнении клеток прямоугольника 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-мерном кубе. Непрерывная функция достигает своего наименьшего значения на кубе. Так как это многочлен второй степени с целыми коэффициенты, то координаты этой точки минимума – решение линейной системы уравнений с целыми коэффициентами, то есть рациональны.

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

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

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

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