- #1

- 2

- 0

## Homework Statement

Given any two sequences of integers of length

*n*, [tex]\left{\{a_k\right\}_{k=1}^n,\left{\{b_k\right\}_{k=1}^n,[/tex], where [tex]1\le a_k,b_k\le n[/tex] for all [tex]1\le k\le n[/tex], show that there are subsequences of [tex]a_k,b_k[/tex] such that the sum of the elements in each subsequence is equal, i.e.:

If a = 1,6,.....,3,2,3,...... and b = 3,5,........,2,.., then the subsequence {3,2,3} and {3,5} of a and b would fit the requirements.

## Homework Equations

N/A

## The Attempt at a Solution

I am completely stuck. So far the best I have is that there are [tex]\frac{1}{2}n(n+1)[/tex] many consecutive subsequences of a, and the same number of b. This means that there are [tex]n^2+n[/tex] many total subsequences of a,b total. The sum of a given consecutive subsequence ranges from 1 (in the case where we select one element as the subsequence, with value 1) all the way to [tex]n^2[/tex] (in the case where the entire n-length sequence has n's for each of its elements). Therefore, we have [tex]n^2+n[/tex] sums going into [tex]n^2[/tex] many possible values, implying that at least two sequences have the same value when summed.

The problem is showing that the two sequences (whose existence I just showed) come from a and b separately, and are not both subsequences of just a or just b.

Another thing I tried was consider [tex]A_I = a_1+a_2+\cdots+a_I[/tex], where [tex]1\le I\le n[/tex], with [tex]B_I[/tex] defined similarly. If we assume that no two consecutive sub-sequences from a,b respectively have the same sum, it means that [tex]A^*=\left{A_I:1\le I\le n\right\}[/tex] is of size n, and is disjoint from a similarly defined [tex]B^*=\left{B_I:1\le I\le n\right\}[/tex]. If we can show that there

*must*exist distinct [tex]x,y\in A^*[/tex] and [tex]u,v\in B^*[/tex] such that [tex]|x-y|=|u-v|[/tex] no matter how we choose sequences a,b we are done, but I can't figure out how to do this. It may be a dead end.

Any help would be much appreciated, including hints!

Thanks folks