Wicked Subsets: Avoiding Three Consecutive Integers

Hey math enthusiasts, let's dive into a super cool problem from the British Mathematical Olympiad 2003-2004! We're going to explore how to count subsets of the set $S = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$ that have a special property: they are "wicked." What does wicked mean in this context, you ask? It means that within these subsets, we can't find any three numbers that are consecutive. So, if you pick a subset, you won't find, say, {3, 4, 5} or {7, 8, 9} lurking in there. This problem is a fantastic workout for our combinatorics and recursion skills, so buckle up!

Understanding the "Wicked" Condition

Alright guys, let's get our heads around this "wicked" condition. We're dealing with subsets of the set $S = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$. The total number of subsets for a set with 10 elements is $2^{10}$, which is 1024. That's a lot of subsets to check manually! We need a smarter approach. The key constraint is that no three consecutive integers can be present in a subset. This means if we have a subset, we can't have $k, k+1, k+2$ for any $k$. For example, {1, 3, 5, 7} is a wicked subset because there are no three consecutive numbers. But {1, 2, 3, 5} is not wicked because it contains 1, 2, and 3. Similarly, {5, 6, 7, 9} is not wicked because of 5, 6, and 7. Our mission is to count all such wicked subsets. This type of problem often involves breaking it down into smaller, manageable parts and looking for patterns, which is where recursion usually comes in handy. We'll be building up our count by considering elements one by one or in small groups, ensuring we don't violate the wicked rule at each step. It's like building a LEGO castle, but you have to be careful not to place bricks in a way that makes the whole thing unstable – in our case, unstable means having three consecutive numbers.

Breaking Down the Problem with Recursion

So, how do we tackle this systematically? Recursion is our best friend here. Let's define a function, say $W(n)$, which represents the number of wicked subsets of the set {1, 2, ..., $n\}$. Our goal is to find $W(10)$.

To figure out $W(n)$, we can think about the last element, $n$. When we form a wicked subset of {1, 2, ..., $n\}$, there are two main cases concerning the element $n$:

Case 1: The subset does not contain $n$.

If a wicked subset doesn't contain $n$, then it must be a wicked subset of {1, 2, ..., $n-1\}$. The number of such subsets is simply $W(n-1)$. This part is straightforward, right? We're just ignoring the last element and focusing on the smaller set.

Case 2: The subset does contain $n$.

This is where things get a bit more interesting. If a wicked subset contains $n$, we need to consider the elements $n-1$ and $n-2$. To ensure the subset remains wicked, we cannot have both $n-1$ and $n-2$ in the subset along with $n$. This gives us a few sub-cases:

• Sub-case 2a: The subset contains $n$, but not $n-1$. If $n$ is in the subset and $n-1$ is not, then the remaining elements must form a wicked subset of {1, 2, ..., $n-2\}$. The number of such subsets is $W(n-2)$. Why $n-2$? Because we've already decided to include $n$ and exclude $n-1$, so the elements we can pick from are up to $n-2$, and they must also form a wicked set. We don't need to worry about $n-1$ or $n-2$ being consecutive with $n$ because $n-1$ is explicitly excluded.

• Sub-case 2b: The subset contains $n$ and $n-1$, but not $n-2$. If $n$ and $n-1$ are in the subset, we absolutely cannot include $n-2$. So, the remaining elements must form a wicked subset of {1, 2, ..., $n-3\}$. The number of such subsets is $W(n-3)$. Here, we've included $n$ and $n-1$, and we must exclude $n-2$. Thus, the other elements we can choose come from the set {1, 2, ..., $n-3\}$ and must form a wicked subset.

Combining these cases, we get a recurrence relation:

W(n) = W(n-1) \text{ (subsets not containing } n\) + W(n-2) \text{ (subsets containing } n \text{ but not } n-1\) + W(n-3) \text{ (subsets containing } n \text{ and } n-1 \text{ but not } n-2\)

This looks like a variation of the Fibonacci sequence, but with three terms! Now, we need the base cases to get this recursion rolling.

Calculating the Base Cases

To use our recurrence relation $W(n) = W(n-1) + W(n-2) + W(n-3)$, we need to establish the values for $W(0)$, $W(1)$, and $W(2)$. Let's figure these out.

