British Maths Olympiad (BMO) 2003 Round 1 Question 4 what is wrong with this approach, can it be fixed?

The questions states:

A set of positive integers is defined to be $wicked$ if it contains no three consecutive integers. We count the empty set, which contains no elements at all, as a $wicked$ set. Find the number of wicked subsets of the set

{$1, 2, 3, 4, 5, 6, 7, 8, 9, 10$}

One approach is to subtract all the sets that are not wicked from all possible sets

We have $2^{10}$ possible sets

The sets that are not $wicked$ must contain some combination of the following consecutive integers:

{1,2,3} $\\$ {2,3,4} $\\$ {3,4,5} $\\$ {4,5,6} $\\$ {5,6,7} $\\$ {6,7,8} $\\$ {7,8,9} $\\$ {8,9,10}

We could partition all the subsets in the following way

$(1,2,3)$ $\times$ {$4,5,6,7,8,9,10$} $= 2^7$ sets which contain (1,2,3)

$(2,3,4)$ $\times$ {$5,6,7,8,9,10$} $= 2^6$ sets which contain (2,3,4)

$(3,4,5)$ $\times$ {$6,7,8,9,10$} $= 2^5$ ...

notice that we purposefully leave out prior numbers so that we are considering disjoint sets.

We thus get $2^7 +2^6 \cdots + 2^0 = 2^8 - 1$ sets that are not $wicked$.

Thus the number of $wicked$ sets is $2^{10} - (2^8 - 1)$

What is wrong with this approach, and can it be fixed to give the right answer?

• What is the place of the non-wicked set $\{1,3,4,5\}$ in your classification? – Chen Wang May 12 '18 at 0:16
• To fix, need I/E. – vadim123 May 12 '18 at 0:19

There are two good ways to do this problem.

1. Let $a_n$ be the number of wicked subsets of $\{1,2,\dots,n\}$. You can show that $$a_n=a_{n-1}+a_{n-2}+a_{n-3}$$ holds for all $n\ge 3$. The $a_{n-1}$ term counts subsets where $n$ is absent, $a_{n-2}$ counts subsets where $n$ is present but $n-2$ is absent, and $a_{n-3}$ is subsets with $n$ and $n-1$ but without $n-2$.
This recurrence, along with the bases cases $a_0=1,a_1=2,a_2=4$, allows you to iteratively compute $a_n$ from the ground up, starting with $a_3$ all the way up to $n=10$.

2. Instead, count the number of un-wicked (saintly) subsets. Thinking of subsets as strings of ten $0$s and $1$s, where $1$s correspond to the elements in the set, every saintly subset contains a $111$ somewhere. To eliminate the problem of overlaps, in any block of three or more ones, we will only consider the initial $111$, which corresponds to either a $111$ at the beginning or a $0111$ somewhere.

There are $2^7$ strings starting with $111$, and $7\cdot 2^6$ strings containing a $0111$ (the $7$ represents the choice of location of $0111$). Well, not quite; there is some double counting happening here. You then need to subtract out the strings which contain two instances of either $\_111$ or $0111$ (where $\_$ is the beginning of the string). Fortunately, there is no triple counting, so after subtracting the double counted strings you are done.

Subtracting the number of saintly sets from the total, the final result is $$2^{10}-2^7-\binom71\cdot 2^6+\binom{4}{1}2^3+\binom{4}22^2.$$The term $\binom{5}{2}2^3$ represents strings containing a $111$ at the start and a $0111$ elsewhere, while the last terms is strings containing two instances of $0111$.

• In the second method, the last term should have a minus sign in front. – sku May 12 '18 at 6:33
• @sku I think it should be plus: what I have written is all $2^{10}$ strings, minus the bad strings containing $111$, plus the strings containing $111$ twice, which is how inclusion exclusion exclusion works. Plus, both methods give the same answer of 504 (after I fixed an unrelated error). – Mike Earnest May 12 '18 at 18:58
• Fine now. The final answer is $504$ – sku May 12 '18 at 20:25