2
$\begingroup$

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?

  • 0
    ok, I have the result that $\frac{1}{5}(2^{402}+2^{2000})$ but I don't have the solution, any one can help me2012-12-06

3 Answers 3

3

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 
  • 0
    Nice solution! This number is about $2^{2000}/5 + 2$.2012-12-06
1

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
0

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.