Разделы 
Дополнительно
Задача по математике - 1900
2019-01-21 
Клетчатая фигура $Ф$ обладает свойством: при любом заполнении клеток прямоугольника $m \times n$ числами, сумма которых положительна, фигуру $Ф$ можно так расположить в прямоугольнике, чтобы сумма чисел в клетках прямоугольника, накрытых фигурой $Ф$ была положительна (фигуру $Ф$ можно поворачивать). Докажите, что данный прямоугольник может быть покрыт фигурой $Ф$ в несколько слоев.
Решение:
Пусть $Ф_1, \cdots , Ф_k$ - все возможные расположения фигуры $Ф$ в прямоугольнике. Утверждение задачи можно переформулировать так: можно взять фигуры $Ф_i$ такой неотрицательной толщины $d_i, i = 1, \cdots, k (d_i$ рационально), что суммарная толщина всех фигур $Ф_i$ над каждой клеткой прямоугольника будет равна $1$.
Предположим, что это утверждение неверно. Покажем, что тогда существует такое заполнение клеток прямоугольника числами, при котором сумма всех чисел положительна, а сумма чисел в клетках, закрываемых фигурой при любом ее положении, неположительна.
Введем обозначения: индексом $j, j = 1, \cdots , m \cdot n$, будем нумеровать клетки прямоугольника, индексом $i, i = 1, \cdots , k$, - положения фигуры $Ф$ на прямоугольнике.
Положим $P_{ij} = 1$, если $j$-я клетка закрыта фигурой $Ф_i, P_{ij} = 0$, если не закрыта. Тогда набору чисел $\{ d_i \}$ соответствует заполнение клеток прямоугольника числами $\Theta_j = 1 - \sum_{i}^{ }d_iP_{ij}$, характеризующими уклонение покрытия прямоугольника фигурами от равномерного. По нашему предположению, все числа $\Theta_j$ не могут быть равными нулю.
Выберем числа $d_j \geq 0$ так, чтобы величина $|\Theta|$ уклонения была минимальна, где $|\Theta|^2 = \sum_{j}^{ }\Theta_j^2$. Покажем, что получившиеся числа$\Theta_j$ и образуют искомое заполнение клеток прямоугольника.
Заменим одно число $d_i$ на $d_i^{\prime} = d_i + x, x \geq -d_i$. Тогда $\Theta_j^{\prime} = \Theta_j - xP_{ij}$, следовательно $|\Theta^{\prime}|^2 = \sum_{j}{ }\Theta_j^2 - 2x \sum_{j}{ }\Theta_jP_{ij} + x^2 \sum_{j}{ }P_ij^2$, т.е. $|\Theta^{\prime}|^2 = y(x) = ax^2 - 2b_ix + c$. Здесь $a = \sum_{j}{ }P_{ij}^2 = \sum_{j}{ }P_{ij} = N$, где $N$ - число клеток в фигуре, $с = |\Theta|^2$. Квадратный трехчлен $y = y(x)$, заданный на множестве $x \geq -d_i$, принимает наименьшее значение при $x = 0$ в случае $b_i = 0$, если $d_i > 0$, и в случае $b_i \leq 0$, если $d_i = 0$. Таким образом, предположив, что $|\Theta|$ минимален на наборе {$d_i$}, мы получаем, что если $d_i > 0$, то $b_i = \sum_{j}{ }\Theta P_{ij} = 0$, а если $d_i = 0$, то $b_i \leq 0$. Значит, сумма чисел, закрываемых фигурой $Ф_i$ (это как раз $\sum_{j}{ }\Theta_jP_{ij}$) - неположительна; с другой стороны, сумма всех чисел в прямоугольнике положительна, так как она равна $\sum_{j}{ }\Theta_j$, а $\sum_{j}{ }\Theta_j = \sum_{j}{ }\Theta_j^2$. Действительно, $\sum_{j}{ }\Theta_j^2 = \sum_{j}{ }\Theta_j (1 - \sum_{i}{ } d_iP_{ij}) = \sum_{j}{ }\Theta_j - \sum_{i}{ }d_i(\Theta_jP_{ij})) = \sum_{j}{ }\Theta_j - \sum_{i, d_i > 0}\sum_{j}{ }\Theta_jP_{ij} = \sum_{j}{ }\Theta_j$, так как при $d_i > 0 b_i = 0$.
Клетчатая фигура $Ф$ обладает свойством: при любом заполнении клеток прямоугольника $m \times n$ числами, сумма которых положительна, фигуру $Ф$ можно так расположить в прямоугольнике, чтобы сумма чисел в клетках прямоугольника, накрытых фигурой $Ф$ была положительна (фигуру $Ф$ можно поворачивать). Докажите, что данный прямоугольник может быть покрыт фигурой $Ф$ в несколько слоев.
Решение:
Пусть $Ф_1, \cdots , Ф_k$ - все возможные расположения фигуры $Ф$ в прямоугольнике. Утверждение задачи можно переформулировать так: можно взять фигуры $Ф_i$ такой неотрицательной толщины $d_i, i = 1, \cdots, k (d_i$ рационально), что суммарная толщина всех фигур $Ф_i$ над каждой клеткой прямоугольника будет равна $1$.
Предположим, что это утверждение неверно. Покажем, что тогда существует такое заполнение клеток прямоугольника числами, при котором сумма всех чисел положительна, а сумма чисел в клетках, закрываемых фигурой при любом ее положении, неположительна.
Введем обозначения: индексом $j, j = 1, \cdots , m \cdot n$, будем нумеровать клетки прямоугольника, индексом $i, i = 1, \cdots , k$, - положения фигуры $Ф$ на прямоугольнике.
Положим $P_{ij} = 1$, если $j$-я клетка закрыта фигурой $Ф_i, P_{ij} = 0$, если не закрыта. Тогда набору чисел $\{ d_i \}$ соответствует заполнение клеток прямоугольника числами $\Theta_j = 1 - \sum_{i}^{ }d_iP_{ij}$, характеризующими уклонение покрытия прямоугольника фигурами от равномерного. По нашему предположению, все числа $\Theta_j$ не могут быть равными нулю.
Выберем числа $d_j \geq 0$ так, чтобы величина $|\Theta|$ уклонения была минимальна, где $|\Theta|^2 = \sum_{j}^{ }\Theta_j^2$. Покажем, что получившиеся числа$\Theta_j$ и образуют искомое заполнение клеток прямоугольника.
Заменим одно число $d_i$ на $d_i^{\prime} = d_i + x, x \geq -d_i$. Тогда $\Theta_j^{\prime} = \Theta_j - xP_{ij}$, следовательно $|\Theta^{\prime}|^2 = \sum_{j}{ }\Theta_j^2 - 2x \sum_{j}{ }\Theta_jP_{ij} + x^2 \sum_{j}{ }P_ij^2$, т.е. $|\Theta^{\prime}|^2 = y(x) = ax^2 - 2b_ix + c$. Здесь $a = \sum_{j}{ }P_{ij}^2 = \sum_{j}{ }P_{ij} = N$, где $N$ - число клеток в фигуре, $с = |\Theta|^2$. Квадратный трехчлен $y = y(x)$, заданный на множестве $x \geq -d_i$, принимает наименьшее значение при $x = 0$ в случае $b_i = 0$, если $d_i > 0$, и в случае $b_i \leq 0$, если $d_i = 0$. Таким образом, предположив, что $|\Theta|$ минимален на наборе {$d_i$}, мы получаем, что если $d_i > 0$, то $b_i = \sum_{j}{ }\Theta P_{ij} = 0$, а если $d_i = 0$, то $b_i \leq 0$. Значит, сумма чисел, закрываемых фигурой $Ф_i$ (это как раз $\sum_{j}{ }\Theta_jP_{ij}$) - неположительна; с другой стороны, сумма всех чисел в прямоугольнике положительна, так как она равна $\sum_{j}{ }\Theta_j$, а $\sum_{j}{ }\Theta_j = \sum_{j}{ }\Theta_j^2$. Действительно, $\sum_{j}{ }\Theta_j^2 = \sum_{j}{ }\Theta_j (1 - \sum_{i}{ } d_iP_{ij}) = \sum_{j}{ }\Theta_j - \sum_{i}{ }d_i(\Theta_jP_{ij})) = \sum_{j}{ }\Theta_j - \sum_{i, d_i > 0}\sum_{j}{ }\Theta_jP_{ij} = \sum_{j}{ }\Theta_j$, так как при $d_i > 0 b_i = 0$.
