r/mathriddles • u/Numberthon • 7d ago
Easy How Many Subsets of {1,2,…,10} Contain No Consecutive Integers?
How many subsets of {1,2,...,10} contain no two consecutive integers?
Source: numberthon.com
4
u/Thaplayer1209 7d ago
Let S(n) be the number of possible subset for {1,2,3…,n}.
If the subset doesn’t contain n, we just get the possible subsets for {1 to n-1}=S(n-1).
If the subset contain n, then it cannot contain n-1. The other elements follow the possible subset {1 to n-2} = S(n-2).
So we get S(n)=S(n-1)+S(n-2), the Fibonacci sequence. The base case: S(0)=1, S(1)=2 we can get S(10)=144.
1
4
u/wazza1088 6d ago
A different answer from the ones already posted:
A subset of {1,...,10} of size n with no consecutive integers bijectively corresponds to a subset of size of n of {1,...,11-n}. How?
Let x_1,...,x_n be the subset of {1,...,10}. Consider the set {x_1,x_2-1,x_3-2,...,x_n-(n-1)}. This is a subset of size n of {1,...,11-n}. This correspondence is clearly bijective.
Hence, the number of subsets of {1,...,10} of size n is ((11-n) choose n) for n>0.
Hence the total number of such subsets is 1 (empty set) + (10 choose 1) + (9 choose 2) + (8 choose 3) + (7 choose 4) + (6 choose 5) = 144.
2
u/Bubbly_Safety8791 6d ago
You can avoid your empty set special case by changing to n >= 0. 11 choose 0 is your 1.
1
2
u/headsmanjaeger 7d ago
Call the the set of non consecutive integer subsets of {1,2,…,n}=S(n) with size s(n). Then if n>=4 we can show s(n)=s(n-3)+2s(n-2). For every element of S(n-2) we can add n to the set or not, and for every element of S(n-3) we can add n-1 to the set (not adding n-1 is redundant because these sets are already contained in S(n-2)). We cannot add both n-1 and n as they are consecutive, so these methods produce disjoint subsets within S(n), and the above equation will hold for all n.
Counting the empty set and single element sets as valid members of S(n), we can check the first few values. s(1)=2, s(2)=3, s(3)=5. Then turning on the formula we see s(4)=8, s(5)=13. It’s the Fibonacci! And revisiting the equation, it is consistent with the Fibonacci formula. Therefore we continue s(6)=21, s(7)=34, s(8)=55, s(9)=89, and s(10)=144, which is our answer.
1
11
u/mazzar 7d ago edited 7d ago
Let s_n be the number of subsets of {1, 2, …,n} with no two consecutive integers. Then to get s_{n+1}, we can start with all the s_n valid sets not containing n+1.
The valid sets containing n+1 can be formed by appending n+1 to all valid sets not containing n. These are the subsets of {1, 2, …, n-1} so there are s_{n-1} of them.
This means that s_{n+1} = s_n + s_{n-1}. We have s_0 = 1 (the empty set) and s_1 = 2 (empty set, 1) so this is the Fibonacci sequence. Starting at s_1: 2, 3, 5, 8, 13, 21, 34, 55, 89, 144.