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](https://cstheory.stackexchange.com/questions/17988/subset-sum-difference-problem), except it is a worst-case instead of an optimization variant.



Minimum real number for subset sum difference
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$.


