SOLUTION: Let S be the set {1, 2, 3, \dots, 10, 11, 12}. How many subsets of the set S have no two consecutive primes as members?
Algebra.Com
Question 1209831: Let S be the set {1, 2, 3, \dots, 10, 11, 12}. How many subsets of the set S have no two consecutive primes as members?
Found 2 solutions by CPhill, ikleyn:
Answer by CPhill(1959) (Show Source): You can put this solution on YOUR website!
Let S={1,2,3,…,12}.
The primes in S are P={2,3,5,7,11}.
We want to find the number of subsets of S such that no two consecutive primes are members.
Let's consider the primes in S. We want to choose a subset of P such that no two consecutive primes are chosen. Let a
n
be the number of subsets of {p
1
,p
2
,…,p
n
} with no consecutive primes, where p
i
is the i-th prime.
For n=0, a
0
=1 (empty set).
For n=1, a
1
=2 (empty set, {p
1
}).
For n=2, a
2
=3 (empty set, {p
1
}, {p
2
}).
For n=3, a
3
=5 (empty set, {p
1
}, {p
2
}, {p
3
}, {p
1
,p
3
}).
For n=4, a
4
=8 (empty set, {p
1
}, {p
2
}, {p
3
}, {p
4
}, {p
1
,p
3
}, {p
1
,p
4
}, {p
2
,p
4
}).
For n=5, a
5
=13 (empty set, {p
1
}, {p
2
}, {p
3
}, {p
4
}, {p
5
}, {p
1
,p
3
}, {p
1
,p
4
}, {p
1
,p
5
}, {p
2
,p
4
}, {p
2
,p
5
}, {p
3
,p
5
}, {p
1
,p
3
,p
5
}).
We observe that a
n
=F
n+2
, where F
n
is the n-th Fibonacci number (F
0
=0,F
1
=1,F
2
=1,F
3
=2,F
4
=3,F
5
=5,…).
Thus, the number of subsets of P with no consecutive primes is a
5
=F
7
=13.
Now consider the non-prime numbers in S: N={1,4,6,8,9,10,12}.
The number of subsets of N is 2
7
=128.
Each subset of N can be combined with any subset of P that has no consecutive primes.
Thus, the total number of subsets of S with no consecutive primes is 13×128=1664.
Final Answer: The final answer is
1664
Answer by ikleyn(52781) (Show Source): You can put this solution on YOUR website!
.
It looks like @CPhill created/invented a new way presenting solutions
to Math problems: - - - making it in an UNREADABLE format.
To all other visitors and readers of his posts, I recommend ignore them
and read directly from the Google AI source.
Concretely for this given problem, you may read the solution in traditional format from this link
https://www.google.com/search?q=Let+S+be+the+set+%7B1%2C+2%2C+3%2C+...+%2C+10%2C+11%2C+12%7D.+How+many+subsets+of+the+set+S+have+no+two+consecutive+primes+as+members%3F&rlz=1C1CHBF_enUS1071US1071&oq=Let+S+be+the+set+%7B1%2C+2%2C+3%2C+...+%2C+10%2C+11%2C+12%7D.++How+many+subsets+of+the+set+S+have+no+two+consecutive+primes+as+members%3F&gs_lcrp=EgZjaHJvbWUyBggAEEUYOdIBCjE5MjYyajBqMTWoAgiwAgHxBXPVsR37pL67&sourceid=chrome&ie=UTF-8
RELATED QUESTIONS
Let S be the universal set, where: -
S={1,2,3,...,18,19,20}
Let sets A and B be... (answered by ikleyn)
Let S be the universal set, where:
S={1,2,3,...,18,19,20)
Let sets A and B be subsets... (answered by ikleyn)
Let
S={1,2,3,...,18,19,20} be the universal set.
Let sets A and B be subsets of S, (answered by Boreal,ikleyn)
Let S be the universal set, where: S = {1,2,3,...,28,29,30}
Let sets A and B be subsets... (answered by MathLover1,ikleyn)
Let S = {1,2,3,...,18,19,20} be the universal set.
Let sets A and B be subsets of S,... (answered by Solver92311)
Let A = {1, 2, 3, 4, 5, 6}.
(a) How many subsets of 4 elements does the set A have?... (answered by ikleyn)
Assume that the set S has 13 elements.
How many subsets of S have at most 3... (answered by Edwin McCravy)
Let S={1,2,3,4,…,n}, and let A and B be two subsets of S such that A ≠ ∅, B ≠ S,... (answered by ikleyn)
Let S={1,2,3,4,5,6,7,8,9,10} be the universal set.
Let sets A, B, and C be subsets of... (answered by math_tutor2020)