# How many subsets $T$ of $X$ are such that the sum of the elements of $T$ is divisible by 5?

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?

-
What do you mean the sum contains 5? Presumably you don't mean just $\{1,4\}$ and $\{2,3\}$. –  Ross Millikan Dec 5 '12 at 14:33
for example one subset is $\left \{1;2;3;4 \right \}$ and $1+2+3+4=10$ divisible for 5, if you understand my meanings can you edit my words, sorry about my bad english –  Haruboy15 Dec 5 '12 at 14:47
ok, I have the result that $\frac{1}{5}(2^{402}+2^{2000})$ but I don't have the solution, any one can help me –  Haruboy15 Dec 6 '12 at 5:27

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

-
Nice solution! This number is about $2^{2000}/5 + 2$. –  Jair Taylor Dec 6 '12 at 1:37

Some thoughts, not a full answer: You only care about the remainder of your numbers when divided by $5$. Your set has $400$ with each remainder. You can ignore the multiples of $5$ and multiply by $2^{400}$ at the end. The answer will be a large number-it should be around $\frac 15 2^{2000}$

I would start by finding how many ways to pick from the $400$ items with remainder $1$ to get each remainder. So to get remainder $2$ you have ${400 \choose 2} + {400 \choose 7} + \ldots +{400 \choose 397}$. This will be the same as the number of ways to get remainder $4$ from the $2$'s. Then find the number of ways to get each remainder from the $1$'s and $2$'s together, and so on.

-
@Douglas S. Stones has implemented this well. He is on a mission to demonstrate the capabilities of GAP, and this is a good example. –  Ross Millikan Dec 6 '12 at 5:33

An idea which might not lead anywhere.

Let $T_1, T_2, T_3, T_4$ denote the subsets of $X$ with the sum having a remainder of $1,2,3,4$ when divided by 5.

The complement function is a bijection from $T_1 \to T_4$ and $T_2 \to T_3$. So, if we find the cardinality of $T_1, T_2$ we are done.

Now, what I would do is looking to the subsets of $T_1, T_2$ which contain/don't contain any combination of $1,2,3$ (and maybe 4). Basically we are partitioning these sets in some subsets. If you can find a bijection between these partitions you are done.

-