Probando la sobreyectividad de algún mapa desde un conjunto de potencias hasta un subconjunto de enteros.

Question

Asignamos a cada elemento de a$i$ de $N=\{1,2,...,n\}$ un entero positivo $a_i$. Supongamos que $$a_1+a_2+...+a_n = 2n-2$$ then prove that map $T: \mathcal{P}(N) \a \{1,2,...,2n-2\}$ defined with $$T(X) = \sum _{i\in X}a_i$$ es surjective.

---

Podemos suponer que $a_1\leq a_2\leq ...\leq a_n$.

Claramente, $a_1 = a_2 = 1$ e lo $1,2,2n-3,2n-4$ están en un rango.

También, si $a_i=2$ para algunos $i$ entonces se podría aplicar fácilmente por inducción.

Decir $b_1< b_2<...<b_k$ son todos diferentes valores que aparecen entre los $a_i$.

Luego tenemos a $n _1\cdot b_1+n_2\cdot b_2+...+n_k \cdot b_k = 2n-2$ e $n_1+n_2+..+n_k = n$. Tenemos que probar que para cada una de las $l\leq 2n-2$ tenemos $$n' _1\cdot b_1+n'_2\cdot b_2+...+n'_k \cdot b_k = l$$

para algunos $n'_i\leq n_i$. Y aquí se detiene. No tengo idea de cómo buscar todos los $n_i'$. Alguna idea?

Answer 1

Todas las respuestas están diciendo básicamente lo mismo, así que me limitaré a tratar de decir que en la mayoría de los "teoría de grafos". :)

---

La construcción de un $n$-nodo de árbol de $G$ con el nodo grados de ser $a_1, a_2, ..., a_n$. [Esto puede hacerse, por ejemplo, empezando con los números más altos y mantener la combinación de ellos.] En un principio, cada nodo es de color negro.

Vamos a ser colorante algunos nodos de la red, y la red los nodos representan a $X \in \mathcal{P}(N)$. Por lo tanto $T(X) = $ suma de nodo de grados de la red de nodos.

Inicialmente, cada nodo es negro, es decir $X = \emptyset, T(X) = 0$. Ahora estamos incremento $T(X)$ uno por uno.

• Si la hoja es de color negro, de color rojo. Este incrementos de $T(X)$ por $1$.

• Si todas las hojas son de color rojo, elegir cualquier negro de nodo interno $v \in G$. Supongamos que su grado es $a > 1$. Desde $G$ es un árbol, $G - \{v\}$ es un nuevo gráfico que es una colección de $a$ árboles independientes (incluyendo posiblemente singleton nodos). Cada uno de estos $a$ árboles más pequeños tiene al menos una hoja perteneciente a la original $G$. Por lo tanto la original $G$ tiene al menos $a$ hojas (que son, por supuesto, todo rojo). Ahora, cambie $v$ de negro a rojo, y cualquier cambio $a-1$ hojas de rojo de nuevo a negro. Este incrementos de $T(X)$ por $1$.

Podemos seguir haciendo esto hasta que todos los nodos son de color rojo, en la que el punto de $T(X) = 2n-2$. Por lo tanto $T()$ pasa a través de $\{0, 1, 2, ..., 2n-2\}$, demostrando que es surjective.

Answer 2

He aquí una solución directa (que creo que llega al corazón del problema). (Lo siento, me acabo de dar cuenta de que OP solicitado una solución basada en la teoría de grafos en la recompensa. No hice caso de eso.)

En $ \{ a_i \}$, $k$ 1, y vamos a $a_n$ ser el valor más grande.

Reivindicación 1: $k \geq a_n$.

Si $ k = n-1$, a continuación, $a_n = (2n-2) - (n-1) = n-1$ lo $k \geq a_n$ como se desee.
Si $ k < n-1$, a continuación, $ 2n-2 = \sum a_i \geq k + 2 (n-k-1) + a_n \Rightarrow k \geq a_n$ como se desee.

Reivindicación 2: Para cualquier $ 1 \leq i \leq 2n-1 $, podemos encontrar un subconjunto de a$\{a_i\}$ que suma a estos valores.

Si $ i \leq 2n-2 - k $, luego hacer caso omiso de la $k$ valores de 1 por ahora. Tomar el mayor subconjunto que da una suma $ \leq i $. Tenga en cuenta que la diferencia entre los $i$ y esta suma es estrictamente menor que cualquier no-1 elemento, por lo tanto estrictamente menor que $k$ a partir de la reivindicación 1. Como tal, se pueden utilizar otros 1 para obtener la suma de los $i$.
Si $i > 2n-2 - k$, luego tomar todos los valores 1, y suficiente 1 los valores.

---

Bonus: Probar que la afirmación sigue siendo cierto si $\sum a_i = 2n-1$. Utilizar el mismo argumento (la modificación de la primera reclamación a $ k \geq a_n - 1$. La segunda afirmación está bien como está).

Bonus: Probar que la afirmación sigue siendo cierto si $\sum a_i \in [n+1, 2n-1]$ utilizando un argumento similar.

Answer 3

