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

2007 iTest Problems/Problem 49

Revision as of 17:14, 1 February 2020 by Rockmanex3 (talk | contribs) (Solution to Problem 49 -- inspired by solution to problem on Math Prize for Girls)

Problem

How many $7$-element subsets of $\{1, 2, 3,\ldots , 14\}$ are there, the sum of whose elements is divisible by $14$?

Solution

In order for a number to be divisible by $14$, the number must be divisible by $2$ and $7$.


For divisibility by $7$, 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 $2$ 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 $n$, where $n$ is the number of red elements in the first section. Since $n$ 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 $\{1, 2, 3,\ldots , 14\}$ is $\binom{14}{7} = 3432$, the total number of 7-element subsets that sum to a multiple of 7 is $2 + \frac{3432-7}{7} = 492$.


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 $A$ is the set of all 492 subsets, then each element of $A$ has a corresponding element that is also in $A$. 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 $\frac{492}{2} = \boxed{246}$.

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2007_iTest_Problems/Problem_49&oldid=116357"