We have two sequences of $2n$ numbers $a_1, a_2,\dots, a_{2n}$ and $b_1,\dots . b_{2n}$, $1\leq a_i , b_i \leq n.$
Prove that there exist 2 sub-sequences, 1 from each sequence, such that the sum of the sub-sequences is equal. I need to use the pigeonhole principle.
I tried to compare the number of possible sums and possible subseries but it lead nowhere
Let $s_0=0, x=1$ and $y=1$ and use the following process until one of the two sequences is exhausted:
$$ \begin{cases} \bullet\text{ if $s_k\le 0$} \rightarrow s_{k+1}=s_k+a_x \\ \quad\quad\text{then increase x by one}\\ \\ \bullet\text{ if $s_k\gt 0$ }\rightarrow s_{k+1}=s_k-b_y \\ \quad\quad\text{then increase y by one}\\ \end{cases}$$
Notice that the maximum value of all $s$ values are $n$. This is because the largest value $s$ can be in the first if condition is $0$. Then one of the $a$ values is added to $s_k$ which has a maximum value of $n$. Similarly notice that the minimum value of all $s$ values are $-n+1$. This is because the smallest value $s$ can be in the second if condition is $1$ then one of the $b$ values is subtracted from $s_k$ which has a maximum value of $n$.
If $a_1$ and $a_2$ are $n$ and all $b$ values are $1$. This is the case where the least number of elements are used from both sequences during the process. This uses $2n+2$ elements. $s_0$ is given from the start before the process begins, therefore we have at least $2n+3$ $s$ values. There are a total of $2n$ possible $s$ values between $-n+1$ and $n$ inclusive. By the pigeonhole-principle there are two $s$ values that are the same. This means there is some combination of $a$ values and negative $b$ values that cancel each other out. In other words there exists two sub-sequences, one from each sequence, such that the sum of the sub-sequences is equal.