![\"\"](\"/images/stars/stars-13.gif\")
You can put this solution on YOUR website!
.
\n" ); document.write( "Find the number of subsets of S = {1, 3, 8, 17, 30, 36, 47, 58},
\n" ); document.write( "so that the sum of the elements in the subset is a multiple of 5.
\n" ); document.write( "(Note that for the empty subset, we take the sum of the elements as 0.)
\n" ); document.write( "~~~~~~~~~~~~~~~~~~~~~~~~~~\r
\n" ); document.write( "
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( " This problem is elementary in it essence.\r
\n" ); document.write( "\n" ); document.write( " So, I tried to find an elementary solution, which I could understand myself\r
\n" ); document.write( "\n" ); document.write( " and to explain to an adequate reader.\r
\n" ); document.write( "
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( "
\r\n" );
document.write( "The set of remainders of given numbers modulo 5 is\r\n" );
document.write( "\r\n" );
document.write( " 1 = 1 mod 5\r\n" );
document.write( "\r\n" );
document.write( " 3 = 3 mod 5\r\n" );
document.write( "\r\n" );
document.write( " 8 = 3 mod 5\r\n" );
document.write( "\r\n" );
document.write( " 17 = 2 mod 5\r\n" );
document.write( "\r\n" );
document.write( " 30 = 0 mod 5\r\n" );
document.write( "\r\n" );
document.write( " 36 = 1 mod 5\r\n" );
document.write( "\r\n" );
document.write( " 47 = 2 mod 5\r\n" );
document.write( "\r\n" );
document.write( " 58 = 3 mod 5\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "So, the list of remainders is {1, 3, 3, 2, 0, 1, 2, 3}, containing 8 elements.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "I will introduce 7 integer numbers 'a', 'b', 'c', 'd', 'e', 'f', 'g', that may have values 0 or 1,\r\n" );
document.write( "and will relate them to the remainders in the list according to this scheme\r\n" );
document.write( "\r\n" );
document.write( " 1 3 3 2 1 2 3\r\n" );
document.write( " a b c d e f g\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "I intently missed the remainder '0' to simplify my reasoning. \r\n" );
document.write( "I will explain it later what to do with the remainder '0'.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "So, my numbers 'a', 'b', 'c', 'd', 'e', 'f', 'g' simply tell us, if the corresponding remainders \r\n" );
document.write( "are included into the subsets or not.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "Then the sum of remainders for any subset in the consideration is \r\n" );
document.write( "\r\n" );
document.write( " a + 3b + 3c +2d + e + 2f + 3g (1)\r\n" );
document.write( "\r\n" );
document.write( "with appropriate values of the coefficients.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "My expression (1) is\r\n" );
document.write( "\r\n" );
document.write( " a + e + 2(f+d) + 3(b+c+g). (2)\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "My task is to determine, how many different solutions (a,b,c,d,e,f,g) has this modular equation \r\n" );
document.write( "\r\n" );
document.write( " a + e + 2(f+d) + 3(b+c+g) = 0 mod 5, (3)\r\n" );
document.write( "\r\n" );
document.write( "if variables a, b, c, d, e, f and g may have the values 0 or 1.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "In equation (3), we can consider 'a', 'e', 'f' and 'd' as free variables, giving them \r\n" );
document.write( "the values 0 or 1 independently.\r\n" );
document.write( "\r\n" );
document.write( "Then for each combinations of 'a', 'e', 'f' and 'd', we should find the number of solutions \r\n" );
document.write( "to equation (3) for variables 'b', 'c' and 'g'.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "I organized my calculations in Excel table, which is shown below.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "In the table, first 4 columns and 16 lines represent all possible values of variables a, e, f and d.\r\n" );
document.write( "\r\n" );
document.write( "The fifth column is the computed sum a + e + 2(f+d).\r\n" );
document.write( "\r\n" );
document.write( "The sixth column is the expression 3(b+c+g) = -(a + e + 2(f+d)) mod 5, according to equation (3).\r\n" );
document.write( "\r\n" );
document.write( "Comparing with the column(5), column (6) has the opposite signs.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "Column (7) is the column (6) taken mod 5.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "(1) (2) (3) (4) (5) (6) (7) (8) (9)\r\n" );
document.write( "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\r\n" );
document.write( " = -3(b+c+g) = 3(b+c+g) = 3(b+c+g) mod 5 in b, c, g\r\n" );
document.write( "------------------------------------------------------------------------------------------------------------------------- \r\n" );
document.write( "0 0 0 0 0 0 0 0 1\r\n" );
document.write( "1 0 0 0 1 -1 4 3 1 \r\n" );
document.write( "0 1 0 0 1 -1 4 3 1 \r\n" );
document.write( "1 1 0 0 2 -2 3 1 3 \r\n" );
document.write( "0 0 1 0 2 -2 3 1 3 \r\n" );
document.write( "1 0 1 0 3 -3 2 4 0 \r\n" );
document.write( "0 1 1 0 3 -3 2 4 0 \r\n" );
document.write( "1 1 1 0 4 -4 1 2 3 \r\n" );
document.write( "0 0 0 1 2 -2 3 1 3 \r\n" );
document.write( "1 0 0 1 3 -3 2 4 0 \r\n" );
document.write( "0 1 0 1 3 -3 2 4 0 \r\n" );
document.write( "1 1 0 1 4 -4 1 2 3 \r\n" );
document.write( "0 0 1 1 4 -4 1 2 3 \r\n" );
document.write( "1 0 1 1 5 -5 0 0 1 \r\n" );
document.write( "0 1 1 1 5 -5 0 0 1 \r\n" );
document.write( "1 1 1 1 6 -6 4 3 1 \r\n" );
document.write( " 24 <<<---sum\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "So, again, the columns (1) - (4) are free variables; the column (5), (6) and (7) are simple straightforward calculations.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "Only columns (8) and (9) require explanations. \r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "To get the number in column (8), we should take the corresponding number from column 7 (let call it z)\r\n" );
document.write( "and solve equation 3x = z mod 5. Then the found x mod 5 goes to column (8).\r\n" );
document.write( "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).\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "To get the number in first row of column 9, we consider the number in the first row of column 8, which is 0.\r\n" );
document.write( "\r\n" );
document.write( "This 'zero' is the right side of the equation b+c+g = 0 mod 5 from equation (3).\r\n" );
document.write( "\r\n" );
document.write( "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).\r\n" );
document.write( "So, we write the number 1 (the number of solutions) in the cell (9,1).\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "To get the number in second row of column 9, we consider the number in the second row of column 8, which is 3.\r\n" );
document.write( "\r\n" );
document.write( "This 'three' is the right side of the equation b+c+g = 3 mod 5 from equation (3).\r\n" );
document.write( "\r\n" );
document.write( "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).\r\n" );
document.write( "So, we write the number 1 (the number of solutions) in the cell (9,2).\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "In the cell (9,3), we have the same situation. So, the number in (9,3) is 1, again.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "In the cell (8,4), we have the number '1'. \r\n" );
document.write( "\r\n" );
document.write( "This 'one' is the right side of the equation b+c+g = 1 mod 5 from equation (3).\r\n" );
document.write( "\r\n" );
document.write( "In variables 'b', 'c', 'g' with the values (0, 1), it has three solution mod 5. \r\n" );
document.write( "These solutions are (b=1, c=0, g=0), (b=0, c=1, g=0), (b=0, c=0, g=1).\r\n" );
document.write( "So, we write the number 3 (the number of solutions) in the cell (9,4).\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "In the cell (9,5), we have the same situation. So, the number in (9,5) is 3, again.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "In the cell (8,6), we have the number '4'. \r\n" );
document.write( "\r\n" );
document.write( "This 'four' is the right side of the equation b+c+g = 4 mod 5 from equation (3).\r\n" );
document.write( "\r\n" );
document.write( "In variables 'b', 'c', 'g' with the values (0, 1), it HAS NO solutions mod 5. \r\n" );
document.write( "So, we write the number 0 (the number of solutions) in the cell (9,6).\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "In the cell (9,7), we have the same situation. So, the number in (9,7) is 0, again.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "In the cell (8,8), we have the number '2'. \r\n" );
document.write( "\r\n" );
document.write( "This 'two' is the right side of the equation b+c+g = 2 mod 5 from equation (3).\r\n" );
document.write( "\r\n" );
document.write( "In variables 'b', 'c', 'g' with the values (0, 1), it has three solution mod 5. \r\n" );
document.write( "These solutions are (b=1, c=1, g=0), (b=1, c=0, g=1), (b=0, c=1, g=1).\r\n" );
document.write( "So, we write the number 3 (the number of solutions) in the cell (9,8).\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "I will stop my explanations for column (9) at this point. The rest of values in column (9) simply repeat\r\n" );
document.write( "the situations described for (9,1), (9,2),(9,3), (9,4), (9,5), (9,6), (9,7), (9,8).\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "The number 24 at the bottom of the 9-th column is the sum of values in this column. It is nothing else as\r\n" );
document.write( "the total number of solutions to equation (3).\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "Thus, so far, there are 24 subsets, satisfying the problem's condition, if do not involve the remainder 0 mod 5,\r\n" );
document.write( "which corresponds to number 30.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "Notice that one of these 24 cases corresponds to the empty subset.\r\n" );
document.write( "It is the case when all coefficients are zeroes a = e = f = d = 0. \r\n" );
document.write( "In this case, the rest of coefficients ALSO are zeroes b = c = g = 0 in the cell (9,1), according to the solution.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "So, we found 23 non-empty subsets and the 24-th subset, which is empty.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "Now, with the number 30 and with individual subset {30}, it doubles 23 subsets to 46 subsets and adds the subset {30}.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "In all, we have now (2*23 + 1) + 1 = 48 sub-sets (47 non-empty subsets PLUS one empty subset). \r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "Here '+1' in parentheses corresponds to the individual subset {30}.\r\n" );
document.write( "\r\n" );
document.write( "\r\n" );
document.write( "ANSWER. In all, there are 48 subsets, satisfying the problem's conditions.\r\n" );
document.write( "\r\n" ); document.write( "\n" ); document.write( "Solved.\r
\n" ); document.write( "
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( " \n" ); document.write( "