Determine the number of subsets of A=\{1, 2, \ldots, 10\} whose sum of elements are greater than or equal to 28 .
512
To determine the number of subsets of set A, whose sum of elements is greater than or equal to 28, you can use the concept of a power set and sum of subsets.
Step 1: Calculate the total number of subsets of set A:
The number of subsets of a set with n elements is 2^n. In this case, set A has 10 elements, so the number of subsets of A is 2^10 = 1024.
Step 2: Calculate the number of subsets whose sum of elements is less than 28:
We need to find the subsets whose sum of elements is greater than or equal to 28. To do this, we can subtract the number of subsets whose sum of elements is less than 28 from the total number of subsets.
To calculate the number of subsets whose sum of elements is less than 28, we can use a technique called dynamic programming.
Let's define a 2D array dp[i][j], where i is the number of elements considered so far and j is the target sum. dp[i][j] will store the count of subsets whose sum of elements is less than j, considering only the first i elements of set A.
Initialize dp[0][0] to 1, since there is one subset with a sum of 0 (i.e., the empty subset).
For each element in set A (i from 1 to 10), iterate from 0 to 27 for the target sum (j). We can calculate dp[i][j] using the recurrence relation:
dp[i][j] = dp[i-1][j] + dp[i-1][j-A[i]], where A[i] is the value of the i-th element of set A.
Finally, calculate the sum of all dp[10][j] for j = 0 to 27. This will give the number of subsets whose sum of elements is less than 28.
Step 3: Calculate the number of subsets whose sum of elements is greater than or equal to 28:
To get the number of subsets whose sum of elements is greater than or equal to 28, subtract the result from step 2 from the total number of subsets (1024).
Therefore, the number of subsets of A whose sum of elements is greater than or equal to 28 is 1024 - (sum of dp[10][j] for j = 0 to 27).