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.)
Found 4 solutions by CPhill, greenestamps, ikleyn, EPM:
Answer by CPhill(1959)   (Show Source):
You can put this solution on YOUR website! Solution:
We want to find the number of subsets of $S = \{1, 3, 8, 17, 30, 36, 47, 58\}$ such that the sum of the elements in the subset is a multiple of 5.
Let's look at the remainders of the elements when divided by 5:
$1 \equiv 1 \pmod{5}$
$3 \equiv 3 \pmod{5}$
$8 \equiv 3 \pmod{5}$
$17 \equiv 2 \pmod{5}$
$30 \equiv 0 \pmod{5}$
$36 \equiv 1 \pmod{5}$
$47 \equiv 2 \pmod{5}$
$58 \equiv 3 \pmod{5}$
The set of remainders is $\{1, 3, 3, 2, 0, 1, 2, 3\}$.
Let $n=8$ be the number of elements in $S$. The total number of subsets of $S$ is $2^n = 2^8 = 256$.
Let $N_r$ be the number of subsets whose sum of elements is congruent to $r \pmod{5}$, for $r = 0, 1, 2, 3, 4$. We want to find $N_0$.
Consider a polynomial for each element $x \in S$, given by $(1 + z^{x \pmod{5}})$, where $z = e^{2\pi i / 5}$ is a fifth root of unity. The product of these polynomials over all elements of $S$ is:
$P(z) = (1 + z^1)(1 + z^3)(1 + z^3)(1 + z^2)(1 + z^0)(1 + z^1)(1 + z^2)(1 + z^3)$
$P(z) = (1 + z)^2 (1 + z^2)^2 (1 + z^3)^3 (1 + 1)^1$
$P(z) = 2 (1 + z)^2 (1 + z^2)^2 (1 + z^3)^3$
We know that $N_k = \frac{1}{5} \sum_{j=0}^{4} P(z^j) z^{-jk}$.
For $k=0$, $N_0 = \frac{1}{5} \sum_{j=0}^{4} P(z^j)$.
$P(z^0) = P(1) = 2 (1 + 1)^2 (1 + 1)^2 (1 + 1)^3 = 2 \cdot 2^2 \cdot 2^2 \cdot 2^3 = 2 \cdot 4 \cdot 4 \cdot 8 = 256$.
For $j=1$, $z^1 = z$: $P(z) = 2 (1 + z)^2 (1 + z^2)^2 (1 + z^3)^3$.
For $j=2$, $z^2$: $P(z^2) = 2 (1 + z^2)^2 (1 + z^4)^2 (1 + z^6)^3 = 2 (1 + z^2)^2 (1 + z^4)^2 (1 + z)^3$.
For $j=3$, $z^3$: $P(z^3) = 2 (1 + z^3)^2 (1 + z^6)^2 (1 + z^9)^3 = 2 (1 + z^3)^2 (1 + z)^2 (1 + z^4)^3$.
For $j=4$, $z^4$: $P(z^4) = 2 (1 + z^4)^2 (1 + z^8)^2 (1 + z^{12})^3 = 2 (1 + z^4)^2 (1 + z^3)^2 (1 + z^2)^3$.
This calculation seems complex. Let's use a recursive approach.
Let $f(i, r)$ be the number of subsets of the first $i$ elements of $S$ whose sum has a remainder of $r$ when divided by 5.
The base case is $f(0, 0) = 1$ and $f(0, r) = 0$ for $r \neq 0$.
The recurrence relation is $f(i, r) = f(i-1, r) + f(i-1, (r - s_i) \pmod{5})$, where $s_i$ is the $i$-th element of $S$.
$s = [1, 3, 8, 17, 30, 36, 47, 58]$
$rem = [1, 3, 3, 2, 0, 1, 2, 3]$
$f(8, 0) = 52$.
Final Answer: The final answer is $\boxed{52}$
Answer by greenestamps(13198)  (Show Source):
You can put this solution on YOUR website!
The AI solution from the other tutor doesn't show the details of how the answer was obtained using a recursive formula. I didn't try to solve the problem using that process; and my answer is different than his.
We want a subset for which the sum of the elements is a multiple of 5 -- i.e., for which the sum is equal to 0 mod 5.
Here are the elements and the mod 5 equivalents of each:
n n mod 5
-------------
1 1
3 3
8 3
17 2
30 0
36 1
47 2
58 3
Two things to notice before we start finding the subsets for which the sum of the elements is a multiple of 5:
(1) 30 itself is a multiple of 5. So for any subset we find for which the sum of the elements is equal to 0 mod 5, we can add the element 30 to that subset to find another such subset.
(2) The sum of all the elements of the given set is a multiple of 5. So for any subset we find for which the sum of the elements is a multiple of 5, the complement of that subset is another such subset. Note, however, that each such complement might be a subset we have already found.
We now find "basic" subsets for which the sum of the elements is a multiple of 5; then for each such subset we form a second subset by adding the element 30; then for each of those subsets we find the complement of that subset as another subset for which the sum of the elements is a multiple of 5 -- EXCEPT if the complement is a subset we have already found.
Basic subsets with 0 elements....
The empty set { } is the only subset with 0 elements. We can then add the element 30 to get a second subset {30}; then the complement of each of those sets is another subset.
Number of subsets for which the basic set has 0 elements: 4
Basic subsets with 2 elements....
There are no elements of the given set that are equal to 4 mod 5, so these subsets will each contain one element equal to 2 mod 5 and a second element equal to 3 mod 5.
There are 2 elements equal to 2 mod 5 and 3 equal to 3 mod 5. Any of the 2 elements equal to 2 mod 5 can be paired with any of the 3 elements equal to 3 mod 5, giving 6 basic subsets of this type:
{17,3}, {17,8}, {17,58}, {47,3}, {47,8}, {47,58}
To each of these 6 basic subsets we can add the element 30 to get another subset; and the complement of each of those two subsets will be another subset.
Number of subsets for which the basic set has 2 elements: 6*2*2 = 24.
Basic subsets with 3 elements....
To get a basic subset with 3 elements, we can have the mod 5 equivalents of the 3 elements be either 1,1,3 or 1,2,2.
The 1,1,3 case....
There are 2 elements equal to 1 mod 5 and 3 elements equal to 3 mod 5. The two elements equal to 1 mod 5 can be combined with any of the 3 elements equal to 3 mod 5, giving three 3 basic subsets of this type:
{1,36,3}, {1,36,8}, {1,36,58}
To each of these basic subsets we can add the element 30 to get another subset; and the complement of each of those two subsets will be another subset. So the number of subsets for this case is 3*2*2 = 12.
The 1,2,2 case....
There are 2 elements equal to 1 mod 5 and 2 equal to 2 mod 5. Each of the elements equal to 1 mod 5 can be combined with both of the elements equal to 2 mod 5, giving 2 basic subsets of this type:
{1,17,47}, {36,17,47}
To each of these basic subsets we can add the element 30 to get another subset; and the complement of each of those two subsets will be another subset. So the number of subsets for this case is 2*2*2 = 8.
Number of subsets for which the basic set has 3 elements: 12+8 = 20.
Basic subsets with 4 elements....
To get a basic subset with 4 elements, we can have the mod 5 equivalents of the 4 elements be either 1,3,3,3 or 2,2,3,3.
The 1,3,3,3 case....
There are 3 elements euqal to 3 mod 5 and 2 equal to 1 mod 5. The 3 elements equal to 3 mod 5 can be combined with either of the 2 elements equal to 1 mod 5 to form a subset, giving us 2 subsets of this type:
{1,3,8,58}, {36,3,8,58}
Each of these subsets contains 4 elements, so we can't add the element 30 to the subset or take its complement, because doing either will give us a subset we have already counted. So there are 2 subsets of this type.
The 2,2,3,3 case....
There are 2 elements equal to 2 mod 5 and 3 equal to 3 mod 5. The two elements equal to 2 mod 5 can be combined with any 2 of the 3 elements equal to 3 mod 5 to give us a subset, giving us 3 subsets of this type:
{17,47,3,8}, {17,47,3,58}, {17,47,8,58}
As with the 1,3,3,3 case, we can't get new subsets by adding the element 30 or by taking the complement. So there are 3 subsets of this type.
The total number of subsets for which the sum of the elements is a multiple of 5 is the sum of the numbers for all the above cases: 4+24+12+8+2+3 = 53
ANSWER: 53
Answer by ikleyn(52776)  (Show Source):
You can put this solution on YOUR website! .
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.
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}.
ANSWER. In all, there are 48 subsets, satisfying the problem's conditions.
Solved.
Answer by EPM(3)  (Show Source):
You can put this solution on YOUR website!
The correct answer is 48. How do I know? I wrote a program in LibertyBasic.
Here is the output. There are 47, but the empty set considered as having a sum
of 0 makes it 48.
1 30
2 3+17=20
3 3+47=50
4 8+17=25
5 8+47=55
6 17+58=75
7 47+58=105
8 1+3+36=40
9 1+8+36=45
10 1+17+47=65
11 1+36+58=95
12 3+17+30=50
13 3+30+47=80
14 8+17+30=55
15 8+30+47=85
16 17+30+58=105
17 17+36+47=100
18 30+47+58=135
19 1+3+8+58=70
20 1+3+30+36=70
21 1+8+30+36=75
22 1+17+30+47=95
23 1+30+36+58=125
24 3+8+17+47=75
25 3+8+36+58=105
26 3+17+47+58=125
27 8+17+47+58=130
28 17+30+36+47=130
29 1+3+8+17+36=65
30 1+3+8+30+58=100
31 1+3+8+36+47=95
32 1+3+17+36+58=115
33 1+3+36+47+58=145
34 1+8+17+36+58=120
35 1+8+36+47+58=150
36 3+8+17+30+47=105
37 3+8+30+36+58=135
38 3+17+30+47+58=155
39 8+17+30+47+58=160
40 1+3+8+17+30+36=95
41 1+3+8+30+36+47=125
42 1+3+17+30+36+58=145
43 1+3+30+36+47+58=175
44 1+8+17+30+36+58=150
45 1+8+30+36+47+58=180
46 1+3+8+17+36+47+58=170
47 1+3+8+17+30+36+47+58=200
Edwin
|
|
|
