Let $ a_1,a_2,\ldots ,a_{100}$ be real numbers, each less than one, satisfy $ a_1+a_2+\cdots+a_{100} > 1$

Show that there exist two integers $p$ and $q$ , $p<q$, such that the numbers

$$a_q, a_q+a_{q-1}, \ldots, a_q+\cdots+a_p,$$

$$a_p, a_p+a_{p+1},\ldots,a_p+\cdots+a_q$$

are all positive.

I proved that if $n$ is the smallest integer such that $ a_1+a_2+\cdots+a_n>1$ then all the sums $a_n,a_n+a_{n-1},\ldots,a_n+\cdots+a_1$ are positive. Will this help to prove?

source: Test of Math at 10+2 level( A collection of old ISI B.stat & B.math entrance exam question papers)

  • $\begingroup$ Can someone suggest me a better tag for the question? $\endgroup$ – Akshay Hegde Nov 30 '15 at 4:53
  • $\begingroup$ Your tags are fine. The question is really a combinatorics question (and not quite an inequality question), and it indeed sounds like contest-math. However, it is best to clearly state where you got the problem from, so that we know it's not an ongoing contest (otherwise the question is not allowed). $\endgroup$ – user21820 Nov 30 '15 at 5:16

[I found this solution collaboratively with someone else offline.] $\def\nn{\mathbb{N}}$ $\def\rr{\mathbb{R}}$

Let $T(n) = ( \text{The theorem is true for any length-$n$ sequence from $\rr$} )$, for any $n \in \nn$.

If $T(n)$ is false for some $n \in \nn$:

  Let $m \in \nn$ be the minimum such that $T(m)$ is false [by well-ordering].

  Let $a_{1..m}$ be a sequence that does not satisfy the theorem.

  For any $p \in [1..m]$:

    If $\sum_{k=1}^p a_k \le 0$:

      $\sum_{k=p+1}^m a_k \ge \sum_{k=1}^m a_k > 1$.

      Also $a_{p+1..m}$ satisfies the theorem [by minimality of $m$].

      Thus some segment of $a_{p+1..m}$ has initial and terminal segments all with positive sum.

      But any segment of $a_{p+1..m}$ is also a segment of $a_{1..m}$.

      Thus $a_{1..m}$ satisfies the theorem, which gives a contradiction.

    Therefore $\sum_{k=1}^p a_k > 0$.

    Similarly $\sum_{k=p}^m a_k > 0$.

  Therefore $a_{1..m}$ has initial and terminal segments all with positive sum.

  Thus $a_{1..m}$ satisfies the theorem, which gives a contradiction.

Therefore $T(n)$ is true for any $n \in \nn$.

  • $\begingroup$ I didn't get some parts of the answer: 1) $a_{1..m} $for a sequence? 2) $\sum ^{p}_{k=1} \leq 0$? $\endgroup$ – Akshay Hegde Nov 30 '15 at 5:03
  • 1
    $\begingroup$ @AkshayHegde: (1) $a_{1..m}$ is just a short-hand for $a_1,a_2,\cdots,a_m$. Same for $[1..m]$ being a short-hand for the collection of all integers from $1$ to $m$. (2) Sorry I missed out the expression to be summed. Edited. $\endgroup$ – user21820 Nov 30 '15 at 5:13
  • $\begingroup$ @AkshayHegde: So do you get it? $\endgroup$ – user21820 Dec 1 '15 at 7:44
  • $\begingroup$ Yeah got it... struggled initially though @user21820 $\endgroup$ – Akshay Hegde Dec 1 '15 at 9:24
  • $\begingroup$ @AkshayHegde: Ah okay great. In general, considering the smallest counter-example (where size is a natural number) can help, even though well-ordering is equivalent to induction. This is because when attempting a proof by contradiction you would start with existence of a counter-example, which by well-ordering immediately gives existence of a smallest counter-example, which is often a lot more information to work with. $\endgroup$ – user21820 Dec 1 '15 at 10:16

If the sum is positive, at least one element is positive. Pick that one as "sequence" (of length 1).

  • $\begingroup$ Please elaborate.. I didn't understand $\endgroup$ – Akshay Hegde Dec 26 '15 at 3:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.