# Homework Help: Pigeonhole Principle and Sequences

1. Nov 2, 2008

### Nets

Hi guys.

1. The problem statement, all variables and given/known data

Given any two sequences of integers of length n, $$\left{\{a_k\right\}_{k=1}^n,\left{\{b_k\right\}_{k=1}^n,$$, where $$1\le a_k,b_k\le n$$ for all $$1\le k\le n$$, show that there are subsequences of $$a_k,b_k$$ 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.

2. Relevant equations

N/A

3. The attempt at a solution

I am completely stuck. So far the best I have is that there are $$\frac{1}{2}n(n+1)$$ many consecutive subsequences of a, and the same number of b. This means that there are $$n^2+n$$ 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 $$n^2$$ (in the case where the entire n-length sequence has n's for each of its elements). Therefore, we have $$n^2+n$$ sums going into $$n^2$$ 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 $$A_I = a_1+a_2+\cdots+a_I$$, where $$1\le I\le n$$, with $$B_I$$ defined similarly. If we assume that no two consecutive sub-sequences from a,b respectively have the same sum, it means that $$A^*=\left{A_I:1\le I\le n\right\}$$ is of size n, and is disjoint from a similarly defined $$B^*=\left{B_I:1\le I\le n\right\}$$. If we can show that there must exist distinct $$x,y\in A^*$$ and $$u,v\in B^*$$ such that $$|x-y|=|u-v|$$ 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

2. Nov 3, 2008

### EternalVortex

Do the subsequences have to be consecutive (the problem doesn't seem to state this)?

3. Nov 3, 2008

### Nets

Yes, they do.

4. Nov 4, 2008

### Math_hunger

i'm stuck on it too~