Cuántos subconjuntos $T$ de $X$ son tales que la suma de los elementos de $T$ es divisible por 5?

Question

Que el $X = \{1,2,\ldots,2000\}$ . ¿Cuántos subconjuntos $T$ de $X$ son tales que la suma de los elementos de $T$ es divisible por 5?

Answer 1

Calculo el número como:

22962613905485090484656664023553639680446354041773904009552854736515325227847406277133189726330125398368919292779749255468942379217261106628518627123333063707825997829062456000137755829648008974285785398012697248956323092729277672789463405208093270794180999311632479761788925921124662329907232844394066536268833781796891701120475896961582811780186955300085800543341325166104401626447256258352253576663441319799079283625404355971680808431970636650308177886780418384110991556717934409897816293912852988275811422719154702569434391547265221166310540389294622648560061463880851178273858239474974548427800576

He encontrado esto de la siguiente manera:

Dejemos que $S_j(n)$ sea el número de subconjuntos de $\{1,2,\ldots,n\}$ cuya suma es congruente con $j$ modulo $5$ .

Cuando $n \geq 5$ ya que cualquier subconjunto de $\{1,2,\ldots,n\}$ es la unión de un único par de subconjuntos, un subconjunto de $\{1,2,\ldots,n-5\}$ y un subconjunto de $\{n-4,n-3,n-2,n-1,n\} \equiv \{0,1,2,3,4\} \pmod 5$ tenemos la recurrencia $$S_j(n) = \sum_{i=0}^4 S_i(n-5)S_k(5)$$ donde $k$ es la solución de la congruencia $i+k \equiv j \pmod 5$ .

He implementado esto en GAP utilizando el siguiente código (nota: GAP utiliza índices que comienzan en 1):

S:=List([1..5],i->List([1],j->Number(Combinations([1,2,3,4,5]),S->Sum(S) mod 5=i mod 5)));

Lo anterior inicializa S con las condiciones de contorno, es decir, cuando $n=5$ .

M:=[ [ 5, 1, 2, 3, 4 ],
     [ 4, 5, 1, 2, 3 ],
     [ 3, 4, 5, 1, 2 ],
     [ 2, 3, 4, 5, 1 ],
     [ 1, 2, 3, 4, 5 ] ];

La matriz M da las soluciones a $i+k \equiv j \pmod 5$ .

for r in [2..400] do
  for j in [1..5] do
    S[j][r]:=Sum([1..5],i->S[i][r-1]*S[M[i][j]][1]);
  od;
od;

Lo anterior sólo implementa la recurrencia.

Como algunas comprobaciones rápidas de cordura: (a) el código siguiente comprueba que los recuentos suman $2^n$ para cualquier $n$ (es decir, el número de subconjuntos de $\{1,2,\ldots,n\}$ ).

for r in [2..400] do
  s:=Sum(List([1..5],i->S[i][r]));
  t:=2^(5*r);
  if(s<>t) then Print(r," failed!\n"); fi;
od;

(b) comprobamos que la respuesta es divisible por $2^{400}$ (como señaló Ross Millikan).

gap> S[5][400] mod (2^400);
0

Answer 2

Algunas reflexiones, no una respuesta completa: Sólo te importa el resto de tus números cuando los divides por $5$ . Su juego tiene $400$ con cada resto. Se pueden ignorar los múltiplos de $5$ y multiplicar por $2^{400}$ al final. La respuesta será un número grande, debería ser alrededor de $\frac 15 2^{2000}$

Empezaría por encontrar cuántas formas de elegir de la $400$ artículos con remanente $1$ para obtener cada resto. Así que para obtener el resto $2$ tienes ${400 \choose 2} + {400 \choose 7} + \ldots +{400 \choose 397}$ . Esto será lo mismo que el número de formas de obtener restos $4$ de la $2$ 's. A continuación, encuentra el número de formas de obtener cada resto de la $1$ y $2$ 's juntos, y así sucesivamente.

Answer 3

Una idea que podría no llevar a ninguna parte.

Dejemos que $T_1, T_2, T_3, T_4$ denotan los subconjuntos de $X$ y la suma tiene un resto de $1,2,3,4$ cuando se divide por 5.

La función de complemento es una biyección de $T_1 \to T_4$ y $T_2 \to T_3$ . Entonces, si encontramos la cardinalidad de $T_1, T_2$ hemos terminado.

Ahora, lo que yo haría es buscar en los subconjuntos de $T_1, T_2$ que contienen/no contienen cualquier combinación de $1,2,3$ (y quizás 4). Básicamente estamos dividiendo estos conjuntos en algunos subconjuntos. Si puedes encontrar una biyección entre estas particiones, ya has terminado.