2007 iTest Problems/Problem 49

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 .