De cuántas maneras se pueden seleccionar 3 números de $1-30$ para que la suma de ellos sea un múltiplo de 3?

Question

De cuántas maneras se pueden seleccionar 3 números de $1-30$ (cada número se utiliza una sola vez) para que la suma de ellos sea un múltiplo de 3?

La respuesta es $1360$ mediante programación (comprobar la suma de cada combinación), y también sé que la fórmula es $10^{3}+3\cdot\binom{10}{3}$ Pero, ¿cómo explicarlo?

Answer 1

Consideremos el caso general en el que $S\subset \mathbb{Z}$ .

Dejemos que $A_i:=\{n\in S: n\equiv i \pmod{3} \}$ , para $i=0,1,2$ . Entonces la suma de tres números distintos de $S=A_0\cup A_1\cup A_2$ es divisible por $3$ si tiene una de estas formas: $$a_0+a_0+a_0,\quad a_1+a_1+a_1,\quad a_2+a_2+a_2,\quad a_0+a_1+a_2$$ con $a_i\in A_i$ . Ahora enuméralos y obtendrás: $$\binom{|A_0|}{3}+\binom{|A_1|}{3}+\binom{|A_2|}{3}+|A_0||A_1||A_2|$$ donde $|A_i|$ denota la cardinalidad del conjunto $A_i$ .

Answer 2

He encontrado esta respuesta para 1-300 y la suma es divisible por 3 espero que te pueda ayudar

In how many ways can three numbers be selected from the numbers 1,2,…,300
such that their sum is divisible by 3?

Así que podemos elegir los dos primeros números como queramos. El tercero tiene que tener una clase de residuo definida mod 3 para que el total sea divisible por 3 .

Si la tercera clase de residuo es distinta de la clase de residuo de los dos primeros números, los dos primeros tienen que ser de clases de residuo diferentes. El número de formas de elegir uno de cada clase de residuo es ${300 \choose 1} $${200 \choose 1} $${100 \choose 1} $ pero hay seis órdenes diferentes en los que se pueden seleccionar los mismos tres números. Si la clase de residuo final es la misma que una de las anteriores, todas tienen que ser iguales. Elegimos una de las tres clases de residuos, y entonces hay ${100\choose3}$ formas de elegir un triple.

Así que el número total de formas es

$16×{300\choose1}×{200\choose1}×{100\choose1}+3×{100\choose3}$

Y esto es igual a

${100\choose1}×{100\choose1}×{100\choose1}+3×{100\choose3}$

puede encontrar esta respuesta aquí responder