Question 1210228
.
Find the number of subsets of S = {1, 3, 8, 17, 30, 36, 47, 58},
so that the sum of the elements in the subset is a multiple of 5. 
(Note that for the empty subset, we take the sum of the elements as 0.)
~~~~~~~~~~~~~~~~~~~~~~~~~~



        This problem is elementary in it essence.

        So, I tried to find an elementary solution, which I could understand myself

        and to explain to an adequate reader.



<pre>
The set of remainders of given numbers modulo 5 is

     1 = 1 mod 5

     3 = 3 mod 5

     8 = 3 mod 5

    17 = 2 mod 5

    30 = 0 mod 5

    36 = 1 mod 5

    47 = 2 mod 5

    58 = 3 mod 5


So, the list of remainders is {1, 3, 3, 2, 0, 1, 2, 3}, containing 8 elements.


I will introduce 7 integer numbers 'a', 'b', 'c', 'd', 'e', 'f', 'g', that may have values 0 or 1,
and will relate them to the remainders in the list according to this scheme

    1   3   3   2   1   2   3
    a   b   c   d   e   f   g


I intently missed the remainder '0' to simplify my reasoning.  
I will explain it later what to do with the remainder '0'.


So, my numbers 'a', 'b', 'c', 'd', 'e', 'f', 'g' simply tell us, if the corresponding remainders 
are included into the subsets or not.


Then the sum of remainders for any subset in the consideration is 

    a + 3b + 3c +2d + e + 2f + 3g    (1)

with appropriate values of the coefficients.


My expression (1) is

    a + e + 2(f+d) + 3(b+c+g).       (2)


My task is to determine, how many different solutions (a,b,c,d,e,f,g) has this modular equation 

    a + e + 2(f+d) + 3(b+c+g) = 0  mod 5,    (3)

if variables a, b, c, d, e, f and g may have the values 0 or 1.


In equation (3), we can consider 'a', 'e', 'f' and 'd' as free variables, giving them 
the values 0 or 1 independently.

Then for each combinations of 'a', 'e', 'f' and 'd', we should find the number of solutions 
to equation (3) for variables 'b', 'c' and 'g'.


I organized my calculations in Excel table, which is shown below.


In the table, first 4 columns and 16 lines represent all possible values of variables a, e, f and d.

The fifth column is the computed sum  a + e + 2(f+d).

The sixth column is the expression  3(b+c+g) = -(a + e + 2(f+d))  mod 5, according to equation (3).

Comparing with the column(5), column (6) has the opposite signs.


Column (7) is the column (6) taken mod 5.


(1)    (2)     (3)     (4)         (5)             (6)             (7)                   (8)          (9)
a	e	f	d	a+e+2(f+d)	-(a+e+2(f+d))	-(a+e+2(f+d)) mod 5   b+c+g mod 5    number of solutions
                               = -3(b+c+g)       = 3(b+c+g)     = 3(b+c+g) mod 5                     in b, c, g
-------------------------------------------------------------------------------------------------------------------------	
0	0	0	0	    0	            0	            0	                  0            1
1	0	0	0	    1	           -1	            4	                  3            1	
0	1	0	0	    1	           -1	            4                     3            1	
1	1	0	0	    2	           -2	            3	                  1            3	
0	0	1	0	    2	           -2	            3	                  1            3	
1	0	1	0	    3	           -3	            2	                  4            0	
0	1	1	0	    3	           -3	            2	                  4            0	
1	1	1	0	    4	           -4	            1	                  2            3	
0	0	0	1	    2	           -2	            3	                  1            3	
1	0	0	1	    3	           -3	            2	                  4            0	
0	1	0	1	    3	           -3	            2	                  4            0	
1	1	0	1	    4	           -4	            1	                  2            3	
0	0	1	1	    4	           -4	            1	                  2            3	
1	0	1	1	    5	           -5	            0	                  0            1	
0	1	1	1	    5	           -5	            0	                  0            1	
1	1	1	1	    6	           -6	            4	                  3            1	
							                                              24    <<<---sum


