2008 Indonesia MO Problems/Problem 4
Problem
Note: Problem statement slightly modified for correction.
Let .
(a) Find the number of subset of such that the product of its elements is divisible by 7.
(b) Let denotes the number of subset of in which the sum of its elements, when divided by 7, leaves the remainder . Prove that .
Solution
(a) Find the number of subsets of such that the product of its elements is divisible by 7.
Because is prime, the product of the elements of a subset is divisible by iff the product contains at least one multiple of . To count the number of such subsets, we use complementary counting. has elements which are multiples of . The number of elements not including these multiples is . Thus, because we either include or exclude each of these elements, there are subsets of which do not include any multiples of . Because there are total subsets of , there are subsets whose elements multiply to a multiple of .
(b) Let denote the number of subsets of in which the sum of its elements, when divided by 7, leaves the remainder . Prove that .
The sum of all of the elements of is the th triangular number, . Because , the sum of all the elements is congruent to modulo . Thus, we need not worry about the case where the subset contains all of the elements of . Furthermore, in the case where we only omit , the sum of the elements . Therefore, for every integer such that , if the sum of the elements of the subset , we can find some element such that has been omitted from the subset. We can do this because we have ruled out all the cases where we cannot find such an element (i.e. where none of the elements are omitted and where only is omitted). Thus, , and conseuqently , and so , as desired.
See Also
2008 Indonesia MO (Problems) | ||
Preceded by Problem 3 |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 | Followed by Problem 5 |
All Indonesia MO Problems and Solutions |