[Math] How many subsets $T$ of $X$ are such that the sum of the elements of $T$ is divisible by 5

combinatorics

Let the $X = \{1,2,\ldots,2000\}$. How many subsets $T$ of $X$ are such that the sum of the elements of $T$ is divisible by 5?

Best Answer

I compute the number as:

22962613905485090484656664023553639680446354041773904009552854736515325227847406277133189726330125398368919292779749255468942379217261106628518627123333063707825997829062456000137755829648008974285785398012697248956323092729277672789463405208093270794180999311632479761788925921124662329907232844394066536268833781796891701120475896961582811780186955300085800543341325166104401626447256258352253576663441319799079283625404355971680808431970636650308177886780418384110991556717934409897816293912852988275811422719154702569434391547265221166310540389294622648560061463880851178273858239474974548427800576

I found this as follows:

Let $S_j(n)$ be the number of subsets of $\{1,2,\ldots,n\}$ whose sum is congruent to $j$ modulo $5$.

When $n \geq 5$, since any subset of $\{1,2,\ldots,n\}$ is the union of a unique pair of subsets, one subset of $\{1,2,\ldots,n-5\}$ and one subset of $\{n-4,n-3,n-2,n-1,n\} \equiv \{0,1,2,3,4\} \pmod 5$, we have the recurrence $$S_j(n) = \sum_{i=0}^4 S_i(n-5)S_k(5)$$ where $k$ is the solution to the congruence $i+k \equiv j \pmod 5$.

I implemented this in GAP using the following code (note: GAP uses indices starting at 1):

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

The above initialises S with the boundary conditions, i.e., when $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 ] ];

The matrix M gives the solutions to $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;

The above just implements the recurrence.

As some quick sanity checks: (a) the code below checks that the counts sum to $2^n$ for any given $n$ (i.e. the number of subsets of $\{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) we check that the answer is divisible by $2^{400}$ (as pointed out by Ross Millikan).

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