Suponga que $\{a_i\}$ contiene $k$ copias de $1$. Suponga además que $a$ es el segundo número más bajo que ocurren en algún lugar en la secuencia. Entonces tenemos: $$ k+a(n-k)\leq a_1+...+a_n=2n-2 $$ que puede ser reorganizado para ver que: $$ k\geq\frac{(a-2)n+2} {- 1}> a-2 $$ La última desigualdad se deriva del hecho de que $a\leq n-1$. Por lo tanto la secuencia contiene, al menos, $a-1$ copias de $1$.

Por último, tenga en cuenta que si quitamos $a$ e $a-2$ copias de $1$ a partir de la secuencia que hemos quitado $a-1$ términos y la reducción de la suma por $2(a-1)$: $$ a+(a-2)\cdot 1=2(a-1) $$ Por lo tanto podemos usar la inducción y hemos terminado.

---

Con respecto a la inducción

Tenemos el caso base $n=2,a_1=a_2=1$ que es fácilmente controlado. Tenga en cuenta que $n=1$ es imposible.

Supongamos ahora que hemos demostrado que todos los casos $n<m$. Considere la posibilidad de $n=m$.

---

Para la construcción de los números más altos, simplemente considera el total de $2m-2$ y restar subconjunto de sumas: $$ 0,1,...,2a-1 $$ mediante la eliminación de los subconjuntos de a$a$ e las $a-1$ copias de $1$. Esto nos lleva tan lejos como: $$ 2m-2-(2a-1)=2(m-a)-1 $$

---

Para dar cuenta de los números más bajos, retire $a-1$ términos que se suma a $2(a-1)$ mediante el uso de los argumentos anteriores. Tenga en cuenta que para $m>2$ tenemos $a\geq 2$. Entonces, nos quedamos con $m-(a-1)$ términos que satisfacen: $$ \begin{align} \sum a_i &=2m-2-2(a-1)\\ &=2\left\{m-(a-1)\right\}-2 \end{align} $$ que es uno de los casos cubiertos por la hipótesis de inducción. Tenga en cuenta que $2\leq m-(a-1)<m$ porque $2\leq a\leq m-1$ para la inducción tiene. Así también hemos cubierto la suma de $1$ hasta: $$ 2\left\{m-(a-1)\right\}-2=2(m-a) $$ y así todas las sumas de $1$ través $2m-2$ han sido contabilizados.

Answer 4

Aquí se trata de una solución basada en la teoría de grafos. La idea es quitar el "hojas" del árbol y proceder por inducción.

Asumiendo $A_n = \{a_1, \dots, a_n\}$, $a_1 = 1$ e $a_2 > 1$, considerar el conjunto $A_{n-1} = \{a_2-1, a_3, \dots a_n\}$ que ha $n-1$ elementos cuya suma es $2n-4$ (es decir, quitar una hoja). A partir de la inducción de la hipótesis de que el mapa de $T^{(n-1)}$ cubre $\{1, \dots, 2n-4\}$. Ahora para $i \in \{1, \dots , 2n-4\}$, hay algunos $X \subset A_{n-1}$ tal que $T^{(n-1)}(X) = i$.

• Si $a_2-1 \in X$ , definir $Y :=(X - \{a_2-1\}) \cup \{a_2\}\subset A_n$ , de modo que $T^{(n)}(Y) = i+1$.
• Si $a_2-1 \notin X$, definir $Y :=X \cup \{a_1\} \subset A_n$ , de modo que $T^{(n)}(Y) = i+1$.

Por lo $T^{(n)}$ cubre $2, \dots, 2n-3$. Pero es evidente que también cubre $1 (=a_1)$ e $2n-2 (=\sum_{a\in A_n} a)$, así que hemos terminado.

Answer 5

Cómo sobre el uso de una inducción en $n$?

A partir de la asunción, $a_1\leq a_2\leq \cdots \leq a_n$, que se derivan de algunos de los hechos: (se menciona)

• $a_1=a_2 = 1$

• $a_3 = 1$ o $2$ si $n\geq3$

El segundo hecho que nos hace posible el uso de una inducción!

El caso inicial, $n=2$, es trivial. Ahora, suponga $n\geq 3$.

Vamos a definir una nueva secuencia $\{a_i'\}_{i=1}^{n-1}$ tales que

• $a_1'=a_2' = 1$
• Caso 1. $a_3=2$. Para $i\geq 3$, $a_i' = a_{i+1}$
• Caso 2. $a_3=1$. $a_3' = a_4 -1$ e $a_i'=a_{i+1}$ para $i\geq4$.

A continuación, $a_1'+\cdots+a_{n-1}'=2n-4$. Por la hipótesis de inducción, hay un surjection $T_{n-1}:\mathcal{P}([n-1])\rightarrow [2n-4]$. (aquí, $[n]=\{1,2,\cdots,n\}$)

Para el Caso 1, se puede extender $T_{n-1}$ a $T_n$.

Sin embargo, una extensión de $T_{n-1}$ no es fácil para el Caso 2. (No tengo idea de para el exentsion para este caso, por desgracia.)