Non-Trivial Proof Using Pigeonhole Principle

**Nested Interval** · October 17th 2008, 08:40 AM

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.

**Laurent** · October 17th 2008, 12:52 PM

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

**Nested Interval** · October 17th 2008, 11:26 PM

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.

Thread: Non-Trivial Proof Using Pigeonhole Principle

LinkBack

Thread Tools

Display

Non-Trivial Proof Using Pigeonhole Principle

Similar Math Help Forum Discussions

help me with pigeonhole principle #3

[SOLVED] Proof for equal sum subsets (pigeonhole principle)

Pigeonhole principle

pigeonhole principle

Pigeonhole Principle

Search Tags