Разделы 
Дополнительно
Задача по математике - 2974
2019-05-06 
Сумма 1959 положительных чисел $a_1, a_2, a_3, \cdots, a_{1959}$ равна 1; доказать, что сумма всевозможных произведений по 1000 разных сомножителей из числа наших чисел меньше 1. [В число рассматриваемых произведений включаются все, отличающиеся друг от друга хоть одним сомножителем, но не произведения, отличающиеся только порядком сомножителей - такие произведения считаются одинаковыми и засчитывается из них лишь одно.]
Решение:
Ясно, что числа 1959 и 1000 в формулировке этой задачи являются случайными - факт, который нам требуется доказать, состоит в том, что если все $a_i > 0$ и $\sum a_{i} = a_1 + a_2 + \cdots + a_n = 1$, то сумма $S_{n,k} = \sum_{i_1, i_2, \cdots, i_k = 1}^{n} {a_{i_1}, a_{i_2}, \cdots, a_{i_k}}$ всевозможных произведений по $k$ из $n$ наших чисел (где $1 \leq k < n$) всегда $\leq 1$, причем, если $k > 1$, то эта сумма строго < 1. Доказать это можно, например, методом математической индукции по числам $n$ и $k$. Ясно, что при $n = 1$ и при $n = 2$ утверждение задачи справедливо; далее предположим его уже доказанным для всех $n$, меньших данного, а для этого $n$ - справедливым для всех $k$, меньших фиксированного $k \geq 2$ (при любом $n$ и $k = 1$ утверждение задачи тривиально).
Рассмотрим теперь сумму $S_{n,k} = \sum_{i_1, i_2, \cdots, i_k = 1}^{n} a_{i_1} a_{i_2} \cdots a_{i_k}$.
Выделяя в этой сумме все произведения, содержащие множитель $а^n$, получим:
$S_{n,k} = \sum_{i_1, i_2, \cdots, i_{k-1} = 1}^{n - 1} a_{i_1} a_{i_2} \cdots a_{i_{k-1}}a_n + \sum_{i_1, i_2, \cdots, i_{k-1} = 1}^{n-1}{a_{i_1} a_{i_2} \cdots a_{i_k}} = S_{n-1,k-q} \cdot a_{n} + S_{n - 1, k} $,
где $S_{n–1,k–1}$ и $S_{n–1, k}$, - суммы всевозможных произведений по $k - 1$ и $k$ сомножителей из чисел $a_1, a_2, \cdots, a_{k-1}$. Но сумма этих последних $n- 1$ чисел равна
$a_1 + a_2 + \cdots + a_{n-1} = (a_1 + a_2 + \cdots + a_{n-1} + a_n) - a_n = 1 - a_n$.
Заменим теперь числа $a_1, a_2, \cdots, a_{n-1}$ числами $a_1^{ \prime} = \frac {a_1}{1-a_n}, a_2^{ \prime} = \frac {a_2}{1-a_n}$, \cdots, $a_{n-1}^{ \prime} = \frac {a_{n-1}}{1 - a_n}$, сумма которых уже равна 1; суммы же всевозможных произведений по $k-1$ и по $k$ из этих новых $n-1$ чисел мы обозначим через $S_{n-1, k-1}^{ \prime}$, и через $S_{n-1, k}^{ \prime}$. По предположению индукции, $S_{n-1,k-1}^{ \prime} \leq 1$ и $S_{n-1,k}^{ \prime} \leq 1$; с другой стороны, в силу пропорциональности чисел $а_i^{ \prime}$ и $a_i$ (где $i = 1, \cdots, n - 1$), очевидно, имеем:
$S_{n-1,k-1} = S_{n-1,k-1}^{ \prime} \cdot (1 - a_n)^{k-1} \leq (1 - a_n)^{k-1}$ и $S_{n-1,k} = S_{n-1,k}^{ \prime} \cdot (1 - a_n)^k \leq (1 - a_n)^k$.
Теперь окончательно получаем:
$S_{n,k} = S_{n-1,k-1} \cdot a_{n} + S_{n- 1, k} < (1 - a_n)^{k-1} a_{n} + (1 - a_{n} )^{k} = (1 - a_{n} )^{ k - 1} [a_{n} + (1 - a_{n} )] = (1 - a_{n} )^{ k - 1} < 1$,
- что и требовалось доказать.
Сумма 1959 положительных чисел $a_1, a_2, a_3, \cdots, a_{1959}$ равна 1; доказать, что сумма всевозможных произведений по 1000 разных сомножителей из числа наших чисел меньше 1. [В число рассматриваемых произведений включаются все, отличающиеся друг от друга хоть одним сомножителем, но не произведения, отличающиеся только порядком сомножителей - такие произведения считаются одинаковыми и засчитывается из них лишь одно.]
Решение:
Ясно, что числа 1959 и 1000 в формулировке этой задачи являются случайными - факт, который нам требуется доказать, состоит в том, что если все $a_i > 0$ и $\sum a_{i} = a_1 + a_2 + \cdots + a_n = 1$, то сумма $S_{n,k} = \sum_{i_1, i_2, \cdots, i_k = 1}^{n} {a_{i_1}, a_{i_2}, \cdots, a_{i_k}}$ всевозможных произведений по $k$ из $n$ наших чисел (где $1 \leq k < n$) всегда $\leq 1$, причем, если $k > 1$, то эта сумма строго < 1. Доказать это можно, например, методом математической индукции по числам $n$ и $k$. Ясно, что при $n = 1$ и при $n = 2$ утверждение задачи справедливо; далее предположим его уже доказанным для всех $n$, меньших данного, а для этого $n$ - справедливым для всех $k$, меньших фиксированного $k \geq 2$ (при любом $n$ и $k = 1$ утверждение задачи тривиально).
Рассмотрим теперь сумму $S_{n,k} = \sum_{i_1, i_2, \cdots, i_k = 1}^{n} a_{i_1} a_{i_2} \cdots a_{i_k}$.
Выделяя в этой сумме все произведения, содержащие множитель $а^n$, получим:
$S_{n,k} = \sum_{i_1, i_2, \cdots, i_{k-1} = 1}^{n - 1} a_{i_1} a_{i_2} \cdots a_{i_{k-1}}a_n + \sum_{i_1, i_2, \cdots, i_{k-1} = 1}^{n-1}{a_{i_1} a_{i_2} \cdots a_{i_k}} = S_{n-1,k-q} \cdot a_{n} + S_{n - 1, k} $,
где $S_{n–1,k–1}$ и $S_{n–1, k}$, - суммы всевозможных произведений по $k - 1$ и $k$ сомножителей из чисел $a_1, a_2, \cdots, a_{k-1}$. Но сумма этих последних $n- 1$ чисел равна
$a_1 + a_2 + \cdots + a_{n-1} = (a_1 + a_2 + \cdots + a_{n-1} + a_n) - a_n = 1 - a_n$.
Заменим теперь числа $a_1, a_2, \cdots, a_{n-1}$ числами $a_1^{ \prime} = \frac {a_1}{1-a_n}, a_2^{ \prime} = \frac {a_2}{1-a_n}$, \cdots, $a_{n-1}^{ \prime} = \frac {a_{n-1}}{1 - a_n}$, сумма которых уже равна 1; суммы же всевозможных произведений по $k-1$ и по $k$ из этих новых $n-1$ чисел мы обозначим через $S_{n-1, k-1}^{ \prime}$, и через $S_{n-1, k}^{ \prime}$. По предположению индукции, $S_{n-1,k-1}^{ \prime} \leq 1$ и $S_{n-1,k}^{ \prime} \leq 1$; с другой стороны, в силу пропорциональности чисел $а_i^{ \prime}$ и $a_i$ (где $i = 1, \cdots, n - 1$), очевидно, имеем:
$S_{n-1,k-1} = S_{n-1,k-1}^{ \prime} \cdot (1 - a_n)^{k-1} \leq (1 - a_n)^{k-1}$ и $S_{n-1,k} = S_{n-1,k}^{ \prime} \cdot (1 - a_n)^k \leq (1 - a_n)^k$.
Теперь окончательно получаем:
$S_{n,k} = S_{n-1,k-1} \cdot a_{n} + S_{n- 1, k} < (1 - a_n)^{k-1} a_{n} + (1 - a_{n} )^{k} = (1 - a_{n} )^{ k - 1} [a_{n} + (1 - a_{n} )] = (1 - a_{n} )^{ k - 1} < 1$,
- что и требовалось доказать.
