Hi guys.(adsbygoogle = window.adsbygoogle || []).push({});

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

Given any two sequences of integers of lengthn, [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.

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 [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 theremustexist 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

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Pigeonhole Principle and Sequences

**Physics Forums | Science Articles, Homework Help, Discussion**