Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
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
add comment

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
share|improve this answer
    
Nice solution! This number is about $2^{2000}/5 + 2$. –  Jair Taylor Dec 6 '12 at 1:37
add comment

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.

share|improve this answer
    
@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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.