Finding equal partial sum given two $N$-tuples of natural numbers

Solution 1:

Let $a=(a_1,a_2,\ldots,a_n)$ and $b=(b_1,b_2,\ldots,b_n)$ be sequences drawn from $\{1,2,\ldots,n\}$. Assume w.n.l.g. that $a_1 \ge b_1$. Starting with $a'=b'=()$, and keeping track of $S=\sum a' - \sum b'$, repeat the following step (*) $n+1$ times: (1) append the next element of $a$ to $a'$, or (2) append the next element of $b$ to $b'$, or (3) do both; you must choose (1) on the first step and (2) on the second, and your choices must keep $S\in[0,n]$. Since $S$ has now assumed $n+2$ values (counting its initial value of $0$), by the pigeonhole principle it must have assumed the same value twice, say before step $k$ and after step $l\ge k$. Then the elements appended to $a'$ and $b'$ on steps $k$ through $l$ must have equal sums.

This proves that $a$ and $b$ have not only subsets, but contiguous subsequences, with equal sums.

(*) Of course, the proof rests on showing that you can successfully repeat this step -- i.e., that one of the three choices satisfies the constraint on $S$ -- the required number of times. Suppose $a$ and $b$ have elements remaining, and $a_i$ and $b_j$ are their next elements. Choice (1) succeeds unless $S+a_i > n$, and choice (2) succeeds unless $S-b_j < 0$. If both fail, then, choice (3) must succeed, because we have $0 \le n-b_j < S+a_i-b_j <a_i\le n$. So we can repeat the step until either $a$ or $b$ is exhausted: at least $n-1$ additional times after the first two steps, which were forced to choose (1) and (2) respectively, for a total of at least $n+1$ times.