problema de combinatoria - suma de enteros

Question

Estoy estudiando para mi examen de combinatoria y no estoy muy convencido de este problema:

¿Cuántos pares de enteros distintos de $1, 2, 3, ..., 60$ están ahí cuya suma de enteros es divisible por $3$ ?

La forma en que lo resolví es que dividí los enteros en $3$ grupos:

$0 \bmod 3, 1 \bmod 3, 2 \bmod 3$ (0m3,1m3,2m3 para futuras referencias).

Cada grupo incluye $20$ enteros, y a partir de ahí ordené todas las combinaciones posibles.

Es una suma de dos enteros, así que las posibles combinaciones son:

(0m3,0m3),(1m3,1m3),(2m3,2m3),(0m3,1m3),(0m3,2m3),(1m3,2m3).

Si dos enteros son del mismo grupo, entonces es $C(20,2)$ y si no lo son es $20^2$ . Como hay 3 casos para cada grupo, la respuesta sería:

$3\cdot C(20,2) + 3\cdot (20^2)$

Resulta que esa no era la respuesta. ¿Qué me falta aquí?

Answer 1

Ya casi has llegado.

Las dos formas, como has dicho, son sumando dos números que son $0 \mod 3$ , o añadiendo un número que es $1 \mod 3$ a uno que es $2 \mod 3$ .

Dado que en el primer caso se extrae del mismo grupo de números, elige dos de ellos, ya que tienen que ser distintos: $_{20}C_2$ .

En el segundo caso, se sabe que los números son distintos (ningún número es a la vez $1 \mod 3$ y $2 \mod 3$ ) así que elige uno del primer grupo y otro del segundo: $20^2$ .

Así que, $190 + 400 = 590$ pares.

Answer 2

Sólo hay 2 casos que satisfacen su criterio: (0m3,0m3) y (1m3,2m3) . Los números son $\binom{20}{2}+ 20^2=590$ .

Answer 3

El problema con tu solución es que tus casos (1m3,1m3), (2m3,2m3), (0m3,1m3) y (0m3,2m3) no funcionan. Los contraejemplos de cada caso son, en realidad, todos los números que se ajustan a los criterios, pero aquí hay algunos específicos para que puedas verlo por ti mismo: (4,4), (5,5), (3,4) y (3,5).

Ahora los casos restantes que funcionan son (0m3, 0m3) y (1m3, 2m3). El primer caso tiene $\binom{20}{2}$ ese trabajo. El segundo caso tiene $20^2$ casos que funcionan.

Answer 4

Otros han señalado tu error, así que sólo añadiré una forma de responder a esta pregunta de manera un poco diferente.

Sí, si se miran los números modulo $3$ A, hay un número igual de números en cada grupo. Pero eso significa que las sumas de los pares de números también serán divisibles en $3$ grupos de igual tamaño. Por lo tanto, el número de pares cuya suma es divisible por $3$ es exactamente un tercio de todos los pares posibles.

Así es:

$$\frac{60 \choose 2}{3}=590$$

EDITAR

¡@antkam señaló correctamente que esta lógica sólo funciona con la sustitución! Bien, entonces, ¿por qué estaba obteniendo el resultado correcto? Es porque $3$ es impar. Es decir, podemos salvar el argumento anterior señalando que hay un tercio de posibilidades de obtener un número que sea $\equiv 0$ en cuyo caso se necesita un número del mismo grupo para obtener una "coincidencia", es decir, hay un $\frac{19}{59}$ posibilidad de obtener una "coincidencia", y para cada uno de los otros grupos se necesita un número de un grupo diferente, y así se tiene una $\frac{20}{59}$ de obtener una coincidencia para cada uno de ellos... para un total de un tercio de posibilidades de obtener una coincidencia. Este La lógica se generalizará para cualquier número impar, ya que para cada uno de los grupos con módulo no cero la coincidencia tiene que venir de un grupo diferente.