1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Pigeonhole Principle and Sequences

  1. Nov 2, 2008 #1
    Hi guys.

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

    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.

    2. Relevant equations


    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 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:
  2. jcsd
  3. Nov 3, 2008 #2
    Do the subsequences have to be consecutive (the problem doesn't seem to state this)?
  4. Nov 3, 2008 #3
    Yes, they do.
  5. Nov 4, 2008 #4
    i'm stuck on it too~
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook