![\"\"](\"/images/stars/stars-13.gif\")
You can put this solution on YOUR website!
\n" ); document.write( "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.
\n" ); document.write( "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.
\n" ); document.write( "Here are the elements and the mod 5 equivalents of each:
\r\n" ); document.write( "\r\n" ); document.write( " n n mod 5\r\n" ); document.write( " -------------\r\n" ); document.write( " 1 1\r\n" ); document.write( " 3 3\r\n" ); document.write( " 8 3\r\n" ); document.write( " 17 2\r\n" ); document.write( " 30 0\r\n" ); document.write( " 36 1\r\n" ); document.write( " 47 2\r\n" ); document.write( " 58 3
\n" ); document.write( "Two things to notice before we start finding the subsets for which the sum of the elements is a multiple of 5:
\n" ); document.write( "(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.
\n" ); document.write( "(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.
\n" ); document.write( "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.
\n" ); document.write( "Basic subsets with 0 elements....
\n" ); document.write( "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.
\n" ); document.write( "Number of subsets for which the basic set has 0 elements: 4
\n" ); document.write( "Basic subsets with 2 elements....
\n" ); document.write( "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.
\n" ); document.write( "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:
\n" ); document.write( "{17,3}, {17,8}, {17,58}, {47,3}, {47,8}, {47,58}
\n" ); document.write( "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.
\n" ); document.write( "Number of subsets for which the basic set has 2 elements: 6*2*2 = 24.
\n" ); document.write( "Basic subsets with 3 elements....
\n" ); document.write( "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.
\n" ); document.write( "The 1,1,3 case....
\n" ); document.write( "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:
\n" ); document.write( "{1,36,3}, {1,36,8}, {1,36,58}
\n" ); document.write( "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.
\n" ); document.write( "The 1,2,2 case....
\n" ); document.write( "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:
\n" ); document.write( "{1,17,47}, {36,17,47}
\n" ); document.write( "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.
\n" ); document.write( "Number of subsets for which the basic set has 3 elements: 12+8 = 20.
\n" ); document.write( "Basic subsets with 4 elements....
\n" ); document.write( "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.
\n" ); document.write( "The 1,3,3,3 case....
\n" ); document.write( "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:
\n" ); document.write( "{1,3,8,58}, {36,3,8,58}
\n" ); document.write( "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.
\n" ); document.write( "The 2,2,3,3 case....
\n" ); document.write( "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:
\n" ); document.write( "{17,47,3,8}, {17,47,3,58}, {17,47,8,58}
\n" ); document.write( "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.
\n" ); document.write( "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
\n" ); document.write( "ANSWER: 53
\n" ); document.write( " \n" ); document.write( "