# Find two subsets with a common sum in two sequences

For a positive integer $$n$$ and two integer sequences $$a_1,a_2...a_n$$ and $$b_1,b_2...b_n$$ where $$\forall i$$, $$a_i,b_i \in [1,n]$$, I want to find two non-empty subsets, one in each sequence, with the same sum.

i.e. I want to find $$1 \leq i_1 and $$1 \leq j_1 where $$p,q \geq 1$$ and $$\sum_{x=1}^p a_{i_x}=\sum_{y=1}^q b_{j_y}$$.

From trying small cases, I highly suspect that such subsets exist for any $$a$$ and $$b$$, but I can't find a rigorous proof for that.

For each $$k\ge 0$$, let $$s_k=a_1+a_2+\dots+a_k,\\ t_k=b_1+b_2+\dots+b_k,$$ with the convention that $$s_0=t_0=0$$. Assume WLOG that $$s_n\le t_n$$, which can achieved by possibly switching $$a$$ and $$b$$. Further assume $$s_n, since in case $$s_n=t_n$$ the entire sets work.
For each $$k=0,1,\dots,n$$, let $$k'$$ be the largest element of $$\{0,1,\dots,n-1\}$$ for which $$s_{k}\ge t_{k'}$$. Note that $$k'$$ exists; there is at least one index $$k'$$ for which $$s_k\ge t_{k'}$$, since $$s_k\ge t_0$$.
We then have that $$0\le s_k-t_{k'}\le n-1.$$ The left inequality is obvious. The right inequality follows by the maximality of $$k'$$; if $$s_k\ge t_{k'}+n$$, then you would also have $$s_k\ge t_{k'+1}$$.
Since $$k$$ can take any of $$n+1$$ values between $$0$$ and $$n$$ inclusive, but $$s_{k}-t_{k'}$$ can only take $$n$$ values between $$0$$ and $$n-1$$ inclusive, by the pigeonhole principle, there must exist indices $$k\ge h$$ for which $$s_k-t_{k'}=s_h-t_{h'},$$ which implies $$s_k-s_h=a_{h+1}+\dots+a_k=b_{h'+1}+\dots+b_{k'}=t_{k'}-t_{h'},$$ so we have found our two equal subsets.