Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

2008 Indonesia MO Problems/Problem 4

Problem

Note: Problem statement slightly modified for correction.

Let $A = \{1,2,\ldots,2008\}$.

(a) Find the number of subset of $A$ such that the product of its elements is divisible by 7.

(b) Let $N(i)$ denotes the number of subset of $A$ in which the sum of its elements, when divided by 7, leaves the remainder $i$. Prove that $N(1) - N(2) + N(3) - N(4) + N(5) - N(6) = 0$.

Solution

(a) Find the number of subsets of $A$ such that the product of its elements is divisible by 7.

Because $7$ is prime, the product of the elements of a subset is divisible by $7$ iff the product contains at least one multiple of $7$. To count the number of such subsets, we use complementary counting. $A$ has $\lfloor\tfrac{2008}7\rfloor=286$ elements which are multiples of $7$. The number of elements not including these multiples is $2008-286=1722$. Thus, because we either include or exclude each of these elements, there are $2^{1722}$ subsets of $A$ which do not include any multiples of $7$. Because there are $2^{2008}$ total subsets of $A$, there are $\boxed{2^{2008}-2^{1722}}$ subsets whose elements multiply to a multiple of $7$.


(b) Let $N(i)$ denote the number of subsets of $A$ in which the sum of its elements, when divided by 7, leaves the remainder $i$. Prove that $N(1) - N(2) + N(3) - N(4) + N(5) - N(6) = 0$.

The sum of all of the elements of $A$ is the $2008$th triangular number, $\tfrac{2008(2009)}2=1004\cdot2009$. Because $7|2009$, the sum of all the elements is congruent to $0$ modulo $7$. Thus, we need not worry about the case where the subset contains all of the elements of $A$. Furthermore, in the case where we only omit $1$, the sum of the elements $\equiv6\pmod7$. Therefore, for every integer $n$ such that $1\leq n\leq5$, if the sum of the elements of the subset $\equiv n\pmod7$, we can find some element $E$ such that $E+1$ 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 $1$ is omitted). Thus, $N(n)=N(n+1)$, and conseuqently $N(1)=N(2)=N(3)=N(4)=N(5)=N(6)$, and so $N(1)-N(2)+N(3)-N(4)+N(5)-N(6)=0$, as desired. $\blacksquare$

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2008_Indonesia_MO_Problems/Problem_4&oldid=224708"