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?
How many subsets $T$ of $X$ are such that the sum of the elements of $T$ is divisible by 5?
-
0ok, I have the result that $\frac{1}{5}(2^{402}+2^{2000})$ but I don't have the solution, any one can help me – 2012-12-06
3 Answers
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
-
0Nice solution! This number is about $2^{2000}/5 + 2$. – 2012-12-06
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.
-
0@Douglas S. Stones has implemented this well. He is on a mission to demonstrate the capabilities of GAP, and this is a good example. – 2012-12-06
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.