![](/files/happy5.png)
search problem
Subset-sums equality (pigeonhole version) ★★★
Author(s):
Problem Let
be natural numbers with
. It follows from the pigeon-hole principle that there exist distinct subsets
with
. Is it possible to find such a pair
in polynomial time?
![$ a_1,a_2,\ldots,a_n $](/files/tex/e7587d53923e6a1289b1a25bce813c459b94a973.png)
![$ \sum_{i=1}^n a_i < 2^n - 1 $](/files/tex/2e06c61586963020dafdeb383b019b8cf808f937.png)
![$ I,J \subseteq \{1,\ldots,n\} $](/files/tex/c7ef2d05312ea577dc99d5541b4d6f105c6241b5.png)
![$ \sum_{i \in I} a_i = \sum_{j \in J} a_j $](/files/tex/4a695b4ff5bea4e5166e5740755c25b9de83abaa.png)
![$ I,J $](/files/tex/540bdad470006e47258d2efec74f098ef7dea897.png)
Keywords: polynomial algorithm; search problem
![Syndicate content Syndicate content](/misc/feed.png)