Solution

Seven of Fourteen

Show the problem again

How many 7-element subsets of {1, 2, ..., 14} have a sum divisible by 7? Give an integer.

Worked solution

The answer is 492. Group the subsets by how they meet the two blocks {1, ..., 7} and {8, ..., 14}; each block is a complete residue system mod 7. There are $\binom{14}{7} = 3432$ subsets in all; set aside the two blocks themselves and consider the other 3430. For such a subset $S$, both $A = S \cap \{1..7\}$ and $B = S \cap \{8..14\}$ are proper nonempty parts, with $1 \le |A| \le 6$. Shifting the elements of $A$ cyclically within {1, ..., 7} (i.e. adding $t$ mod 7) while fixing $B$ changes the sum by $t|A|$ mod 7. Since 7 is prime and $|A| \not\equiv 0$, the seven shifts give seven different subsets whose sums run through all residues. These orbits partition the 3430 subsets into groups of 7 with exactly one good subset each: 490 good subsets. Both blocks have sum 28 or 77, both divisible by 7, so add 2: the answer is 490 + 2 = 492, matching the general formula $\left(\binom{2p}{p} - 2\right)/p + 2$.

Source: The case p = 7 of IMO 1995 Problem 6. Statement written for AxiomIQ.