Разделы 
Дополнительно
Задача по математике - 3740
2019-06-16 
а) Даны вещественные числа $a_1, a_2, a_3, b_2$ и положительные числа $p_1, p_2, q_1, q_2$. Докажите, что в следующей таблице $2 \times 2$
$\binom {\frac {a_1 + b_1}{p_1 + a_1} \frac {a_1 + b_2}{p_1 + q_2}}{\frac {a_2 + b_1}{p_2 + q_1} \frac {a_2 + b_2}{p_2 + q_2}}$
найдется число, которое не меньше числа, стоящего с ним в одной строке, и не больше числа, стоящего с ним в одном столбце.
б) Даны вещественные числа $a_1, a_2, \cdots, a_m, b_1, b_2, \cdots, b_n$ и положительные числа $p_1, p_2, \cdots, p_m, q_1, q_2, \cdots, q_n$. Составлена таблица $m \times n$, в которой на пересечении $i$-й строки ($i = 1, 2, \cdots, m$) и $j$-го столбца ($j = 1,2, \cdots, n$), стоит число
$\frac {a_i + b_j}{p_i + q_j}$.
Докажите, что в этой таблице найдется число, которое не меньше любого числа, стоящего с ним в одной строке, и не больше любого числа, стоящего с ним в одном столбце.
Решение:
а) Отметим два наибольших числа из четырех, составляющих таблицу $2 \times 2$. Если они стоят в одном столбце, то искомым числом является меньшее из них, а если они стоят в одной строке, то - большее из других двух чисел (при этом допускаются и нестрогие неравенства).
Остается случай, когда два отмеченных числа стоят по диагонали (и строго больше двух других), но этот случай невозможен. Проще всего убедиться в этом, опираясь на тот факт, что дробь $\frac{c + d}{p + q}$ всегда лежит между $\frac{c}{p}$ и $\frac{d}{q}$ (при $p > 0, q > 0$; рис. дает этому факту геометрическую интерпретацию). Из него следует, что $\frac {a_1 + b_1 + a_2 + b_2}{p_1 + q_1 + p_2 + q_2}$ лежит между $\frac {a_1 + b_1}{p_1 + q_1}$ и $\frac {a_2 + b_2}{p_2 + q_2}$, а также между $\frac {a_1 + b_2}{p_1 + q_2}$ и $\frac {a_2 + b_1}{p_2 + q_1}$, поэтому два наибольшие и два наименьшие числа в нашей таблице не могут стоять по диагоналям.
б) Дадим два решения этой задачи, одно - независимое от а) и, тем самым, дающее новое решение этого частного случая, а другое - использующее а) как лемму.
Первое решение. Мы должны указать такое число $x^{*} = \frac {a_k + b_l}{p_k + q_l}$ в нашей таблице $m \times n$ что выполнены условия
$\frac {a_k + b_j}{p_k + q_j} \leq x^{*}$ (для всех $j$), $\frac {a_i + b_l}{p_i + q_l} \geq x^{*}$ (для всех $i$); перепишем эти условия так:
$p_k x^{*} - a_k \geq - q_j x^{*} + b_j, p_i x^{*} - a_i \leq -q_l x^{*} + b_l$. (*)
Рассмотрим кусочно-линейные функции $f(x) = max_{1 \leq i \leq m} (p_i x - a_i)$ и $g(x) = max_{1 \leq i \leq n} (-q_i x + b_j)$, график каждой функции состоит из отрезков прямых и двух лучей. Первая - монотонно возрастает, вторая - убывает, и потому уравнение $f(x)= g(x)$ имеет единственное решение $(x^{*},y^{*})$ (точка $(x^{*},y^{*})$, где $y^{*} = f(x^{*}) = g(x^{*})$ - самая высокая из точек пересечения прямых $y = p_i x - a_i$ с прямыми $y = -q_j x + b_j$, рис.). Примем за $k$ и $l$ номера тех линейных функций $у = p_ kx - a_k$ и $у = -q_i x + b_i$, пересечение графиков которых дает точку $(х^{*},у^{*})$, то есть тех, для которых $p_k x^{*} - a_k = max_{1 \leq i \leq m} (p_i x^{*} - a_i) = y^{*} = - q_l x^{*} + b_l = max_{1 \leq i \leq n} (-q_j x^{*} + b_j)$. Для .указанных $k, l$ и $x^{*}$, выполнены все нужные условия (*).
Второе решение основано на таком замечательном наблюдении. Будем говорить, что таблица имеет «седло», если у нее есть элемент, который не меньше всех в своей строке и не больше всех в своем столбце.
Лемма. Если каждая таблица $2 \times 2$, полученная из данной таблицы $m \times n$ вычеркиванием $m - 2$ строк и $n - 2$ столбцов, имеет седло, то этим свойством обладает и вся таблица $m \times n$.
Эта лемма сводит задачу б) к частному случаю а).
Докажем лемму. Предположим, что существует таблица, у которой нет седла, но любая подтаблица $2 \times 2$ имеет седло. Отметим в 1-й строке этой таблицы некоторое наибольшее число $M_i$, а в $j$-м столбце - наименьшее $m_j$. Построим из отмеченных чисел цепочку, переходя от некоторого наибольшего числа в строке к наименьшему в его столбце, а от него - к наибольшему в его строке, и т. д. Такая цепочка не может окончиться на каком-то одном элементе (так как таблица не имеет седла), поэтому она должна содержать цикл; заменив номера, т. е. переставив строки и столбцы надлежащим образом, мы можем считать, что этот цикл состоит из элементов $M_1 = x_{11}, m_1 = x_{21}, M_2 = x_{22}, m_2 = x_{32}, \cdots, m_r = x_{r r-1}, M_r = x_{rr}, m_r = x_1$ (рис.), причем $M_1 = min_{1 \leq i \leq r} M_i$. Поскольку таблица $2 \times 2$ в левом верхнем углу имеет седло, причем $m_1 < M_1 \leq M_2, m_1 < M_2$ и $x_{12} \leq M_1$, должно быть $M_1 = x_{12} \leq M_2$. Аналогично можно показать (рассматривая таблицы $2 \times 2$ с нижними строчками $(m_2, M_3), (m_3, M_4), \cdots)$, что все элементы первой строки равны $M_1: x_{11} = x_{12} = x_{13} = \cdots = x_{1r} = M_1$. Тогда $x_{1r} = m_r$ - седловая точка. Получили противоречие.
а) Даны вещественные числа $a_1, a_2, a_3, b_2$ и положительные числа $p_1, p_2, q_1, q_2$. Докажите, что в следующей таблице $2 \times 2$
$\binom {\frac {a_1 + b_1}{p_1 + a_1} \frac {a_1 + b_2}{p_1 + q_2}}{\frac {a_2 + b_1}{p_2 + q_1} \frac {a_2 + b_2}{p_2 + q_2}}$
найдется число, которое не меньше числа, стоящего с ним в одной строке, и не больше числа, стоящего с ним в одном столбце.
б) Даны вещественные числа $a_1, a_2, \cdots, a_m, b_1, b_2, \cdots, b_n$ и положительные числа $p_1, p_2, \cdots, p_m, q_1, q_2, \cdots, q_n$. Составлена таблица $m \times n$, в которой на пересечении $i$-й строки ($i = 1, 2, \cdots, m$) и $j$-го столбца ($j = 1,2, \cdots, n$), стоит число
$\frac {a_i + b_j}{p_i + q_j}$.
Докажите, что в этой таблице найдется число, которое не меньше любого числа, стоящего с ним в одной строке, и не больше любого числа, стоящего с ним в одном столбце.
Решение:
а) Отметим два наибольших числа из четырех, составляющих таблицу $2 \times 2$. Если они стоят в одном столбце, то искомым числом является меньшее из них, а если они стоят в одной строке, то - большее из других двух чисел (при этом допускаются и нестрогие неравенства).
Остается случай, когда два отмеченных числа стоят по диагонали (и строго больше двух других), но этот случай невозможен. Проще всего убедиться в этом, опираясь на тот факт, что дробь $\frac{c + d}{p + q}$ всегда лежит между $\frac{c}{p}$ и $\frac{d}{q}$ (при $p > 0, q > 0$; рис. дает этому факту геометрическую интерпретацию). Из него следует, что $\frac {a_1 + b_1 + a_2 + b_2}{p_1 + q_1 + p_2 + q_2}$ лежит между $\frac {a_1 + b_1}{p_1 + q_1}$ и $\frac {a_2 + b_2}{p_2 + q_2}$, а также между $\frac {a_1 + b_2}{p_1 + q_2}$ и $\frac {a_2 + b_1}{p_2 + q_1}$, поэтому два наибольшие и два наименьшие числа в нашей таблице не могут стоять по диагоналям.
б) Дадим два решения этой задачи, одно - независимое от а) и, тем самым, дающее новое решение этого частного случая, а другое - использующее а) как лемму.
Первое решение. Мы должны указать такое число $x^{*} = \frac {a_k + b_l}{p_k + q_l}$ в нашей таблице $m \times n$ что выполнены условия
$\frac {a_k + b_j}{p_k + q_j} \leq x^{*}$ (для всех $j$), $\frac {a_i + b_l}{p_i + q_l} \geq x^{*}$ (для всех $i$); перепишем эти условия так:
$p_k x^{*} - a_k \geq - q_j x^{*} + b_j, p_i x^{*} - a_i \leq -q_l x^{*} + b_l$. (*)
Рассмотрим кусочно-линейные функции $f(x) = max_{1 \leq i \leq m} (p_i x - a_i)$ и $g(x) = max_{1 \leq i \leq n} (-q_i x + b_j)$, график каждой функции состоит из отрезков прямых и двух лучей. Первая - монотонно возрастает, вторая - убывает, и потому уравнение $f(x)= g(x)$ имеет единственное решение $(x^{*},y^{*})$ (точка $(x^{*},y^{*})$, где $y^{*} = f(x^{*}) = g(x^{*})$ - самая высокая из точек пересечения прямых $y = p_i x - a_i$ с прямыми $y = -q_j x + b_j$, рис.). Примем за $k$ и $l$ номера тех линейных функций $у = p_ kx - a_k$ и $у = -q_i x + b_i$, пересечение графиков которых дает точку $(х^{*},у^{*})$, то есть тех, для которых $p_k x^{*} - a_k = max_{1 \leq i \leq m} (p_i x^{*} - a_i) = y^{*} = - q_l x^{*} + b_l = max_{1 \leq i \leq n} (-q_j x^{*} + b_j)$. Для .указанных $k, l$ и $x^{*}$, выполнены все нужные условия (*).
Второе решение основано на таком замечательном наблюдении. Будем говорить, что таблица имеет «седло», если у нее есть элемент, который не меньше всех в своей строке и не больше всех в своем столбце.
Лемма. Если каждая таблица $2 \times 2$, полученная из данной таблицы $m \times n$ вычеркиванием $m - 2$ строк и $n - 2$ столбцов, имеет седло, то этим свойством обладает и вся таблица $m \times n$.
Эта лемма сводит задачу б) к частному случаю а).
Докажем лемму. Предположим, что существует таблица, у которой нет седла, но любая подтаблица $2 \times 2$ имеет седло. Отметим в 1-й строке этой таблицы некоторое наибольшее число $M_i$, а в $j$-м столбце - наименьшее $m_j$. Построим из отмеченных чисел цепочку, переходя от некоторого наибольшего числа в строке к наименьшему в его столбце, а от него - к наибольшему в его строке, и т. д. Такая цепочка не может окончиться на каком-то одном элементе (так как таблица не имеет седла), поэтому она должна содержать цикл; заменив номера, т. е. переставив строки и столбцы надлежащим образом, мы можем считать, что этот цикл состоит из элементов $M_1 = x_{11}, m_1 = x_{21}, M_2 = x_{22}, m_2 = x_{32}, \cdots, m_r = x_{r r-1}, M_r = x_{rr}, m_r = x_1$ (рис.), причем $M_1 = min_{1 \leq i \leq r} M_i$. Поскольку таблица $2 \times 2$ в левом верхнем углу имеет седло, причем $m_1 < M_1 \leq M_2, m_1 < M_2$ и $x_{12} \leq M_1$, должно быть $M_1 = x_{12} \leq M_2$. Аналогично можно показать (рассматривая таблицы $2 \times 2$ с нижними строчками $(m_2, M_3), (m_3, M_4), \cdots)$, что все элементы первой строки равны $M_1: x_{11} = x_{12} = x_{13} = \cdots = x_{1r} = M_1$. Тогда $x_{1r} = m_r$ - седловая точка. Получили противоречие.