• For $n=0$ (the empty set {}}): The only subset is the empty set itself, {}. The empty set has no elements, let alone three consecutive ones. So, it is definitely wicked. Thus, $W(0) = 1$. This might seem a bit abstract, but it's crucial for the recursion to work correctly. Think of it as the starting point for building our valid subsets.

• For $n=1$ (the set {1}): The subsets are {} and {1}. Both are wicked. So, $W(1) = 2$.

• For $n=2$ (the set {1, 2}): The subsets are {}, {1}, {2}, and {1, 2}. None of these contain three consecutive numbers. So, $W(2) = 4$.

Let's check if our recurrence holds for $n=3$ using these base cases. The set is {1, 2, 3}. The subsets are: {} {1}, {2}, {3} {1, 2}, {1, 3}, {2, 3} {1, 2, 3} (This one is not wicked!)

So, there are 7 wicked subsets for $n=3$. Let's see what our formula gives: $W(3) = W(2) + W(1) + W(0) = 4 + 2 + 1 = 7$. Perfect! Our recurrence relation seems to be working like a charm. This gives us confidence to proceed with calculating $W(10)$.

Calculating $W(10)$ Step-by-Step

Now that we have our base cases and our recurrence relation, let's compute the values of $W(n)$ up to $n=10$. Get ready for some number crunching, guys!

• $W(0) = 1$

• $W(1) = 2$

• $W(2) = 4$

• $W(3) = W(2) + W(1) + W(0) = 4 + 2 + 1 = 7$

• $W(4) = W(3) + W(2) + W(1) = 7 + 4 + 2 = 13$ Let's sanity check $W(4)$ for the set {1, 2, 3, 4}. The wicked subsets are: {}, {1}, {2}, {3}, {4} {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4} {1,3} (no, wait, {1,3} is fine), {1,4}, {2,4} {1,2,4}, {1,3,4} (no, {1,3,4} is fine), {2,3,4} (NOT wicked) Let's list them systematically: Size 0: {} (1) Size 1: {1}, {2}, {3}, {4} (4) Size 2: {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4} (6) Size 3: {1,2,4}, {1,3,4} (2) Size 4: None. Total: $1 + 4 + 6 + 2 = 13$. Yep, $W(4)=13$ is correct!

• $W(5) = W(4) + W(3) + W(2) = 13 + 7 + 4 = 24$

• $W(6) = W(5) + W(4) + W(3) = 24 + 13 + 7 = 44$

• $W(7) = W(6) + W(5) + W(4) = 44 + 24 + 13 = 81$

• $W(8) = W(7) + W(6) + W(5) = 81 + 44 + 24 = 149$

• $W(9) = W(8) + W(7) + W(6) = 149 + 81 + 44 = 274$

• $W(10) = W(9) + W(8) + W(7) = 274 + 149 + 81 = 504$

So, after all that calculation, the number of wicked subsets of {1, 2, 3, ..., 10} is 504!

Alternative Perspective: Using States

While the recurrence relation is solid, sometimes it's helpful to think about this problem using states. Imagine we are building a subset by deciding whether to include each number from 1 to 10. At any point, the crucial information we need to carry forward is whether the last two numbers we included were consecutive. This is because if we are considering adding the number $k$, and we included $k-1$ and $k-2$, then we cannot include $k$.

Let's define three types of wicked subsets ending at position $n$ (meaning they are subsets of {1, 2, ..., $n$})

1. Type 0: Subsets that do not contain $n$. Let $a_n$ be the count of such subsets.
2. Type 1: Subsets that contain $n$ but not $n-1$. Let $b_n$ be the count of such subsets.
3. Type 2: Subsets that contain $n$ and $n-1$, but not $n-2$. Let $c_n$ be the count of such subsets.

The total number of wicked subsets of {1, 2, ..., $n$} would be $W(n) = a_n + b_n + c_n$. Now let's see how these counts evolve.

• To get a Type 0 subset ending at $n$ (i.e., not containing $n$): We could have had any type of wicked subset ending at $n-1$ (Type 0, Type 1, or Type 2). So, $a_n = a_{n-1} + b_{n-1} + c_{n-1} = W(n-1)$.

• To get a Type 1 subset ending at $n$ (i.e., containing $n$ but not $n-1$): We must not have included $n-1$. This means the subset ending at $n-1$ must not have contained $n-1$. This means it must have been a Type 0 subset ending at $n-1$. So, $b_n = a_{n-1}$.

