Difference between revisions of "2007 iTest Problems/Problem 49"
(Created page with "== Problem == How many <math>7</math>-element subsets of <math>\{1, 2, 3,\ldots , 14\}</math> are there, the sum of whose elements is divisible by <math>14</math>? == Solution ==") |
Rockmanex3 (talk | contribs) (Solution to Problem 49 -- inspired by solution to problem on Math Prize for Girls) |
||
| Line 1: | Line 1: | ||
| − | == Problem == | + | ==Problem== |
| − | How many <math>7</math>-element subsets of <math>\{1, 2, 3,\ldots , 14\}</math> are there, the sum of whose elements is divisible by <math>14</math>? | + | How many <math>7</math>-element subsets of <math>\{1, 2, 3,\ldots , 14\}</math> are there, the sum of whose elements is divisible by <math>14</math>? |
| − | == Solution == | + | ==Solution== |
| + | |||
| + | In order for a number to be divisible by <math>14</math>, the number must be divisible by <math>2</math> and <math>7</math>. | ||
| + | |||
| + | <br> | ||
| + | For divisibility by <math>7</math>, we can consider a coloring where elements inside the subset are red and elements outside the subset are blue. We can also split the coloring into two sections -- one from numbers 1 to 7, and another from numbers 8 to 14. Note that the total number of elements in a subset must be 7, so the number of red elements in the first section determines the number of red elements in the second section. Thus, we can split into two cases -- one where all sections are monochromatic and another where not all sections are monochromatic. | ||
| + | |||
| + | <br> | ||
| + | For the first case, because of the seven member limit for subsets, there are <math>2</math> options -- one where the first section is all red and one where the first section is all blue. For the second case, we can apply a cyclic shift on only the first section (i.e.: where RBBBBBB becomes BRBBBBB), and since the rest of the cases are covered, the rest of the cases can be divided into groups of 7. Doing a cyclic shift on the first section would result in an increase mod 7 of <math>n</math>, where <math>n</math> is the number of red elements in the first section. Since <math>n</math> is not a multiple of 7, each cyclic shift (up to the seventh one) result in a different residue mod 7. | ||
| + | |||
| + | <br> | ||
| + | Since the raw total of 7-element subsets of <math>\{1, 2, 3,\ldots , 14\}</math> is <math>\binom{14}{7} = 3432</math>, the total number of 7-element subsets that sum to a multiple of 7 is <math>2 + \frac{3432-7}{7} = 492</math>. | ||
| + | |||
| + | <br> | ||
| + | Now we need to find the number of 7-element subsets that sum to a multiple of 7 to also be a multiple of 2. To do this, note that one can swap the two sections of the original coloring and maintain the same residue mod 7. Thus, if <math>A</math> is the set of all 492 subsets, then each element of <math>A</math> has a corresponding element that is also in <math>A</math>. Moreover, during the swap, the parity is reversed because an odd number of residues would be affected (as residues that are colored red for both sections would be unaffected), so half of the subsets would be even. | ||
| + | |||
| + | <br> | ||
| + | Therefore, the number of 7-element subsets that sum to a multiple of 14 is <math>\frac{492}{2} = \boxed{246}</math>. | ||
| + | |||
| + | ==See Also== | ||
| + | {{ITest box|year=2007|num-b=48|num-a=50}} | ||
| + | |||
| + | [[Category:Olympiad Combinatorics Problems]] | ||
Revision as of 17:14, 1 February 2020
Problem
How many 
-element subsets of 
are there, the sum of whose elements is divisible by 
?
Solution
In order for a number to be divisible by , the number must be divisible by 
and .
For divisibility by , we can consider a coloring where elements inside the subset are red and elements outside the subset are blue. We can also split the coloring into two sections -- one from numbers 1 to 7, and another from numbers 8 to 14. Note that the total number of elements in a subset must be 7, so the number of red elements in the first section determines the number of red elements in the second section. Thus, we can split into two cases -- one where all sections are monochromatic and another where not all sections are monochromatic.
For the first case, because of the seven member limit for subsets, there are options -- one where the first section is all red and one where the first section is all blue. For the second case, we can apply a cyclic shift on only the first section (i.e.: where RBBBBBB becomes BRBBBBB), and since the rest of the cases are covered, the rest of the cases can be divided into groups of 7. Doing a cyclic shift on the first section would result in an increase mod 7 of 
, where is the number of red elements in the first section. Since is not a multiple of 7, each cyclic shift (up to the seventh one) result in a different residue mod 7.
Since the raw total of 7-element subsets of is 
, the total number of 7-element subsets that sum to a multiple of 7 is 
.
Now we need to find the number of 7-element subsets that sum to a multiple of 7 to also be a multiple of 2. To do this, note that one can swap the two sections of the original coloring and maintain the same residue mod 7. Thus, if 
is the set of all 492 subsets, then each element of has a corresponding element that is also in . Moreover, during the swap, the parity is reversed because an odd number of residues would be affected (as residues that are colored red for both sections would be unaffected), so half of the subsets would be even.
Therefore, the number of 7-element subsets that sum to a multiple of 14 is 
.
See Also
| 2007 iTest (Problems, Answer Key) | ||
| Preceded by: Problem 48 |
Followed by: Problem 50 | |
| 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 • 26 • 27 • 28 • 29 • 30 • 31 • 32 • 33 • 34 • 35 • 36 • 37 • 38 • 39 • 40 • 41 • 42 • 43 • 44 • 45 • 46 • 47 • 48 • 49 • 50 • 51 • 52 • 53 • 54 • 55 • 56 • 57 • 58 • 59 • 60 • TB1 • TB2 • TB3 • TB4 | ||
