3-ші «Жібек жолы» математикалық олимпиадасы, 2003 жыл


Егер $1 \leq k \leq 2003$ үшін $a_k$, $a_k + a_{k+1}$, $\ldots$, $a_k + a_{k+1} + \ldots + a_{2003}$ қосындыларының ең болмағанда біреуі оң болса, онда берілген $a_1, a_2, \ldots, a_{2003}$ нақты сандар тізбегінің $a_k$ элементін бастаушы деп атаймыз. Егер тізбектің ең болмағанда бір бастаушы элементі табылса, онда оның барлық бастаушы элементтерінің қосындысы оң болатынын дәлелдеңіздер.
посмотреть в олимпиаде

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

  4
2023-12-10 16:26:10.0 #

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

Мы будем рассуждать следующим образом. Начните с первого главного термина, скажем, $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$); и обратите внимание, что у нас есть второй блок ведущих членов, сумма которых положительна.

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

  0
2023-12-11 01:00:36.0 #

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

пред. Правка 2   2
2023-12-11 03:53:22.0 #

Здравствуйте 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.

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

  0
2023-12-11 20:48:11.0 #

Bruuuhhh

  0
2023-12-11 20:53:54.0 #

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

  1
2023-12-11 23:43:02.0 #

Bro has no chill, harosh ahahhwhshah

пред. Правка 2   1
2023-12-11 04:29:35.0 #

Докажем по индукции для любого набора $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$. Значит сумма ведущих из первого набора положительна, как и сумма ведущих из второго, в сумме все ведущие дадут положительное число.

  0
2023-12-16 16:06:21.0 #

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