ONE
    Númas
    ← Back to the programme
    OlympiadHardCombinatorics10–12

    How many subsets of {1,2,…,9}\{1, 2, \ldots, 9\} have a sum divisible by 33? (The empty set counts, with sum 00.)

    Quantos subconjuntos de {1,2,…,9}\{1, 2, \ldots, 9\} têm soma divisível por 33? (O conjunto vazio conta, com soma 00.)

    Answer options

    Solution

    Step 1 of 3

    1. 1.Use the roots of unity filter on f(x)=∏k=19(1+xk)f(x) = \prod_{k=1}^{9}(1 + x^{k}), with ω\omega a primitive cube root of unity.