1

We have two sequences $(a_n)$ and $(b_n)$, of positive integers, such that, $1\leq a_1,...,a_m\leq n$, $1\leq b_1,...,b_n\leq m$ prove that there exist $p\leq q$, $r\leq s$ such that,

$$\sum_{i=p}^{q} a_i =\sum_{i=r}^{s}b_i$$

I think Pigeon Hole Principle can be applied, but I'm not sure how.

Any help will be appreciated.

Community
  • 1
Henry
  • 5,549
  • Are these sequences of integers? – helloworld112358 May 11 '17 at 20:43
  • This is absolutely not true without further conditions. Perhaps the $a_n$ and $b_n$ must be integers? In which case the pigeonhole principle might be brought to bear. – Harald Hanche-Olsen May 11 '17 at 20:43
  • @HaraldHanche-Olsen Added details. – Henry May 11 '17 at 20:50
  • 2
    @Henry: Why do say "it seems trivial"? – quasi May 11 '17 at 20:50
  • If $n=1$, then all $a_i = 1$ and $1 \le b_1 \le m$. This then says that $q-p+1 =b_1$. Which is true.

    This might form the base case for an induction proof.

     – marty cohen May 11 '17 at 21:40
  • A similar (but not identical) question: https://math.stackexchange.com/questions/1870377/the-pigeonhole-principle-how-to-solve-questions-like-that – awkward May 11 '17 at 23:22
  • @awkward Good catch! In fact, the solution to the question you point to solves this one, too. So I'll vote to close this one, now. – Harald Hanche-Olsen May 12 '17 at 06:40
  • @HaraldHanche-Olsen Although the questions are quite similar, this one is a generalization of the previous result (https://math.stackexchange.com/questions/1870377/the-pigeonhole-principle-how-to-solve-questions-like-that)). The previous question is the case $m=n$, whereas in this question we do not have that restriction. It shouldn't be difficult to apply the same method of proof, however (I think). – awkward May 13 '17 at 12:36

0 Answers0