# Proving the same sum of two subsequences by Pigeonhole Principle?

Let m,n be positive integers. Suppose $x_1 , ... x_m$ are positive integers between 1 and n and $y_1 , ... y_n$ are positive integers between 1 and m. Prove that there is a nonempty sub sequence of consecutive entries of $x_1 , ... x_m$ and a nonempty sub sequence of consecutive entries of $y_1 , ... y_n$ that have the same sum.

I'm not really sure how to prove this, I would imagine the pigeons are one set of entries, and the holes are another set of entries from the other sub sequence.. but I'm not really sure I get it.

• @RustynYazdanpour It's clear that at least one of the sequences $\{x_k\}$ or the $\{y_k\}$ will contain repetitive entries depending on the whether $m>n$ or $n>m$. I think it's safe to conclude that the members of the sequences do not have to be distinct. – EuYu Sep 17 '13 at 7:46
• @EuYu Thanks, agreed. – Rustyn Sep 17 '13 at 7:52

## 2 Answers

Let $a_i = \sum_1^i x_i$ be the sums of a subset of the possible subsequences (which start at $x_1$ and have strictly increasing sums). Similarly define $b_j = \sum_1^j y_j$.

WLOG let $b_n \ge a_m$ (otherwise switch the $x$ and $y$) throughout in what follows.

So $b_n \ge a_m \ge a_i$. Define $k(i)$ to be the smallest index of $b_j$ s.t. $b_j \ge a_i$. Now we can form a set of differences $D = \{b_{k(i)} - a_i, 1 \le i \le m \}$, which can have upto $m$ elements. Note however that if the number of elements is less than $m$, two differences match, and we have found two subsequences with the same sum as shown in the last para here. Hence let us assume all the differences are distinct and proceed to find a contradiction.

Now think of the elements in $D$ as $m$ pigeons. The holes are the $\{1, 2, 3, ... m-1\}$, which we prove are the only possible values these can take.

First note that $0$ is not an element, otherwise we already have a case of $a_i = b_j$. So all elements of $D$ are positive.

Further, $b_{k(i)} - a_i \ge m \implies b_{k(i)} -m \ge a_i \implies b_{k(i)-1} \ge a_i$ as $b_{k(i)} - b_{k(i)-1} \le m$ (remember $b_i$ sums $y_i$ which are chosen from positive integers only upto $m$). As this would defeat the definition of $k(i)$, this is not possible and hence $b_{k(i)} - a_i < m$, and elements of $D$ cannot equal or exceed $m$.

Thus we have shown that there $m$ pigeons and $m-1$ holes, we must have at least one case where $b_{k(i)} - a_i = b_{k(j)} - a_j$ so $b_{k(i)} - b_{k(j)} = a_i - a_j$ and we have two subsequences with matching sums.

• It might help to point out that if $|D|<m$, then you have found two consecutive subsequences whose values match; that is, you are proceeding by contradiction? – copper.hat Sep 17 '13 at 16:59
• @copper.hat Have rephrased it to reflect your comment. Thanks. – Macavity Sep 17 '13 at 17:05

As a hint, observe that the extreme case is $\gcd(m,n)=1$ and $x_i=n$ for all $i$, $y_j=m$ for all $j$. In this case the only consecutive subsequences that have the same sum are the entire sequences.

• I'm afraid I don't see where this leads us. Would you mind a bit of elaboration? – EuYu Sep 17 '13 at 8:10
• Why is this an extreme case? – copper.hat Sep 17 '13 at 16:37