2
$\begingroup$

Given a positive integer $n$, what is the minimum positive real number $b(n)$ such that for any $a_1,\ldots,a_n\in[0,1]$, some two subset sums differ by at most $b(n)$?

This is similar to subset sum problems, except it is a worst-case instead of an optimization variant.

$\endgroup$
1
  • 3
    $\begingroup$ The answer is somewhere between $1/2^{n-1}$ (attained for the set $\{2^{i+1-n}\colon 0\le i\le n-1\}$) and $n/(2^n-1)$ (we have $2^n$ subset sums residing in the interval $[0,n]$). So, the fight can be for a logarithmic factor only. $\endgroup$
    – Seva
    Mar 16 '20 at 20:56
2
$\begingroup$

As I wrote in my comment, the trivial bounds are $1/2^{n-1}$ and $n/(2^n-1)$. Here is a proof of the estimate $b(n)<3\sqrt n/2^n$; maybe it can be improved further using the same idea.

Consider the random variable $X=c_1a_1+\dotsb+c_na_n$ where $c_1,\dotsc,c_n$ independently take values $0$ and $1$, with equal probability. Writing $S_1:=a_1+\dotsb+a_n$ and $S_2:=a_1^2+\dotsb+a_n^2$, we have $\mathbb E(X)=S_1/2$ and $\mathbb V(x)=S_2/4$; hence, by Chebyshev's inequality, $$ P(|X-S_1/2|\ge t) \le \frac{S_2}{4t^2}. $$ We choose $t:=\sqrt{S_2}$ to conclude that with probability at least $3/4$ we have $|X-S_1/2|<\sqrt{S_2}$. In other words, there are at least $\frac34\cdot 2^n$ $n$-tuples $(c_1,\dotsc,c_n)$ with $c_1a_1+\dotsb+c_na_n$ in the range $(S_1/2-\sqrt{S_2},S_1/2+\sqrt{S_2})$. Among these $n$-tuples there are two such that the corresponding sums are at most $$ 2\sqrt{S_2}/((3/4)\cdot 2^n-1) \approx \frac83\sqrt{|S_2|}/2^n $$ away from each other. It remains to notice that $S_2\le n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.