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 16:44, 7 August 2024
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 |