Results 1 to 3 of 3

Thread: 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 $\displaystyle \{a_1,\ldots,a_k\}$ and $\displaystyle \{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 $\displaystyle \sum_{i=1}^k a_i + \sum_{j=1}^l b_j \leq kl$ and the numbers are non-zero (to avoid $\displaystyle a_i=0$ for all $\displaystyle i$). In this case, here is a solution: consider the differences $\displaystyle \delta(K,L)=\sum_{i=1}^K a_i -\sum_{j=1}^L b_j$, where $\displaystyle K\in\{1,\ldots,k\}$ and $\displaystyle L\in\{1,\ldots,l\}$. There are $\displaystyle kl$ of them. What about the possible values? $\displaystyle \delta(K,L)$ is an integer, it is less than $\displaystyle \sum_{i=1}^k a_i-1$ and greater than $\displaystyle 1-\sum_{j=1}^L b_j$, so there are at most $\displaystyle \sum_{i=1}^K a_i+\sum_{j=1}^L b_j -1 <kl$ values for the $\displaystyle \delta(K,L)$'s. By the pigeonhole principle, there are two couples $\displaystyle (K,L)\neq (K',L')$ such that $\displaystyle \delta(K,L)=\delta(K',L')$. For instance, $\displaystyle K>K'$ (they can't be equal since it would imply that $\displaystyle L=L'$ because the numbers are non-zero). Then $\displaystyle \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 $\displaystyle \sum_{i=1}^k a_i$ , $\displaystyle \sum_{j=1}^l b_j$ $\displaystyle <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 $\displaystyle 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 $\displaystyle 1 \leq c < l$ , $\displaystyle 1 \leq d < k$ such that
    $\displaystyle \forall$ $\displaystyle 1 \leq i \leq k$ . $\displaystyle a_i=c$ and $\displaystyle \forall$ $\displaystyle 1 \leq j \leq l$ . $\displaystyle b_j=d$, the proof is trivial: Any d-term subsequence of $\displaystyle (a_i)$ has the same sum as any c-term subsequence of $\displaystyle (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; Oct 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: Oct 31st 2009, 06:38 PM
  2. Replies: 7
    Last Post: Feb 20th 2009, 02:05 PM
  3. Pigeonhole principle
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Jan 31st 2009, 03:59 PM
  4. pigeonhole principle
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Aug 12th 2008, 07:01 AM
  5. Pigeonhole Principle
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Aug 30th 2007, 03:15 PM

Search Tags


/mathhelpforum @mathhelpforum