# Thread:

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.
Attached Thumbnails

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

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 $\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.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 33, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9658109545707703, "perplexity_flag": "head"}