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

    How many subsets of {1,2,…,10}\{1, 2, \ldots, 10\} contain no two consecutive integers? (The empty set counts.)

    Quantos subconjuntos de {1,2,…,10}\{1, 2, \ldots, 10\} não contêm dois inteiros consecutivos? (O conjunto vazio conta.)

    Answer options

    Solution

    Step 1 of 3

    1. 1.A subset of size kk with no two consecutive elements corresponds to a choice of kk items from 11−k11 - k, so there are (11−kk)\binom{11-k}{k} of them.