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