MAS114: Challenge Problem 1

Problem

How many subsets are there of \(\{1,2,3,\ldots,19,20\}\) which contain no two consecutive elements? (For example, \(\{1,4,18\}\) is okay, but \(\{1,4,17,18\}\) is not okay since it contains the consecutives \(17\) and \(18\).)

I received many entries! So many that I can only discuss the fully correct ones.

Solution 1

The union of Emily Briscoe and Adam "John" Hughes determined that the relevant number is \[\binom{20}{1} + \binom{19}{2} + \cdots + \binom{12}{9} + \binom{11}{10} = 17710,\] and gave an argument why.

Their argument boils down to saying that \(\binom{n+1-r}{r}\) is the number of \(r\)-element subsets of \(1,\ldots,n\) without any consecutives, because every time you choose an element after the first one, you have lost the chance to choose the element immediately to its right: so (for example) choosing three out of twenty without consecutives is like choosing three out of eighteen.

After adding up all the subsets of each size, you get the formula they gave. One should probably also add on the extra binomial coefficient \(\binom{21}{0}=1\) corresponding to the empty subset.

Their argument can be made into a bijection between subsets of \(1,\ldots,n+1-r\) of size \(r\), and subsets of \(1,\ldots,n\) of size \(r\) with no consecutives. Can anyone see how?

Solution 2

There is, however, a solution that involves a little less work (no calculating enormous binomial coefficients, for example). This is what Benjamin Andrews and Mohammad Tayyab Sajjad did, and also close to what Oliver Feghali was doing. I'll write up the former solution (Mohammad's was similar).

Once we know the number of valid subsets of \(\{1,2,3,\ldots,n\}\), how do we work out how many valid subsets of \(\{1,2,3,\ldots,n,n+1\}\) there are?

Some of the valid subsets of \(\{1,2,3,\ldots,n\}\) contain n. All of these would still be valid for \(\{1,2,3,\ldots,n,n+1\}\). Some of the valid subsets of \(\{1,2,3,\ldots,n\}\) do not contain n (these are the subsets of \(\{1,2,3,\ldots,n-1\}\). These are also valid for \(\{1,2,3,\ldots,n,n+1\}\) by including n+1. (They are also valid if n+1 is not included, but these were also subsets of \(\{1,2,3,\ldots,n\}\) so they have already been counted).

This means that to work out the number of valid subsets of \(\{1,2,3,\ldots,n,n+1\}\) you add up the number of valid subsets of \(\{1,2,3,\ldots,n\}\) and \(\{1,2,3,\ldots,n-1\}\), which is where the Fibonacci sequence appears from.

For clarity, here’s an example. Once you know the number of valid subsets of \(\{1,2,3,4\}\), here’s how to count them for \(\{1,2,3,4,5\}\).

Count all the ones for \(\{1,2,3,4\}\) containing a 4. These are still valid.

Count also the ones for \(\{1,2,3\}\) with 5 added into the set. These are valid, and were not in the subsets of \(\{1,2,3,4\}\) as they did not have 5 in them.

From this we can see that the answer is the number of valid subsets from \(\{1,2,3,4\}\) added to the number from \(\{1,2,3\}\).

So for \(n=20\), the answer is the 20th term after the second 1 in the Fibonacci sequence: \[2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711\]

There are 17,711 subsets of \(\{1,2,3,\ldots,19,20\}\) with no consecutive elements in them.