Proving the same sum of two subsequences by Pigeonhole Principle?

Question

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.

Answer 1

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.

Answer 2

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.