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

Difference between revisions of "2008 Indonesia MO Problems/Problem 4"

(created solution page)
 
(→‎Solution)
 
Line 10: Line 10:
  
 
== Solution ==
 
== Solution ==
 +
(a)  Find the number of subsets of <math>A</math> such that the product of its elements is divisible by 7.
 +
 +
Because <math>7</math> is prime, the product of the elements of a subset is divisible by <math>7</math> iff the product contains at least one multiple of <math>7</math>. To count the number of such subsets, we use [[complementary counting]]. <math>A</math> has <math>\lfloor\tfrac{2008}7\rfloor=286</math> elements which are multiples of <math>7</math>. The number of elements not including these multiples is <math>2008-286=1722</math>. Thus, because we either include or exclude each of these elements, there are <math>2^{1722}</math> subsets of <math>A</math> which do not include any multiples of <math>7</math>. Because there are <math>2^{2008}</math> total subsets of <math>A</math>, there are <math>\boxed{2^{2008}-2^{1722}}</math> subsets whose elements multiply to a multiple of <math>7</math>.
 +
 +
 +
(b) Let <math>N(i)</math> denote the number of subsets of <math>A</math> in which the sum of its elements, when divided by 7, leaves the remainder <math>i</math>. Prove that <math>N(1) - N(2) + N(3) - N(4) + N(5) - N(6) = 0</math>.
 +
 +
The sum of all of the elements of <math>A</math> is the <math>2008</math>th [[triangular number]], <math>\tfrac{2008(2009)}2=1004\cdot2009</math>. Because <math>7|2009</math>, the sum of all the elements is congruent to <math>0</math> [[modulo]] <math>7</math>. Thus, we need not worry about the case where the subset contains all of the elements of <math>A</math>. Furthermore, in the case where we only omit <math>1</math>, the sum of the elements <math>\equiv6\pmod7</math>. Therefore, for every integer <math>n</math> such that <math>1\leq n\leq5</math>, if the sum of the elements of the subset <math>\equiv n\pmod7</math>, we can find some element <math>E</math> such that <math>E+1</math> 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 <math>1</math> is omitted). Thus, <math>N(n)=N(n+1)</math>, and conseuqently <math>N(1)=N(2)=N(3)=N(4)=N(5)=N(6)</math>, and so <math>N(1)-N(2)+N(3)-N(4)+N(5)-N(6)=0</math>, as desired. <math>\blacksquare</math>
  
 
==See Also==
 
==See Also==
 
{{Indonesia MO box|year=2008|num-b=3|num-a=5}}
 
{{Indonesia MO box|year=2008|num-b=3|num-a=5}}

Latest revision as of 17:44, 7 August 2024

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"