Los dos conjuntos son disjuntos, $S_1 \cap S_2 = \varnothing$ desde $S(X)$ será par o impar.
Observe que si $a < 1, b > 4n$,$|S_1| = |S_2|$.
Somos más propensos a contraer estas grandes diferencias cuando se corrige el valor de $S(X)=c$, en cuyo caso $|S_1|=0$ o $|S_2|=0$ y que ataba el tamaño del conjunto no vacío.
Deje $S(X) = S(E_0) + S(O_0)$ donde $E\subseteq X$ es el subconjunto de incluso los elementos y $O \subseteq X$ son el impar de elementos.
Los números pares, $E = \{ 2,4,6,\dots, 4n \}$ no afectará a la paridad de $S(X)$ - así que vamos a poner alguna de las $2^{2n}$ subconjuntos $E_0 \subseteq E$ no, y dejar que su suma sea $S(E_0)$.
Sólo los números impares $O = \{ 1,3,\dots, 4n-1\}$ afectarán a la paridad. Una vez que arreglar una colección de números, la suma de los restantes números impares debe ser
$S(O)=c - S(E)$. Cuántos posibles subconjuntos hay?
La proposición que Vamos a mostrar que para cualquier $2n$ números en la mayoría de las $\binom{2n}{n}$ subconjuntos pueden tener la misma suma.
Vamos a probar esto por inducción:
- $n=1$, tenemos dos números de $\{ a_1, a_2\}$. No puede haber más de dos $\binom{2}{1}$ subconjuntos $X$ con el mismo $S(X)$ si $a_1 = a_2$, y ninguno si $a_2 > a_1$.
- Asumir por $n=k$, la hipótesis de inducción tiene $\displaystyle \max_{1 \leq c \leq 4n} |\{X: S(X)=c\}| \leq \binom{2k}{k} $.
- Si se incluye un nuevo elemento $a_{k+1}$, no puede haber más de $ 2 \binom{2k}{k} < \binom{2k+2}{k+1}$ subconjuntos $X$ con el mismo valor de $S(X)$.
Esto suena como una olimpiada problema y me tomó de manera más que el tiempo asignado. Tal vez hay una prolija prueba utilizando el método de probabilidades.
Deje $X \subseteq S$ ser un conjunto aleatorio con $\mathbb{P}[i \in X] = \frac{1}{2}$, de modo que cada conjunto se produce con una probabilidad de $2^{-2n}$.
Hay dos eventos a tener en cuenta:
- $a \leq S(X) \leq b$
- $S(X)$ es un número par o impar
En términos de probabilidades, nuestros dos subconjuntos podría ser por escrito
- $2^{-2n}|S_1| = \mathbb{P}\big[ a \leq S(X) \leq b \bigwedge S(X) \equiv 1 \mod 2\big]$
- $2^{-2n}|S_2| = \mathbb{P}\big[ a \leq S(X) \leq b \bigwedge S(X) \equiv 0 \mod 2\big]$
Se nos pidió para acotar la probabilidad de que estos dos eventos que ocurren:
$$ \frac{|S_1|-|S_2|}{2^{2n}} \leq \frac{1}{2^{2n}}\binom{2n}{n}$$
De hecho, hemos demostrado que la fijación de $S(X)=c$ determina la paridad de $S(X)$:
\begin{eqnarray*} \mathbb{P}\big[ S(X)=c \bigwedge S(X) \equiv 1 \mod 2\big]
&=& \mathbb{P}\big[S(X) \equiv 1 \mod 2 \big|S(X)=c \big]
\mathbb{P}\big[ S(X) = c \big] \\
&=& \left\{ \begin{array}{cc} \mathbb{P}\big[ S(X) = c \big] & c \text{ is odd} \\
0 & c \text{ is even} \end{array}\right.
\end{eqnarray*}
Queda por estimar que $\mathbb{P}[S(X) = c] \leq \frac{1}{2^{2n}}\binom{2n}{n}$.
Nos oserved que $S(X) = S(X_1)+S_2(X_2)$ que se divide en pares e impares partes.
\begin{eqnarray} \mathbb{P}\big[ S(X)=c \bigwedge S(X) \equiv 1 \mod 2\big]
&=& \mathbb{P}\big[ S(X_1)=c- S(X_2) \bigwedge S(X_1) \equiv 1 \mod 2\big] \\
&\leq & \sum_{X_2 \subseteq \{ 2,4,\dots, 2n\}} \mathbb{P}[X_2] \mathbb{P}\big[ S(X_1)=c- S(X_2) | X_2\big] \\
& \leq & \sum_{X_2} \mathbb{P}[X_2] \cdot \frac{1}{2^{2n}} \binom{2n}{n} \\
& = & \frac{1}{2^{2n}} \binom{2n}{n}
\end{eqnarray}
Que es la misma estimación que antes.
Para un punto de partida diferente, mira las notas de la conferencia de las particiones por el mismo hombre, Herbert Wilf.
