¿De cuántas maneras podemos dividir un conjunto en subconjuntos más pequeños para que la suma de los números de cada subconjunto sea igual?

Question

Dejemos que $A = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$ ¿Cuántas formas hay de dividir este conjunto en al menos 2 subconjuntos para que la suma de los números de cada subconjunto sea igual?

Esto es lo que he probado: Dejar que $n$ sea el número de subconjuntos y $s$ la suma de los números de un subconjunto (donde todos los conjuntos son iguales). Dado que $n\cdot{}s=45$ , $n$ tiene que dividir $45$ y por otro lado, $s$ no puede ser menor que $9$ por lo que las únicas opciones para $n$ son $3$ y $5$ . Ahora sé que puedo contar cuántas soluciones posibles hay dado el hecho de que $n$ sólo tiene $2$ valores posibles, pero me preguntaba si existe una solución más elegante.

P.D: En realidad esto salió en un concurso de matemáticas y no tuve tiempo de contar todas las soluciones posibles así que si no hay ninguna solución "mejor", ¿qué crees que debería haber hecho ya que sólo tenía alrededor de $5$ minutos para esta pregunta.

Answer 1

Aquí está el tedioso método que mencionó @antkam:

Considera las sumas que suman 9. Tienes:

El conjunto que contiene $9$ . El conjunto que contiene $8$ debe contener $1$ . El conjunto que contiene $7$ debe contener $2$ . El conjunto que contiene $6$ debe contener $3$ (Porque no puede contener $1$ y $2$ que ya se utilizan). El conjunto que contiene $5$ debe contener $4$ (Porque $1, 3$ se utilizan ambos). Sólo hay una forma de distribuir los números $1$ a través de $9$ . Lo único que queda es elegir dónde poner $0$ . Para ello, existen $5$ maneras (Cualquier conjunto puede tener $0$ en ella).

A continuación, considere cuando la suma es $15$ ( $3$ conjuntos). Queremos considerar primero los números más restrictivos (ya que esto eliminará las posibilidades más rápidamente): Escribamos todas las formas posibles de sumar a $15$ que contienen un $9$ en dígitos no nulos:

$1+2+3+9, 1+5+9, 2+4+9, 6+9$

A continuación, haga lo mismo con $8$ :

$1+2+4+8, 1+6+8, 2+5+8, 3+4+8, 7+8$

Sólo tenemos que elegir los dos primeros conjuntos (un conjunto que contiene 9 y otro que contiene 8). El resto de los dígitos estarán en el tercer conjunto. Y, podemos colocar el cero en cualquiera de los tres conjuntos, por lo que cada partición válida de los elementos no nulos puede convertirse en tres particiones distintas cuando añadimos el cero.

$\{1,2,3,9\}$ sólo puede emparejarse con $\{7,8\}$ : $3$ formas

$\{1,5,9\}$ puede emparejarse con $\{3,4,8\}$ o $\{7,8\}$ : $6$ formas

$\{2,4,9\}$ puede emparejarse con $\{1,6,8\}$ o $\{7,8\}$ : $6$ formas

$\{6,9\}$ puede emparejarse con $\{1,2,4,8\}$ , $\{2,5,8\}$ , $\{3,4,8\}$ o $\{7,8\}$ : $12$ formas

Sumando todo, es decir $5+3+6+6+12=32$ formas.

Answer 2

Creo que la clave es entender que $0$ puede ir a donde sea y que cada número debe ir a alguna parte. Dejen a un lado $0$ por el momento.

Cuando $n=5$ tenemos $s=9$ . Podemos utilizar un razonamiento inductivo como el siguiente:

• $9$ debe estar solo, por lo que obtenemos $\{9\}$ y eso deja $\{1,2,3,4,5,6,7,8\}$ .
• $8$ sólo puede emparejarse con $1$ para alcanzar $s=9$ , por lo que obtenemos $\{1,8\}$ y eso deja $\{2,3,4,5,6,7\}$ .
• $7$ sólo puede emparejarse con $2$ para alcanzar $s = 9$ , por lo que obtenemos $\{2,7\}$ y eso deja $\{3,4,5,6\}$ .
• Procediendo de esta manera, encontramos que los subconjuntos tienen el siguiente aspecto $\big\{\{9\}, \{1,8\}, \{2,7\}, \{3,6\}, \{4,5\}\big\}$ .

Lo único que queda es asignar $0$ a algún subconjunto, por lo que obtenemos $5$ posibilidades de $s=9$ .

---

Cuando $n=3$ tenemos $s=15$ y las cosas se complican un poco más. Seguimos estableciendo $0$ para esto.

En primer lugar, observe que $9$ y $8$ deben ir hacia diferentes subconjuntos. A continuación, encontraremos la forma de rellenar el $9$ subconjunto, y para cada una de esas maneras, encontraremos cómo llenar el $8$ subconjunto. Los números restantes formarán su propio subconjunto.

La idea que subyace es que empezar por el número más grande es mejor porque la suma restante es menor, por lo que hay menos opciones que considerar.

Por lo tanto, tenemos $\{1,2,3,4,5,6,7\}$ y tenemos que averiguar de cuántas maneras podemos escoger elementos de ella para llegar a una suma de $6$ . Ahora, procediendo como antes, encontramos que las posibilidades son $\big\{\{6\}, \{1,5\}, \{2,4\}, \{1,2,3\}\big\}$ .

