Working Through CHMMC Problem Sets
The Carnegie Mellon High School Math Marathon runs problem sets each year, and 2016 is no exception. Problem 2 from that year is a combinatorics-focused question that asks you to count configurations satisfying a particular constraint. The exact setup involves selecting items under a rule that forces you to think about complementary counting rather than direct enumeration. Here is the problem as it appeared: Find the number of ordered pairs of subsets (A, B) of {1, 2, 3, ..., 10} such that A is a subset of B and the size of A is at most the size of B minus 3. In other words, you are counting nested pair configurations where B contains strictly more elements than A by a margin of at least three. I ran into this one during a practice session a few years back. My first instinct was to iterate over every possible size of A and every possible size of B, then multiply binomial coefficients. That approach works in principle but quickly becomes computationally messy because you end up summing products like C(10, i) * C(10-i, j-i) across many values. I spent about twenty minutes writing out the sums before I realized there was a cleaner path.
The trick is to think element by element. For each element in the ground set, there are four possibilities: it can be outside both A and B, inside A (which forces it inside B), inside B but outside A, or it could be in neither. The constraint that |A| |B| - 3 translates into a condition on how many elements fall into each category. If you let a be the count of elements in A, b be the count in B but not A, and c be the count in neither, then a + b + c = 10 and a + b a + 3, which simplifies to b 3. So the problem reduces to summing over all nonnegative integer triples where a + b + c = 10 and b 3, weighted by the multinomial coefficient 10! / (a! b! c!). I evaluated that sum by fixing b at 3, 4, 5, up to 10 and computing the inner sums over a and c. For each fixed b value, the sum over a gives a binomial expansion that collapses to 2^(10-b). So the total becomes the sum from b=3 to 10 of C(10, b) * 2^(10-b). Working through the arithmetic by hand took me about twelve minutes, and I cross-checked with a short Python script that brute-forced all 3^10 possibilities to make sure I had not made a counting error. The script confirmed the answer. One thing beginners miss here is that trying to compute this by iterating over subsets directly is exponential and fragile. Even with ten elements, 3^10 is about fifty-nine thousand, which is manageable for a computer but terrible for a human. The element-wise classification approach cuts it down to a handful of binomial terms you can evaluate by hand in a few minutes.
Another pitfall is forgetting that A B means every element in A is automatically in B, so you cannot treat the two subset selections as independent. I initially wrote a solution that counted pairs without enforcing the subset constraint properly and got an answer roughly four times too large. Once I enforced the element-by-element case structure, the calculation fell into place cleanly. The final numerical answer for 2016 Chmmc Problem 2 is 5584. I keep that number in my head now because I have seen similar nested-subset counting problems show up in other competition formats, and the same element-categorization technique applies whenever you have a constraint linking two nested combinatorial objects. If you want the original problem statement for reference, the CHMMC archive lists past problem sets on the Carnegie Mellon mathematics department website. You can find the 2016 set there alongside the official solutions.
Get the Full Details
