Number of "Cool" Subsets

Probability Level 5

A subset of {1, 2, 3, ... , 42} is "cool" if it satisfies both conditions:

  1. if it contains both 1 and 2, then it contains 3;

  2. the sum of its elements is divisible by 7.

Find the number of "cool" subsets.

Note: The sum of elements of empty set is 0.


The answer is 549755813888.

Albert Yiyi by albert yiyi , 31, Malaysia

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Albert Yiyi
Jun 12, 2018

Consider the sum of subsets of {1, 2, 3} :

0 = 0 1 = 1 2 = 2 1 + 2 = 3 (not cool) 3 = 3 1 + 3 = 4 2 + 3 = 5 1 + 2 + 3 = 6 \begin{aligned} 0 &= 0 \\ 1 &= 1 \\ 2 &= 2 \\ 1+2 &= 3 \text{ (not cool) } \\ 3 &= 3 \\ 1+3 &= 4 \\ 2+3 &= 5 \\ 1+2+3 &= 6 \end{aligned}

Notice that there is only one "cool" way to sum to 0~6.

Hence, for any sum of subset of {4, 5, 6, ... 42} , there is one "cool" way to pick a subset of {1, 2, 3} such that their sum is divisible by 7.

So the number of "cool" subsets is equal to the number of subsets of {4, 5, 6, ... 42}, which is 2 42 − 3 = 549755813888 2^{42-3}=549755813888 .

8 Helpful 3 Interesting 1 Brilliant 1 Confused

Very nice bijection!

Calvin Lin Staff - 2 years, 11 months ago

Log in to reply

thank you!

albert yiyi - 2 years, 11 months ago

Here's a different way I used to solve it, which isn't as elegant as the bijection but perhaps more standard. We use roots of unity filter. In general, the sum of all coefficients of terms of degree multiple of m m in a polynomial P ( x ) P(x) is 1 / m ( P ( 1 ) + P ( ω ) + P ( ω 2 ) + ⋯ + P ( ω m − 1 ) , 1/m (P(1)+P(\omega) + P(\omega^2) + \cdots + P(\omega^{m-1}), where ω = e 2 π / m \omega = e^{2 \pi / m} is an m m -th root of unity. So, if we wanted to solve the problem without the first condition, it would just be finding the sum of the coefficients of terms with degree a multiple of seven in the expansion of ( 1 + x ) ( 1 + x 2 ) ( 1 + x 3 ) ⋯ ( 1 + x 42 ) . (1+x)(1+x^2)(1+x^3) \cdots (1+x^{42}).

With the first condition added, we have four cases:

(1) Pick both 1 and 2 (so also must pick 3): The corresponding generating function is x ⋅ x 2 ⋅ x 3 ( 1 + x 4 ) ⋯ ( 1 + x 42 ) x \cdot x^2 \cdot x^3 (1+x^4) \cdots (1+x^{42})

(2) Pick 1 but not 2: The corresponding generating function is x ⋅ ( 1 + x 3 ) ⋯ ( 1 + x 42 ) x \cdot (1+x^3) \cdots (1+x^{42})

(3) Pick 2 but not 1: This gives us x 2 ( 1 + x 3 ) ⋯ ( 1 + x 42 ) . x^2(1+x^3) \cdots (1+x^{42}).

(4) Pick neither 1 nor 2: This gives us ( 1 + x 3 ) ⋯ ( 1 + x 42 ) (1+x^3)\cdots (1+x^{42})

Rick Zhou - 11 months, 1 week ago

Log in to reply

As you may have realized, the sum of those generating functions is P ( x ) = ( 1 + x + x 2 + x 3 + x 4 + x 5 + x 6 ) ∏ i = 4 42 ( 1 + x i ) . P(x) = ( 1 + x + x^2 + x^3 + x^4 + x^5 + x^6 ) \prod_{i=4}^{42} ( 1 + x^i ) . This makes the evaluation of P ( ω ) P ( \omega) very easy because the first polynomial term evaluates to 0 when x x is a 7th root of unity that is not 1.

The factor ( 1 + x + x 2 + x 3 + x 4 + x 5 + x 6 ) ( 1 + x + x^2 + x^3 + x^4 + x^5 + x^6 ) is exactly what Albert expressed above. (Do you see why?)

P.S. FYI To type in Latex, just use \ ( \ ) \backslash( \quad \backslash) instead of the $ $ . I've edited your comment.

Calvin Lin Staff - 11 months, 1 week ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...