Did I post in the wrong category? If so can you please advise on the correct category to post to?READ BEFORE POSTING
Welcome to FreeMathHelp.com! Please take the time to read the following before you make your first post. It will help you to get your math questions answered promptly and in the most helpful manner. A summary is available here, but please read the complete guidelines below at your earliest...www.freemathhelp.com
If you "read before posting", you would know that this is not how the site works. Rather, we want you to explain (partially) how you did not arrive at the answer, so we can tell where you need help.Please also explain fully how you arrived at the answer.
I would approach this by first thinking carefully about what it means. I think it means that there can be one pair of two consecutive integers, but no more, so that {1, 3, 19} and {1, 2, 19} are included, but not {1, 2, 3, 19} or {1, 2, 18, 19}, for example. Is that how you interpret it?how many subsets of {1, 2, 3, …, 20} are there with no more than 2 consecutive integers?
Right, I interpreted the problem the same way where (1, 2, 5) would be a proper subset and (1, 2, 3) would not be. my main issue at this point is figuring out a formula or process to incorporate this into solving the problem. Do you have any idea how to specifically go about solving the equation,, besides simply creating a smaller container set, as I would still not know the best way to go about solving the problem?If you "read before posting", you would know that this is not how the site works. Rather, we want you to explain (partially) how you did not arrive at the answer, so we can tell where you need help.
I would approach this by first thinking carefully about what it means. I think it means that there can be one pair of two consecutive integers, but no more, so that {1, 3, 19} and {1, 2, 19} are included, but not {1, 2, 3, 19} or {1, 2, 18, 19}, for example. Is that how you interpret it?
Then, if I didn't see a good way to create all such subsets, I might try actually listing them for a smaller containing set, like {1, 2, 3, 4, 5}, in order to better understand how it works, and to be able to try out methods and see if they missed or double-counted anything.
But when you tell us what you have tried, and any special methods you've been learning, we may have more to suggest.
I think you are using "proper subset" not with its proper definition, but to mean "the kind of subset you are to count".Right, I interpreted the problem the same way where (1, 2, 5) would be a proper subset and (1, 2, 3) would not be. my main issue at this point is figuring out a formula or process to incorporate this into solving the problem. Do you have any idea how to specifically go about solving the equation,, besides simply creating a smaller container set, as I would still not know the best way to go about solving the problem?
Please advise your friend to communicate with this forum directly and share "friendly" work on this problem......a question my friend asked me and needs help with
Then pass on our requests to your friend, if he is unable to connect with us himself. We need his context, such as what he is studying, in order to know what sort of suggestions to make. Don't imagine that you, knowing nothing of the subject, could teach someone else just by having seen an answer. (I can too easily imagine someone, hopefully not you, saying what you do as an excuse to get us to give a complete solution for his own test problem.)unfortunately, I am new to subset problem solving and interpretation. this isn't something I was taught but rather a question my friend asked me and needs help with, which is why I wanted to rationalize a relatively clear cut solution to him to arrive at the answer and to be able to explain to him the process.
I made it clear that I had not done much work; my words "I don't want to be tempted to tell you all about a great method I discover" (not "have discovered) refer to the possible future, not the past or present!If you really have discovered a great way to solve the problem then I would greatly appreciate it if you could show me that method and application.
If we take only the odd numbers in that set [imath]\mathcal{O}=\{1,3,5,\cdots,17,19\}[/imath] there [imath]2^{10}-1[/imath] non-empty subsets with no two consecutive integers. Likewise if we take only the even numbers in that set [imath]\mathcal{E}=\{2,4,6\cdots,18,20\}[/imath] there are [imath]2^{10}-1[/imath] non-empty subsets with no two consecutive integers.unfortunately, I am new to subset problem solving and interpretation. this isn't something I was taught but rather a question my friend asked me and needs help with, which is why I wanted to rationalize a relatively clear cut solution to him to arrive at the answer and to be able to explain to him the process. If you really have discovered a great way to solve the problem then I would greatly appreciate it if you could show me that method and application.how many subsets of {1, 2, 3, …, 20} are there with no more than 2 consecutive integers? Please also explain fully how you arrived at the answer.
Just for everyone's information, I have now solved it (I think!) using these ideas; the answer I got is related to the Fibonacci sequence, which suggests that something like my approach may be what's expected, not what you'd normally think of as combinatorics in the restricted sense. On the other hand, Fibonacci can be expressed in terms of combinations!This will be most useful to someone who knows about recursive sequences or inductive proof. I think the other case will require just a small modification.
Working on the "no consecutive pairs" case, and making a list of values for S_n for small n, where S_n means the number of subsets of a set of n numbers with no consecutive pairs) reveals a nice pattern and a possible proof. This will be most useful to someone who knows about recursive sequences or inductive proof. I think the other case will require just a small modification.
n f(n)
--------
1 1
2 2
3 4
4 7
5 12
6 20
7 33
8 54
9 88
10 143
1 1
2 3
3 6
4 12
5 22
6 40
7 71
8 125
9 218
10 378
Are you not counting the empty set in your f(n)?A different thread concerning recursion reminded me of this problem. And since this thread is over a month old now then we can more openly discuss the answer.
For the "no consecutive pairs" case I found a Fibonacci like recursive formula f(n) that gives...
Code:n f(n) -------- 1 1 2 2 3 4 4 7 5 12 6 20 7 33 8 54 9 88 10 143
For the case of, "no more than 2 consecutive integers" in the original question it's possible to use a summation over all the possible consecutive pairs - using f(x) to determine the combinations both lower and higher. Add to this the result for no consecutive pairs f(n) and I obtain...
@Dr.Peterson was this the method that you used, or did you find a recursive relation for this too? (Perhaps you don't remember because it was a long time ago)Code:1 1 2 3 3 6 4 12 5 22 6 40 7 71 8 125 9 218 10 378
I haven't given my solution, nor the answer for n=20, just in case anyone else would like to look into this problem as a puzzle.
For no consecutive integers, I get:
n=0, subsets of {}: {}, so [imath]S_0=1[/imath]
n=1, subsets of {1}: {}, {1} so [imath]S_1=2[/imath]
n=2, subsets of {1,2}: {}, {1}, {2} so [imath]S_2=3[/imath]
n=3, subsets of {1,2,3}: {}, {1}, {2}, {3}, {1,3} so [imath]S_3=5[/imath]
n=4, subsets of {1,2,3,4}: {}, {1}, {2}, {3}, {4}, {1,3}, {1,4}, {2,4} so [imath]S_4= 8[/imath]
For a given n, we can use any of the subsets in [imath]S_{n-1}[/imath], together with any of the subsets is [imath]S_{n-2}[/imath] together with n. For example, the subsets for n=4 are {}, {1}, {2}, {3}, {1,3} together with {4}, {1,4}, {2,4}. So the recursion is [imath]S_{n} = S_{n-1} + S_{n-2}[/imath], and is the Fibonacci sequence, offset.
If you don't count empty subsets, then your answer is correct (1 less than Fibonacci).
I haven't found notes from my original work, so I have to think about it again (I haven't had much time yet). I've got a candidate that doesn't involve a summation, but need to check and improve it.
n | S | T | U |
0 | 1 | 0 | 1 |
1 | 2 | 0 | 2 |
2 | 3 | 1 | 4 |
3 | 5 | 2 | 7 |
4 | 8 | 5 | 13 |
5 | 13 | 10 | 23 |
6 | 21 | 20 | 41 |
7 | 34 | 38 | 72 |
8 | 55 | 71 | 126 |
9 | 89 | 130 | 219 |
10 | 144 | 235 | 379 |