• Si el $9$ susbset es $\{6,9\}$ nos quedamos con $\{1,2,3,4,5,7\}$ y tenemos que averiguar de cuántas maneras podemos escoger elementos de ella para llegar a una suma de $7$ (para completar el $8$ subconjunto). Procedemos como antes y llegamos a $\big\{\{7\}, \{2,5\}, \{3,4\}, \{1,2,4\}\big\}$ . Esto nos da $4$ posibilidades adicionales antes de añadir $0$ .

• Si el $9$ susbset es $\{1,5,9\}$ nos quedamos con $\{2,3,4,6,7\}$ y tenemos que averiguar en cuántas podemos escoger elementos de ella para llegar a una suma de $7$ . Procedemos como antes y llegamos a $\big\{\{7\}, \{3,4\}\big\}$ . Esto nos da $2$ posibilidades adicionales antes de añadir $0$ .

• Si el $9$ susbset es $\{2,4,9\}$ nos quedamos con $\{1,3,5,6,7\}$ y tenemos que averiguar en cuántas podemos escoger elementos de ella para llegar a una suma de $7$ . Procedemos como antes y llegamos a $\big\{\{7\}, \{1,6\}\big\}$ . Esto nos da $2$ posibilidades adicionales antes de añadir $0$ .

• Por último, si el $9$ susbset es $\{1,2,3,9\}$ nos quedamos con $\{4,5,6,7\}$ y tenemos que averiguar en cuántas podemos escoger elementos de ella para llegar a una suma de $7$ . Claramente, la única manera es elegir un solo $7$ que nos da $1$ posibilidad adicional antes de añadir $0$ .

Así que tenemos $9$ posibilidades sin $0$ . Para cada una de estas configuraciones, tenemos $3$ formas de asignar $0$ a un subconjunto, lo que nos da $9\times 3 = 27$ posibilidades totales en el $n=3$ caso.

---

En total, esto nos da $27+5 = 32$ posibilidades.

---

Ahora bien, esta es una forma estructurada de pensar para abordar este problema (abordar los números grandes para reducir las posibilidades de suma sobrantes), pero existe, por supuesto, un enfoque más... operativo. Las funciones generadoras son una herramienta muy útil para cualquier combinador.

Una forma de considerar este problema si se dispone de potencia de cálculo es la siguiente.

Cuando $n=3$ consideramos el producto

$$\prod_{i=0}^9 (x_1^i+x_2^i+x_3^i).\tag{$ * $}$$

Expandiendo este producto, encontraremos una suma de monomios de la forma $c\cdot x_1^ax_2^bx_3^c$ . Cada uno de estos monomios puede interpretarse como sigue: hay $c$ formas de dividir el conjunto $\{0,1,2,\dots,9\}$ de manera que el primero El subconjunto suma a $a$ El segundo El subconjunto suma a $b$ y el tercera El subconjunto suma a $c$ .

En efecto, al ampliar el producto, en cada paso debemos elegir qué $x_i^j$ que estamos tomando. Elección de $x_i^j$ significa asignar el elemento $j$ de $\{0,1,2,\dots,9\}$ a la $i$ -año de subgrupo.

Como queremos que todos nuestros subconjuntos sumen $s=15$ entonces nos interesa el coeficiente de $x_1^{15}x_2^{15}x_3^{15}$ en la expansión de $(*)$ . Por supuesto, como tampoco nos importa el orden de nuestros subconjuntos, tenemos que dividir el resultado final por $3!$ .

Cuando digo que no nos importa el orden de nuestros subconjuntos, quiero decir que la familia de subconjuntos $\big\{\{0,6,9\}, \{7,8\}, \{1,2,3,4,5\}\big\}$ es tan bueno como $\big\{\{7,8\}, \{1,2,3,4,5\}, \{0,6,9\}\big\}$ o cualquier otra permutación.

Puede consultar con Cuadernos Wolfram en línea (o el software matemático de su elección) utilizando 1/3! * Coefficient[Product[(x^i+y^i+z^i),{i,0,9}], x*y*z,15] que la respuesta es $27$ como hacíamos cuando contábamos a mano.

Del mismo modo, para contar el número de posibilidades de $n=5$ miraríamos

$$\frac1{5!}\left[x_1^9x_2^9x_3^9x_4^9x_5^9\right]\left(\prod_{i=0}^9 (x_1^i+x_2^i+x_3^i+x_4^i+x_5^i)\right).$$

Puede consultar con 1/5! * Coefficient[Product[(a^i+b^i+c^i+d^i+e^i),{i,0,9}], a*b*c*d*e, 9] que la respuesta es $5$ como hacíamos cuando contábamos a mano.

Diré, sin embargo, que esta no es una forma computacionalmente barata o rápida de obtener la respuesta (si estás interesado en computacionalmente formas factibles de abordar este problema, tradicionalmente se maneja con una técnica llamada programación dinámica). Así que, si puedes permitirte dejar que el ordenador haga los cálculos por ti mientras tú haces otra cosa, adelante. Por supuesto, también puede ampliar el producto a mano usted mismo si lo prefiere.

También se pueden combinar ambos métodos. Este método se ve claramente perjudicado en los valores más altos de $n$ porque el número de monomios en la expansión del producto crece demasiado rápido con $n$ . Por otro lado, para valores más altos de $n$ , $s$ es menor y vemos en el ejemplo que el razonamiento inductivo se simplifica, con menos combinaciones a considerar.

Por último, este enfoque también aborda otras variaciones de este problema, como la especificación de diferentes sumas para diferentes subconjuntos y también la generalización a subconjuntos ordenados.