Разделы 
Дополнительно
Задача по математике - 3549
2019-06-12 
Даны положительные числа $a_1, a_2, \cdots, a_n, b_1 b_2, \cdots, b_n$, причем $a_1 + a_2 + \cdots + a_m = b_1 + b_2 + \cdots + b_n$. Докажите, что в пустую таблицу из $m$ строк и $n$ столбцов можно поставить не более чем $m + n - 1$ положительное число так, чтобы сумма чисел в $i$-й строке равнялась $a_i$ сумма чисел в $k$-м столбце равнялась $b_k$.
Решение:
Рассмотрим таблицу $m \times n$ и будем рассуждать по индукции, считая, что для таблиц с меньшей суммой $m + n$ утверждение уже доказано. Для таблицы $1 \times 1$ оно очевидно. Выберем наименьшее из $m + n$ данных чисел $a_1, a_2, \cdots, a_m, b_1 - a_1, b_2, \cdots, b_n$ - пусть это будет $a_1$. Поставим $a_1$ в левый верхний угол, а затем первую строку отрежем; останется решить задачу для таблицы $(m - 1) \times n$ и набора чисел $a_2, \cdots, a_m, b_1 - a_1, b_2, \cdots, b_m$, а это по предположению индукции мы делать умеем.
Другое, типично «олимпиадное» решение. Нарисуем отрезок длины $d = a_1 + a_2 + \cdots + a_m = b_1 + b_2 + \cdots + b_n$ и разобьем его двумя способами: на $m$ «красных» отрезков длины $b_1, b_2, \cdots, b_n$ и $n$ «синих» отрезков длины $b_1, b_2, \cdots, b_n$. Всего будет $(n-1) + (m - 1)$ точек разбиения и соответственно $m + n - 1$ маленьких отрезков. Остается записать длину каждого из этих отрезков (пересечения некоторого красного $a_i$ и некоторого синего $b_j$) в соответствующую клетку таблицы (стоящую на пересечении $i$-й строки и $j$-го столбца).
Даны положительные числа $a_1, a_2, \cdots, a_n, b_1 b_2, \cdots, b_n$, причем $a_1 + a_2 + \cdots + a_m = b_1 + b_2 + \cdots + b_n$. Докажите, что в пустую таблицу из $m$ строк и $n$ столбцов можно поставить не более чем $m + n - 1$ положительное число так, чтобы сумма чисел в $i$-й строке равнялась $a_i$ сумма чисел в $k$-м столбце равнялась $b_k$.
Решение:
Рассмотрим таблицу $m \times n$ и будем рассуждать по индукции, считая, что для таблиц с меньшей суммой $m + n$ утверждение уже доказано. Для таблицы $1 \times 1$ оно очевидно. Выберем наименьшее из $m + n$ данных чисел $a_1, a_2, \cdots, a_m, b_1 - a_1, b_2, \cdots, b_n$ - пусть это будет $a_1$. Поставим $a_1$ в левый верхний угол, а затем первую строку отрежем; останется решить задачу для таблицы $(m - 1) \times n$ и набора чисел $a_2, \cdots, a_m, b_1 - a_1, b_2, \cdots, b_m$, а это по предположению индукции мы делать умеем.
Другое, типично «олимпиадное» решение. Нарисуем отрезок длины $d = a_1 + a_2 + \cdots + a_m = b_1 + b_2 + \cdots + b_n$ и разобьем его двумя способами: на $m$ «красных» отрезков длины $b_1, b_2, \cdots, b_n$ и $n$ «синих» отрезков длины $b_1, b_2, \cdots, b_n$. Всего будет $(n-1) + (m - 1)$ точек разбиения и соответственно $m + n - 1$ маленьких отрезков. Остается записать длину каждого из этих отрезков (пересечения некоторого красного $a_i$ и некоторого синего $b_j$) в соответствующую клетку таблицы (стоящую на пересечении $i$-й строки и $j$-го столбца).
