Pigeonhole Principle and Sequences

  • Thread starter Nets
  • Start date
  • #1
2
0
Hi guys.

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 :blushing:
 

Answers and Replies

  • #2
Do the subsequences have to be consecutive (the problem doesn't seem to state this)?
 
  • #3
2
0
Yes, they do.
 
  • #4
i'm stuck on it too~
 

Related Threads on Pigeonhole Principle and Sequences

  • Last Post
Replies
1
Views
4K
  • Last Post
Replies
12
Views
11K
  • Last Post
Replies
0
Views
2K
  • Last Post
Replies
8
Views
825
  • Last Post
Replies
17
Views
8K
  • Last Post
Replies
8
Views
3K
  • Last Post
Replies
13
Views
10K
Replies
5
Views
1K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
0
Views
2K
Top