So, again, the columns (1) - (4) are free variables; the column (5), (6) and (7) are simple straightforward calculations.


Only columns (8) and (9) require explanations. 


To get the number in column (8), we should take the corresponding number from column 7 (let call it z)
and solve equation  3x = z mod 5.  Then the found  x mod 5  goes to column (8).
It is because from the number 3(b+c+g) mod 5 in the column (7) we want to get b+c+g in column (8).



To get the number in first row of column 9, we consider the number in the first row of column 8, which is 0.

This 'zero' is the right side of the equation  b+c+g = 0 mod 5  from equation (3).

In variables 'b', 'c', 'g' with the values (0, 1), it has only one solution mod 5.  This solution is (b=0, c=0, g=0).
So, we write the number 1 (the number of solutions) in the cell (9,1).



To get the number in second row of column 9, we consider the number in the second row of column 8, which is 3.

This 'three' is the right side of the equation  b+c+g = 3 mod 5  from equation (3).

In variables 'b', 'c', 'g' with the values (0, 1), it only one solutions mod 5.  This solution is (b=1, c=1, g=1).
So, we write the number 1 (the number of solutions) in the cell (9,2).


In the cell (9,3), we have the same situation.  So, the number in (9,3) is 1, again.



In the cell (8,4),  we have the number '1'. 

This 'one' is the right side of the equation  b+c+g = 1 mod 5  from equation (3).

In variables 'b', 'c', 'g' with the values (0, 1), it has three solution mod 5.  
These solutions are  (b=1, c=0, g=0),  (b=0, c=1, g=0),  (b=0, c=0, g=1).
So, we write the number 3 (the number of solutions) in the cell (9,4).



In the cell (9,5), we have the same situation.  So, the number in (9,5) is 3, again.



In the cell (8,6),  we have the number '4'. 

This 'four' is the right side of the equation  b+c+g = 4 mod 5  from equation (3).

In variables 'b', 'c', 'g' with the values (0, 1), it HAS NO solutions mod 5.  
So, we write the number 0 (the number of solutions) in the cell (9,6).



In the cell (9,7), we have the same situation.  So, the number in (9,7) is 0, again.



In the cell (8,8),  we have the number '2'. 

This 'two' is the right side of the equation  b+c+g = 2 mod 5  from equation (3).

In variables 'b', 'c', 'g' with the values (0, 1), it has three solution mod 5.  
These solutions are  (b=1, c=1, g=0),  (b=1, c=0, g=1),  (b=0, c=1, g=1).
So, we write the number 3 (the number of solutions) in the cell (9,8).



I will stop my explanations for column (9) at this point.  The rest of values in column (9) simply repeat
the situations described for (9,1), (9,2),(9,3), (9,4), (9,5), (9,6), (9,7), (9,8).



The number 24 at the bottom of the 9-th column is the sum of values in this column. It is nothing else as
the total number of solutions to equation (3).


Thus, so far, there are 24 subsets, satisfying the problem's condition, if do not involve the remainder 0 mod 5,
which corresponds to number 30.


Notice that one of these 24 cases corresponds to the empty subset.
It is the case when all coefficients are zeroes  a = e = f = d = 0. 
In this case, the rest of coefficients ALSO are zeroes  b = c = g = 0  in the cell  (9,1), according to the solution.


So, we found 23 non-empty subsets and the 24-th subset, which is empty.


Now, with the number 30 and with individual subset {30}, it doubles 23 subsets to 46 subsets and adds the subset {30}.


In all, we have now (2*23 + 1) + 1 = 48 sub-sets   (47 non-empty subsets PLUS one empty subset). 


Here '+1' in parentheses corresponds to the individual subset {30}.


<U>ANSWER</U>.  In all, there are  48 subsets, satisfying the problem's conditions.
</pre>

Solved.