Dado el conjunto $A=\{1,2,\dotsc,14\}$ , encontrar todos los subconjuntos de $7$ elementos que suman un múltiplo de $7$ .

Question

Agradecería que alguien me ayudara con el siguiente problema.

Dado el conjunto $A=\{1,2,\dotsc,14\}$ calcula el número de conjuntos distintos $M \subset A$ tal que $|M| = 7$ y tal que la suma de los elementos de $M$ es un múltiplo de $7$ .

Answer 1

Considere la colección $F_a$ de todos los conjuntos $M \subseteq A$ de cardinalidad $7$ tal que $M \cap \{1,\dots 7\}$ tiene cardinalidad $a$ .

Dejemos que $\sigma$ sea la permutación de $A$ dado por $\sigma(x) = x+1$ para $x = 1, \dots 6$ , $\sigma(7) = 1$ , $\sigma(x) = x$ para $x = 8, \dots 14$ . Entonces el mapeo $M \mapsto \sigma(M)$ es una permutación de $F_a$ . Además, si la suma de los elementos de $M$ es $b$ entonces la suma de los elementos de $\sigma(M)$ es $b + a$ modulo $7$ .

Así, el número de elementos de $F_a$ con la suma $b$ modulo $7$ es el mismo que el número con suma $b + a$ modulo $7$ . Cuando $a \ne 0,7$ La aplicación repetida de este argumento muestra que este número es independiente de $b$ . Por lo tanto, exactamente $1/7$ de los elementos de $F_a$ tienen suma $0$ modulo $7$ .

$F_0$ y $F_7$ son las únicas excepciones a esta regla, y cada una tiene un elemento. Por lo tanto, el número requerido es $\frac{1}{7}\left[\binom{14}{7} - 2\right] + 2 = 492$ .

Answer 2

David publicó su respuesta mientras yo trabajaba en la mía. Su respuesta es mejor si quieres contar los conjuntos; sin embargo, si quieres generarlos, no ayuda.

Esto es lo que estaba escribiendo:

Esta no es una respuesta completa, pero si juntas las piezas, puedes responder a tus dos preguntas (cómo encontrar todos los conjuntos y cuántos hay).

Lo primero es observar que podemos dividir uno de sus conjuntos $A$ en $A_1=A\cap\{1,2,\ldots,7\}$ y $A_2=A\cap\{8,9,\ldots,14\}$ . Entonces tendrá que encontrar el número $n(m,k)$ de subconjuntos de $A_1$ con tamaño $m$ cuya suma equivale a $k\pmod7$ , para $m=0,\ldots,7$ , $k=0,\ldots,6$ . A continuación, puede combinar un conjunto $A_1$ con $(m,k)=(2,3)$ con un conjunto $A_2$ con $(m,k)=(5,4)$ por ejemplo.

Tenga en cuenta que como $A_2$ es $A_1$ desplazado hacia arriba por 7, puede utilizar esta tabla para ambos $A_1$ y $A_2$ .

Ahora, para calcular $n(m,k)$ Obsérvese que la suma de los elementos de $\{1,2,\ldots,7\}$ es un múltiplo de 7; por lo tanto, $n(m,k)=n(7-m,7-k)$ . Eso significa que sólo tiene que encontrar $n(m,k)$ para $m\le 3$ el resto se puede calcular de manera similar a mi discusión sobre la combinación de $A_1$ y $A_2$ .