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(52776)  (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
|
|
|
