Combinatorial puzzle reminiscent of knapsack problem. Is this classic?

Question

I have $n$ red integers $a_1,\ldots,a_n$ (not necessarily distinct), all with $1\leq a_i\leq n$. I also have $n$ blue integers $b_1,\ldots,b_n$ with same constraints. I want to show that there is a (red) subset of the $a_i$'s and a blue subset of the $b_j$'s that add up to the same value. I.e. that there exist two non-empty subsets $I,J\subseteq\{1,\ldots,n\}$ such that $\sum_{i\in I}a_i = \sum_{j\in J}b_j$. This is obvious if $a_1=a_2=\cdots=a_n$ and $b_1=b_2=\cdots=b_n$ and it seems that allowing the $a_i$'s and the $b_j$'s to be distinct only give me more opportunities for the existence of matching subsets but I did not manage to find a proof (or a counter-example?).

At the moment the best I can prove is: if the $a_i$'s and $b_j$'s are all $\leq \frac{n}{2}$ then a solution exists and one can even find a solution where $I,J$ are convex subsets of $\{1,\ldots,n\}$ (i.e., they are subintervals). The solution is found by a greedy algorithm that runs in linear-time.

This looks like a classic problem but I am outside my field ...

Answer 1

Yes, it's a "classic problem" in pigeonhole principle for olympiad problems.

Proof by contradiction. Suppose not. Without loss of generality, $ \sum a_i > \sum b_i $.

Define $f(k)$ to be the smallest value $j$ such that

$$ \sum_{i=1}^j a_i > \sum_{i=1}^k b_i$$

Note that the difference between these partial sums $ \sum_{i=1}^{f(k)} a_i - \sum_{i=1}^k b_i $ is in the set $\{1, 2, \ldots , n-1\}$, since it is not 0, and it is capped by $a_j-1$. (Use the fact that $ \sum_{i=1}^{j-1} a_i < \sum_{i=1}^k b_i$)

By pigeonhole principle, since there are $n$ differences but only $n-1$ possibilities, thus there exists 2 differences that are identical. IE

$$ \sum_{i=1}^{f(k)} a_i - \sum_{i=1}^k b_i = \sum_{i=1}^{f(l)} a_i - \sum_{i=1}^l b_i $$

Now, take the differences of the partial sums, and they will have the same sum. IE (with $k>l$)

$$ \sum_{i=f(l) + 1}^{f(k)} a_i = \sum_{i=l+1}^k b_i $$

---

This also proves the observation that it is sufficient to consider subintervals.

This also shows why the condition of $1 \leq a_i \leq n$ is the best possible, with obvious counterexamples if we relax the condition further.

Putnam 1993 has a similar problem, with a similar solution that you are welcome to find.

Let $x_1, \ldots , x_{19}$ be positive integers less than or equal to 93. Let $y_1, \ldots , y_{93}$ be positive integers less than or equal to 19. Prove that there exists a (nonempty) sum of some $x_i$’s equal to a sum of some $y_i$’s.

Answer 2

In [1], the author defines a generalization of this problem (it does not have the restriction that $1 \leq a_i, b_i \leq n$) as Equal Subset Sum From Two Sets and shows that it is NP-complete. It is unclear to me if this special case is also NP-complete. The proof given in the cited thesis does not directly carry over to this case.

EDIT:

In [2], the authors define a different generalization of this problem as Equal Subset Sum with Exclusions: given a graph $G=(X, E)$ and weight function $w: X \rightarrow \mathbb{N}$, does there exist two subsets $Y, Z \subseteq X$ that are independent in $G$ (i.e.: no edge in $E$ joins two elements within $Y$ or $Z$) and have equal weights. The problem posed here can be modeled as ESS with Exclusions by simply taking $G$ to be a complete bipartite graph joining all the red integers on one side with all the blue integers on the other side (and the weight function reflecting the values of the integers).

In that paper, the authors also present an algorithm for solving ESS with Exclusions in pseudo-polynomial time $O(n^2 S)$ where $S$ is the sum of all the weights. In this special case, since $S$ is bounded by $2n^2$, that algorithm should complete in polynomial time.

EDIT #2:

I now realize that the asker's actual question is whether or not this problem always has a solution. Perhaps a careful examination of the algorithm for ESS with Exclusions presented in [2] applied to this case may provide some insight.

1. Cieliebak, Mark. Algorithms and hardness results for DNA physical mapping, protein identification, and related combinatorial problems. Diss. ETH Zurich, 2003.

2. Cieliebak, Mark, et al. On the Complexity of Variations of Equal Sum Subsets. Nord. J. Comput. 14.3 (2008): 151-172.