- #1
Nets
- 2
- 0
Hi guys.
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.
N/A
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
Homework Statement
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.
Homework Equations
N/A
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