Results 1 to 3 of 3

Math Help - Non-Trivial Proof Using Pigeonhole Principle

  1. #1
    Newbie
    Joined
    Oct 2008
    Posts
    2

    Non-Trivial Proof Using Pigeonhole Principle

    Hello,

    Attached is a statement whose proof requires use of the Pigeonhole Principle. I came rather close to proving it on my own, but I would rather not share my sketch of the proof since it probably isn't in the right direction. In my experience, it can be misleading to see a partial solution that is, in fact, impossible to complete.

    Thanks in advance to anyone willing to share their insights.
    Attached Thumbnails Attached Thumbnails Non-Trivial Proof Using Pigeonhole Principle-pigeonhole.png  
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    With your statement, I'd say: the subsequences \{a_1,\ldots,a_k\} and \{b_1,\ldots,b_l\} have the same sum (and so do the empty subsequences). Do you want a strict subsequence? Writing your own steps could have helped to guess what you're looking for.

    My guess (since it makes my proof work): your hypothesis should be \sum_{i=1}^k a_i + \sum_{j=1}^l b_j \leq kl and the numbers are non-zero (to avoid a_i=0 for all i). In this case, here is a solution: consider the differences \delta(K,L)=\sum_{i=1}^K a_i -\sum_{j=1}^L b_j, where K\in\{1,\ldots,k\} and L\in\{1,\ldots,l\}. There are kl of them. What about the possible values? \delta(K,L) is an integer, it is less than \sum_{i=1}^k a_i-1 and greater than 1-\sum_{j=1}^L b_j, so there are at most \sum_{i=1}^K a_i+\sum_{j=1}^L b_j -1 <kl values for the \delta(K,L)'s. By the pigeonhole principle, there are two couples (K,L)\neq (K',L') such that \delta(K,L)=\delta(K',L'). For instance, K>K' (they can't be equal since it would imply that L=L' because the numbers are non-zero). Then \sum_{i=K'+1}^K a_i = \sum_{j=L+1}^{L'} b_j and these subsequences aren't empty. qed
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2008
    Posts
    2
    Thanks for your help. Allow me to clarify a few things: Since I translated the question from another language, I accidentally omitted the word "non-empty". Not only that, but I forgot to note that since it is not required to find a strict subsequence, it is likely that the hypothesis in the exercise is stated incorrectly. Your own hypothesis makes perfect sense, but I interpreted it as \sum_{i=1}^k a_i , \sum_{j=1}^l b_j <kl. I am now convinced that your hypothesis is the correct one; however, I would like to find a counter-example for the statement as I interpreted it.

    I, too, considered the delta-differences in your proof. The possible values under my hypothesis are any number between 2-kl and kl-2 (inclusive), which means that there are 2kl-3 such numbers, with only kl differences. This is why I thought that my direction was off; taking the absolute values of the differences limits the number to kl-1, but then the equal absolute values predicted by the Pigeonhole Principle may not necessarily be written as two regular differences that agree on the sign of the a_i's.

    I suspect that fairly large numbers are required to form a counter-example. I should note that in the "ideal" case where there exist 1 \leq c < l , 1 \leq d < k such that
    \forall 1 \leq i \leq k . a_i=c and \forall 1 \leq j \leq l . b_j=d, the proof is trivial: Any d-term subsequence of (a_i) has the same sum as any c-term subsequence of (b_j). I haven't had any luck finding a counter-example by brute force, but so far I have limited myself to a low range of k and l.
    Last edited by Nested Interval; October 17th 2008 at 11:41 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. help me with pigeonhole principle #3
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 31st 2009, 06:38 PM
  2. Replies: 7
    Last Post: February 20th 2009, 02:05 PM
  3. Pigeonhole principle
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: January 31st 2009, 03:59 PM
  4. pigeonhole principle
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: August 12th 2008, 07:01 AM
  5. Pigeonhole Principle
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 30th 2007, 03:15 PM

Search Tags


/mathhelpforum @mathhelpforum