# Thread: Non-Trivial Proof Using Pigeonhole Principle

1. ## 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.

2. 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

3. 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.