• To get a Type 2 subset ending at $n$ (i.e., containing $n$ and $n-1$, but not $n-2$): We must have included $n$ and $n-1$. For this to be valid, the subset ending at $n-1$ must have contained $n-1$ but not $n-2$. This means it must have been a Type 1 subset ending at $n-1$. So, $c_n = b_{n-1}$.

Let's try to set up the base cases for this state-based approach.

For $n=1$ (set {1}):

• $a_1$: Subsets not containing 1. Only {}. So $a_1 = 1$.
• $b_1$: Subsets containing 1 but not 0 (doesn't apply). This state formulation needs careful handling at the edges. A simpler way is to define the states based on the last element included.

Let's redefine the states slightly for clarity:

Let $f(n)$ be the number of wicked subsets of {1, ..., $n$}. Let $g(n)$ be the number of wicked subsets of {1, ..., $n$} that do not contain $n$. Let $h(n)$ be the number of wicked subsets of {1, ..., $n$} that do contain $n$.

Clearly, $f(n) = g(n) + h(n)$.

Now, consider $g(n)$. If a wicked subset of {1, ..., $n$} does not contain $n$, it must be a wicked subset of {1, ..., $n-1$}. So, $g(n) = f(n-1)$.

Now, consider $h(n)$. If a wicked subset of {1, ..., $n$} does contain $n$, we need to be careful. The preceding elements must form a wicked subset of {1, ..., $n-1$}, with the additional constraint that we cannot have $n-1$ and $n-2$ both present if $n$ is present.

This state definition seems tricky. Let's go back to the first recurrence, which proved effective.

$W(n) = W(n-1) + W(n-2) + W(n-3)$

• $W(n-1)$: Wicked subsets of {1, ..., $n-1$}. These are subsets of {1, ..., $n$} that do not contain $n$.
• $W(n-2)$: Wicked subsets of {1, ..., $n-2$}. If we add $n$ to these, we get wicked subsets of {1, ..., $n$} containing $n$ but not $n-1$.
• $W(n-3)$: Wicked subsets of {1, ..., $n-3$}. If we add $n$ and $n-1$ to these, we get wicked subsets of {1, ..., $n$} containing $n$ and $n-1$ but not $n-2$.

This decomposition correctly covers all possibilities without overlap:

1. Subsets not containing $n$ (these are exactly the wicked subsets of {1, ..., $n-1$}).
2. Subsets containing $n$ but not $n-1$ (these are formed by taking wicked subsets of {1, ..., $n-2$} and adding $n$).
3. Subsets containing $n$ and $n-1$ but not $n-2$ (these are formed by taking wicked subsets of {1, ..., $n-3$} and adding $n$ and $n-1$).

Any wicked subset of {1, ..., $n$} must fall into one of these three categories:

• It doesn't contain $n$.
• It contains $n$ but not $n-1$.
• It contains $n$ and $n-1$ (and thus, by the wicked rule, cannot contain $n-2$).

The sum $W(n-1) + W(n-2) + W(n-3)$ correctly enumerates these distinct cases. The calculation we performed using this recurrence relation is sound.

Conclusion: The Final Count

We embarked on a quest to find the number of "wicked" subsets of the set $S = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$, where "wicked" means the subset contains no three consecutive integers. By establishing a recurrence relation $W(n) = W(n-1) + W(n-2) + W(n-3)$ with base cases $W(0)=1$, $W(1)=2$, and $W(2)=4$, we systematically calculated the values.

The sequence unfolds as:

• $W(0) = 1$
• $W(1) = 2$
• $W(2) = 4$
• $W(3) = 7$
• $W(4) = 13$
• $W(5) = 24$
• $W(6) = 44$
• $W(7) = 81$
• $W(8) = 149$
• $W(9) = 274$
• $W(10) = 504$

Therefore, there are 504 wicked subsets of the set {1, 2, 3, ..., 10}. This problem beautifully illustrates the power of recursion in combinatorics, breaking down a complex counting problem into smaller, manageable steps. It's a classic example found in contest math that really makes you think about how to construct valid sets based on specific rules. Keep practicing these kinds of problems, guys, and you'll become a combinatorics whiz in no time!