I was tyring to solve:
Let $a_1,a_2,\dots ,a_{2n}$ and $b_1,b_2,\dots ,b_{2n}$ be two sequences of integers such that for every $1\leq i \leq 2n$: $1\leq a_i , b_i \leq n$.
Prove there exists two nonempty sub-sets of indices $I,J\subseteq [2n]$ such that $\sum_{i\in I}a_i=\sum_{j\in J}b_j$.
This problem has been solved for example in:
- Prove there exists two sub-sets of indices $I,J\subseteq [2n]$ such that $\sum_{i\in I}a_i=\sum_{j\in J}b_j$
- The pigeonhole principle – how to solve questions like that?
- Need hint about with pigeonhole principle problem
I understand the solutions there, but it's not clear to me how I was supposed to get there on my own and that's what I want to know.
Understanding a solution does not necessarily mean that I have understood how to deal with a similar question, that is my concern.
I started writing on paper visual representation the series like $a_1,a_2,\dots ,a_{2n}$ and $b_1,b_2,\dots ,b_{2n}$ and circled some of the indexes and hoped that it would somehow help me understand what are the pigeons in this case. But it didn't help, so I would appreciate some help (like tell how you think about it).
Thanks for reading and hope someone can help me:)
Best Answer
EDIT: I completed my solution, which to my belief, involves minimal arbitrary decisions and even 'derives' the arbitrary property of contiguous subsets that the other answers use.
Looking at the answers in the posts you linked, they all seem to actually be solving a stronger version of the problem than required, as below
A contiguous subset is a set of consecutive indices; e.g. $\{3,4,5\}$. It's not obvious to me that you can add the contiguous property in the original problem statement and keep it valid. So I'll write steps for a version of their solutions and my thought process behind it, but not looking for a contiguous subset, so as to be more faithful to the original question
We could use the stronger version of the pigeon-hole principle for this, which says there exists some value of $X$ such that at least $\left\lceil \frac{\left(2^{2n} - 1\right)^2}{4n^2 - 1} \right\rceil$ distinct pairs $(I,J)$ have this value.Now clearly this is a long and seemingly convoluted proof, especially if you compare to the other linked answers. But this is just like research. When solving a problem no one else has solved before, you often have to take a long arduous journey with many twists and turns to get to the solution. Once you find the solution, often you can look back and find a more direct path. However, such direct paths usually involve arbitrary choices, which prove to work out in the end, but at the time you can't really justify why that choice was made.