A combination problem about same sum subsets

101 Views Asked by At

Suppose $k$ is such that, given any $k$ distinct integers in $\{1,2,\dots,100\}$, there are two distinct subsets with the same sum. What is the minimum possible value of $k$?

I have $8≤ k_{min} ≤10$. For the lower bound, note $\{1,2,4,8,16,32,64\}$ has size $7$ and no distinct subsets with the same sum. And if you have a subset of size $10$, then there are $1024$ distinct subsets (all lying in $\{0,1,2,\dots,1000\}$, so two distinct subsets must have the same sum.

1

There are 1 best solutions below

0
On

The 8-subset $\{54, 76, 87, 93, 96, 98, 99, 100\}$ from an answer to this question shows that $k \ge 9$.