Número real mínimo para la diferencia de la suma de subconjuntos

Question

Dado un número entero positivo $n$ ¿Cuál es el mínimo número real positivo $b(n)$ tal que para cualquier $a_1,\ldots,a_n\in[0,1]$ , algunas de las sumas de dos subconjuntos difieren como máximo en $b(n)$ ?

Esto es similar a problemas de suma de subconjuntos , salvo que se trata de una variante del peor caso en lugar de una variante de optimización.

Answer 1

Como escribí en mi comentario, los límites triviales son $1/2^{n-1}$ y $n/(2^n-1)$ . He aquí una prueba de la estimación $b(n)<3\sqrt n/2^n$ ; tal vez se pueda mejorar aún más utilizando la misma idea.

Consideremos la variable aleatoria $X=c_1a_1+\dotsb+c_na_n$ donde $c_1,\dotsc,c_n$ toman independientemente los valores $0$ y $1$ con igual probabilidad. Escribiendo $S_1:=a_1+\dotsb+a_n$ y $S_2:=a_1^2+\dotsb+a_n^2$ tenemos $\mathbb E(X)=S_1/2$ y $\mathbb V(x)=S_2/4$ por lo tanto, por la desigualdad de Chebyshev, $$ P(|X-S_1/2|\ge t) \le \frac{S_2}{4t^2}. $$ Elegimos $t:=\sqrt{S_2}$ para concluir que con probabilidad al menos $3/4$ tenemos $|X-S_1/2|<\sqrt{S_2}$ . En otras palabras, hay al menos $\frac34\cdot 2^n$ $n$ -tuplas $(c_1,\dotsc,c_n)$ con $c_1a_1+\dotsb+c_na_n$ en el rango $(S_1/2-\sqrt{S_2},S_1/2+\sqrt{S_2})$ . Entre estos $n$ -hay dos que tienen como máximo las siguientes sumas $$ 2\sqrt{S_2}/((3/4)\cdot 2^n-1) \approx \frac83\sqrt{|S_2|}/2^n $$ de los demás. Queda por notar que $S_2\le n$ .