Mostrar que hay en la mayoría $n\choose \left \lfloor\frac{n}{2} \right\rfloor$subconjuntos $A\subset[n]$ tal que $\displaystyle\sum\limits_{i\in{A}} a_i=\alpha$

Question

Deje $a_1, a_2, a_3, ... , a_n$ $\alpha$ n+1 no-cero de los números reales. Probar que existen en la mayoría de las $n\choose \left\lfloor\frac{n}{2}\right\rfloor$ subconjuntos $A\subset[n]$ tal que $\displaystyle\sum\limits_{i\in{A}} a_i=\alpha$

No estoy muy seguro de cómo abordar esto, pero sospecho que es algo que ver con el hecho de que cada antichain es el tamaño en la mayoría de las $n\choose \left \lfloor \frac{n}{2} \right \rfloor$. Yo estaba pensando que tal $A$ que satisfacen la condición de alguna manera podría referirse a un antichain, pero no acabo de ver cómo funciona esto, especialmente ya que si (decir) $x_1+x_2=\alpha$ $x_1+x_2+x_3+x_4=\alpha$ esta sería la relación entre los conjuntos de $\left\{ {1, 2}\right\}$$\left\{ {1, 2, 3, 4}\right\}$, lo que claramente no es parte de un antichain.

Cualquier ayuda sería muy apreciada!

Answer 1

El caso general se reduce al caso de resultados positivos de pesos, que es inmediatamente resuelto por Sperner del teorema. Definir:

$P$ a ser el conjunto múltiple de positivos $\alpha_i$'s,

$Q$ a ser el conjunto múltiple de negativo $\alpha_i$'s (el complemento de $P$)

$Q'$ $Q$ con signos de todos los elementos que se revierte en positivo

$s$ a la suma de los elementos de $Q'$

$P \oplus Q'$ a ser el conjunto múltiple de la unión de $P$ $Q'$

Hay un bijection entre los subconjuntos de a $P \cup Q$ suma $\alpha$, y los subconjuntos de a $P \oplus Q'$ suma $(\alpha + s)$, mediante la sustitución de los elementos seleccionados de $Q$ con los negativos de los elementos de $Q$ no seleccionado.

Por construcción, $P \oplus Q'$ sólo tiene elementos positivos, y sus subconjuntos con suma $\alpha+s$ (o cualquier otra suma fija) forma un antichain. Sperner del teorema es que la cardinalidad de un antichain es en la mayoría de las $n \choose \lfloor \frac{n}{2} \rfloor$.