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
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 contiguous sub-sets of indices $I,J\subseteq [2n]$ such that $\sum_{i\in I}a_i=\sum_{j\in J}b_j$.
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 need to prove there exists subsets from the two sequences such that the sum of their elements match, but not necessarily identify what they are or even know how to find them: we just need to prove they exist somewhere.
- The desired matching property is not a property of one subset, but of a pair of subsets: one from each sequence. So we need to prove that among all possible pairs of subsets from the two sequences, there exists one pair with the desired matching property: that the two subsets within the pair have the same sum.
- "Have the same sum" is a qualitative form of the condition. But it's often easier to work with a quantitative form, where we just evaluate a single expression. One way is to define
$$X(I,J) \equiv \sum_{i\in I}a_i - \sum_{j\in J}b_j \tag{1}$$
for the pair $(I,J)$. Now our goal becomes: prove there exists a pair $(I,J)$ such that $X(I,J)=0$.
- If we want to show there exists one pair with $X(I,J)=0$, a first step is to check the range of possible values. Since $1\leq a_i , b_i \leq n \; \forall \; i$ and $1 \leq |I|, |J| \leq 2n$ for all non-empty $I,J$, the range for $X$ is, $$1 - 2n^2 \leq X \leq 2n^2 - 1$$
- Since the elements $a_i, b_i$ are all integers, the value of $X$ must also be an integer. Hence, based on the range above, $X(I,J)$ has $4n^2 - 1$ distinct values.
- There are $2^{2n} - 1$ possible subsets each for $I$ and $J$. So there are $\left(2^{2n} - 1\right)^2$ possible pairs $(I,J)$. And these pairs can have at most $4n^2 - 1$ distinct $X$ values
- Comparing these two expressions, we have for $n\geq 1$,
$$4n^2 - 1 \leq 2^{2n} - 1 < \left(2^{2n} - 1\right)^2 \tag{2}$$
Simple justification is that this is satisfied at $n=1$, and exponential grows faster than quadratic. But you can use a more rigorous explanation if you want.
- This means that there are more possible pairs $(I,J)$ (the pigeons) than distinct values of $X(I,J)$ (the holes). Therefore by the pigeon-hole principle, there exists two distinct pairs $(I', J')$ and $(I'', J'')$ with the same $X$ value; i.e. $$X(I', J') = X(I'', J'') \tag{3}$$
- Substituting the definition for $X$ and with some rearrangement, we get
$$\sum_{i\in I' \setminus I' \cap I''}a_i - \sum_{i\in I'' \setminus I' \cap I''}a_i = \sum_{j\in J' \setminus J' \cap J''}b_j - \sum_{j\in J'' \setminus J' \cap J''}b_j \tag{4} \label{eq4}$$
- If $I' \subset I''$ and $J' \subset J''$ (or $I' \supset I''$ and $J' \supset J''$), then we would get the desired result. We could try proving there exists two pairs with matching $X$ and the aforementioned property, however this may be difficult.
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.
- The current result we have was obtained using the full space of possible pairs. But we don't have to use the full space. To apply the pigeon-hole principle, there just needs to be more pigeons than holes. So if we instead use a sub-space of pairs, such that the desired property for cancellation holds for any two pairs, while the size of the sub-space is still larger than the number of values of $X$, we will be done.
- Specifically, we want to construct a sub-space such that for any two pairs $(I', J')$ and $(I'', J'')$, $$\left(I' \subset I'' \lor I' \supset I'' \right) \land \left(J' \subset J'' \lor J' \supset J'' \right) \tag{5}\label{eqI'I''J'J''}$$
- The full space of pairs can be constructed via $S^P = P^+([2n]) \times P^+([2n])$, where $P^+() \equiv P() \setminus \phi$ is the power set function excluding the empty set. Likewise, we can assume the desired subspace of pairs is constructable via $ S^F = F_I \times F_J$, where $F_I, F_J \subseteq P^+([2n])$ are families of subsets of $[2n]$.
- Consider just $F_I$. For Eq. $\eqref{eqI'I''J'J''}$ to hold, any member of $F_I$ must be either a subset or superset of all other members. Since we are looking for distinct pairs, these members of $F_I$ should be distinct. This implies each member of $F_I$ must have a distinct size. Since $F_I \subseteq P^+([2n])$, $1 \leq |I| \leq 2n \; \forall \; I \in F_I$. Hence, $|F_I| \leq 2n$. By similar logic, $|F_J| \leq 2n$.
- Then, the desired subspace of pairs, $S^F$ can have a size of atmost $4n^2$. In order to apply the pigeon-hole principle, the size of our subspace must be greater than $4n^2 - 1$. Hence, the constituent families $F_I, F_J$ for the subspace must have the maximal size of $2n$ each.
- At this point, we just need to prove there exists $F_I, F_J$ satisfying our required properties of size $2n$ and each member being a strict subset/superset of each other member. Since $|F_I| = 2n$, there exists a member in $F_I$ of every size from $1$ to $2n$. And since $F_I \subseteq P^+([2n])$, $I \subseteq [2n] \; \forall \; I \in F_I$. So the $I \in F_I$ such that $|I| = 2n$ must be $[2n]$. The $I \in F_I$ such that $|I| = 2n - 1$ must be a subset of $[2n]$, so we can choose it by taking any one element from $[2n]$. Take away another element, and we get $|I| = 2n - 2$. In this fashion, we can generate all the $I \in F_I$ for $|I|$ from $2n$ down to $1$. Therefore, a valid $F_I$ exists. By similar logic, a valid $F_J$ exists. One example is the following
$$F_I = F_J = \{[k] \, | \, k \in \mathbb{N}, k \leq 2n\} \tag{6} \label{eqFIExample}$$
Side-note: We could have just proved existence with the above example in this case. But I included the arguments for cases where an example is not easy to generate
- We have now proved there exists $F_I, F_J$ (such as Eq. \eqref{eqFIExample}) such that for any two distinct pairs $(I', J')$ and $(I'', J'')$ from $S^F = F_I \times F_J$, Eq. \eqref{eqI'I''J'J''} holds. Applying the pigeon-hole principle between the $4n^2$ pairs in this subspace $S^F$ and the $4n^2 - 1$ distinct values of $X$, we can repeat steps 8-9 to get Eq. \eqref{eq4} again.
- But this time we can apply Eq. \eqref{eqI'I''J'J''}. If $I' \subset I''$, then the first sum in the LHS disappears, making the LHS strictly negative, implying the RHS must also be strictly negative. So, following Eq. \eqref{eqI'I''J'J''}, $J' \subset J''$, yielding
$$\sum_{i\in I^*}a_i = \sum_{j\in J^*}b_j, \quad I^* \equiv I'' \setminus I', \; J^* \equiv J'' \setminus J' \tag{7}$$
Similarly, if $I' \supset I''$, we get,
$$\sum_{i\in I^{**}}a_i = \sum_{j\in J^{**}}b_j, \quad I^{**} \equiv I' \setminus I'', \; J^{**} \equiv J' \setminus J'' \tag{8}$$
- Since $I^*, I^{**}, J^*, J^{**} \subseteq [2n]$ (can be shown from their definitions), either $(I^*, J^*)$ or $(I^{**}, J^{**})$ are two sub-sets that the problem statement is looking for.
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.
