Count of Sparse Subsets - Duke Math Meet 2009 Problem 6

Try this problem from Duke Math Meet 2009 Problem 6 based on Count of Sparse Subsets. This problem was asked in the team round.

Call a set S sparse if every pair of distinct elements of S differ by more than 1. Find the number of sparse subsets (possibly empty) of {1, 2, . . . , 10}.

Suppose there are k elements in the sparse subsets. We put them in increasing order. Since any two elements differ by at least 2, we have $ a_2 \ge a_1 + 2 , a_3 \ge a_2 + 2 \ge a_1 + 4 , ... , a_5 \ge a_1 + 8 $ Hence there are at most 5 elements in the set.

To count the number of sparse sets we use the following strategy: look at the gaps

for example if there 4 elements in the subsets, after putting them in increasing order, we look at the gaps between the elements. There are 5 such gaps: $ g_1 = a_1 - 1, g_2 = a_2 - a_1 - 1 ... g_5 = 10 - a_4 $. These 5 gaps must account for the remaining 6 elements and the least value of the middle three gaps is 1.

Let $ g_2' = g_2 + 1 , g_3' =g_3 + 1 , g_4' = g_4+1 $

Thus we are looking for the number of non negative integer solutions of $ g_1 + g_2' + g_3' + g_4' + g_5 = 3 $. This is given by $latex \binom{7}{3} = 35 $

Similarly 5 element sparse sets we look at $ g_1 + g_2' + g_3' + g_4' + g_5' + g_6 = 1 $ This is given by $latex \binom{6}{1} = 6 $

Similarly for 3-element subsets we look at $ g_1 + g_2' + g_3' + g_4 = 5 $ . This is given by $latex \binom{8}{3} = 56 $

Similarly for 2-element subsets we look at $ g_1 + g_2' + g_3 = 7$ . This is given by $latex \binom{9}{2} = 36 $

Finally there are 10 single element sub set and 1 null set all of which are sparse.

Why?

Consider the statement:

'If there are two elements then they differ by at least 2.'

The above is an implication statement and it is true for singleton or null sets as 'if there are two elements' part of the statement is false (an implication statement becomes true if antecedent becomes false).

Hence the total number of sparse sets: 6 + 35 + 56 + 36 + 10 + 1 = 144

Some Useful Links:

• Duke Math Meet 2009 Problem 9
• Our Math Olympiad Program
• AM-GM Inequality – Video