II математическая олимпиада «Шелковый путь», 2003 год

Пусть $a_1, a_2, \ldots, a_{2003}$ является последовательностью действительных чисел. Элемент $a_k$, $1 \le k \le 2003$, назовем $\textit{ведущим}$ элементом, если хотя бы одно из выражений $a_k, a_k + a_{k+1}, \ldots, a_k + a_{k+1} + \ldots + a_{2003}$ является положительным. Докажите, сумма всех ведущих элементов последовательности является положительной, если последовательность имеет хотя бы один ведущий элемент.

Комментарий/решение

Это также возможно, без индукции.

Мы будем рассуждать следующим образом. Начните с первого главного термина, скажем, $a_{n_1}$. Если $a_{n_1}>0$; добавьте его к сумме и продолжайте искать второй такой член. Если нет, то пусть $\ell$ — наименьший индекс, для которого

$a_{n_1}+a_{n_1+1}+\cdots+a_{n_1+\ell}>0.$

Во втором случае $a_{n_1}$ является ведущим термином и равен нулю. Очевидно, $a_{n_1+\ell}>0$ (поскольку $\ell$ — наименьший из таких парней), следовательно, $a_{n_1+\ell}$ также является ведущим термом. Теперь среди цифр

$a_{n_1+1},a_{n_1+2},\cdots,a_{n_1+\ell},$

пусть $I$ будет индексом всех чисел, они отрицательны. У нас есть,

$\sum_{i\in \{n_1,n_1+1,\cdots,n_1+\ell\}\setminus I}a_i + \sum_{i\in I}a_i>0.$

Очевидно, что все индексы, содержащиеся в первом суммировании (а именно, $i\in\{n_1,n_1+1,\cdots,n_1+\ell\}\setminus I$), $a_i$ являются ведущими членами . Если существует подмножество $J\subseteq I$ такое, что $a_j$ является ведущим термином, для каждого $j\in J$ мы имеем:

$\sum_{i\in \{n_1,n_1+1,\cdots,n_1+\ell\}\setminus I}a_i + \sum_{j\in J}a_j>\sum_{i\in \{n_1,n_1+ 1,\cdots,n_1+\ell\}\setminus I}a_i + \sum_{i\in I}a_i>0,$

следовательно, сумма всех главных членов, начиная с $a_{n_1}$ и заканчивая $a_{n_1+\ell}$, положительна. Теперь найдите следующий ведущий термин (а именно, $a_k$, такой, что $k>n_1+\ell$, с ведущим $a_k$); и обратите внимание, что у нас есть второй блок ведущих членов, сумма которых положительна.

При таком подходе мы учитываем каждое ведущее слагаемое на последующих шагах на основе построенных выше блоков; и в каждый момент времени все суммы в подблоках положительны, что доказывает, что сумма всех ведущих членов положительна при условии, что ведущий термин существует.

Вы действительно сами решаете все эти задачи под которыми пишите решения или вы просто копируете решения с aops?

Здравствуйте BekzhanMoldabekov! Я написал отличное решение для этой задачи, вот оно:

grupyorum

1221 posts

#2VPMh Jan 22, 2018, 9:26 AM• 1 Y

This is also doable, without induction.

We will argue as follows. Start with the first leading term, say it is, $a_{n_1}$. If, $a_{n_1}>0$; add it to the sum, and, go on finding the second such term. If not, then, let, $\ell$ be the smallest index, for which,

$$

a_{n_1}+a_{n_1+1}+\cdots+a_{n_1+\ell}>0.

$$In this second case, $a_{n_1}$ is a leading term, and is zero. Clearly, $a_{n_1+\ell}>0$ (as, $\ell$ is the smallest such guy), hence, $a_{n_1+\ell}$ is also a leading term. Now, among the numbers,

$$

a_{n_1+1},a_{n_1+2},\cdots,a_{n_1+\ell},

$$let, $I$ be the index of all, those are negative. We have,

$$

\sum_{i\in \{n_1,n_1+1,\cdots,n_1+\ell\}\setminus I}a_i + \sum_{i\in I}a_i>0.

$$Clearly, all the indices, contained in the first summation (namely, $i\in\{n_1,n_1+1,\cdots,n_1+\ell\}\setminus I$), $a_i$'s are leading terms. If, there is a subset $J\subseteq I$, such that, $a_j$ is a leading term, for every $j\in J$, we have,

$$

\sum_{i\in \{n_1,n_1+1,\cdots,n_1+\ell\}\setminus I}a_i + \sum_{j\in J}a_j>\sum_{i\in \{n_1,n_1+1,\cdots,n_1+\ell\}\setminus I}a_i + \sum_{i\in I}a_i>0,

$$hence, the sum of all leading terms, starting from, $a_{n_1}$, to, $a_{n_1+\ell}$ are positive. Now, search for the next leading term (namely, $a_k$, such that, $k>n_1+\ell$, with, $a_k$ leading); and notice that, we have a second block of leading terms, whose sum is positive.

With this approach, we take each leading term, into account, at subsequent steps, based on the blocks, constructed above; and at each time, the sums in subblocks are all positive, proving that, the sum of all leading terms are positive, provided, a leading term exists.

Но к сожалению, я не знаю русского языка, не могли бы вы посоветовать сайты переводчики?

Bruuuhhh

История повторяется?

Bro has no chill, harosh ahahhwhshah

Докажем по индукции для любого набора $a_1,...,a_k$ в котором есть хотя бы один ведущий элемент.

База. $k=1$, если есть ведущий элемент, то он должен быть положительным, всё работает.

Переход. Теперь предположим что для любого набора из $i$ чисел в котором есть хотя бы $1$ ведущий элемент это работает. Возьмём наборчик $a_1,a_2,...,a_{i+1}$, докажем что для него тоже будет работать.

Давайте проигнорируем $a_1$, он такой бесполезный на самом то деле. Взглянем на набор $a_2,a_3,...,a_{i+1}$, ему вообще плевать на $a_1$, ни один элемент отсюда не берёт в сумму $a_1$, так что он никак не влияет на отбор ведущих элементов в этом наборе.

Если этот набор не имеет ведущих элементов, то единственный ведущий элемент это $a_1$, он положителен, задача решена. Теперь пусть он имеет ведущие элементы.

Есть два случая, либо $a_1$ так и останется бесполезным не ведущим элементом и мы можем просто использовать индукцию для того набора и задача решена. Либо, $a_1$ всё таки ведущий элемент, и какая то сумма $a_1+a_2+...+a_t$ оказалась положительной. Отсечём наборы $a_1,a_2,...,a_t$ (Набор 1) и $a_{t+1},...,a_{i+1}$ (Набор 2). Опять же, ведущим во втором наборе плевать на первый набор, они определяются сами по себе, оставим их.

Посмотрим на Набор 1, по сути $a_2+...+a_t>-a_1$. Давайте посмотрим на сумму ведущих в первом наборе (кроме $a_1$) и $a_2+...+a_t$. Любой ведущий есть в $a_2,...,a_t$ (любое пол. число = ведущий), а кроме ведущих останутся лишь отрицательные числа, то есть по сути $a_2+...+a_t$ это сумма ведущих $+$ оставшиеся отрицательные числа, то есть по факту сумма ведущих уже больше чем эта сумма, а значит больше чем $-a_1$. Значит сумма ведущих из первого набора положительна, как и сумма ведущих из второго, в сумме все ведущие дадут положительное число.

Гоу лайк мопсичеку