Subset problem

SeventhSigma

not so much. I am trying to use a smaller set of S to see if I can count them properly. I am not sure that approach works because it's easier to count the extremities than it is to count the nitty gritty stuff towards the center of S where stuff gets messier

haruspex

I'm puzzled there's been no response to my post (#31).
Isn't it the answer to the originally posed question? Do I need to explain more?

ClifDavis

As you note, you are answering the original question for {1,2,3,...,n} whereas what he actually needs is an answer to the simpler question for {a(1),a(2),a(3),....a(n)} which generally looks like {1,2,3,4,6,9,13,...}.

More importantly your answer is wrong for the question you are answering.

For N=5 you calculate an answer of 9 subsets. But the subsets that fit the criteria are:
{1,2,3,4} 1+2+3+4=13>5
{2,3,4} 2+3+4=9>5
{1,3,4} 1+3+4=8>5
{3,4} 3+4=7>5
{1,2,4} 1+2+4=7>5
{2,4} 2+4=6>5
{1,2,3} 1+2+3=6>5

By my count that makes 7. If you could cough up another two, that would be interesting.

So yes, I think you do need to explain more.

ClifDavis

Well the reason that I initially suggested that you start by checking the number of subsets of S that total to n is that those subsets are the key to counting the qualifying subsets that total to more than n. And finding them points out that you only have to count the extremities in that you only have to count subsets that contain a(n-1) which we've already done, or that don't contain a(n-1) and do contain a(n-2).

At some point you do have to look at the simple sets that don't have enough elements to fit the general case, but until you look at the general case, you don't know how many of the simple cases to look at.

Our basic relationship a(n-3)+a(n-1)=a(n) was the key to counting the number of qualifying subsets that contained a(n-1). To look at those that don't contain a(n-1) we want to get rid of the a(n-1) in our equivalence expression, so we use the known fact from our definition of the a function that a(n-1)=a(n-2)+a(n-4). So we have a(n)=a(n-3)+a(n-1)=a(n-3)+a(n-2)+a(n-4) or to rearrange the terms slightly, we have a(n-4)+a(n-3)+a(n-2)=a(n) and so we have another equivalence where a(n-1) does not occur. This one will be our starting point for counting qualifying subsets where a(n-2) is in the subset.

Now counting the qualifying subsets with a(n-2) as the largest element is something we still have to do. But once we are through we will want to move on to get the next equivalence that doesn't contain a(n-2) either. We know that a(n-2)=a(n-3)+a(n-5) so we can use that to get rid of a(n-2).
So, we have
a(n)=a(n-4)+a(n-3)+a(n-2) and applying the definition of a to a(n-2)
=a(n-4)+a(n-3)+a(n-3)+a(n-5)
=a(n-5)+a(n-4)+a(n-3)+a(n-3) which is okay except we have two a(n-3) but as before
=a(n-5)+a(n-4)+a(n-3)+a(n-4)+a(n-6) we get rid of an a(n-3)
=a(n-6)+a(n-5)+a(n-4)+a(n-4)+a(n-3) but now we have two a(n-4)s so get rid of 1
=a(n-7)+a(n-6)+a(n-5)+a(n-5)+a(n-4)+a(n-3) and now two a(n-5)s...
=a(n-8)+a(n-7)+a(n-6)+a(n-6)+a(n-5)+a(n-4)+a(n-3)

and you see what is happening. Every time we use the definition of the function a to get rid of a duplicate, it creates a new duplicate and it will continue to do so until we extend down to an a(1) term at which point we'll have a duplicate a(3) term. In other words the sum
a(1)+a(2)+a(3)+...+a(n-3)<a(n). If we're doing this right, we should prove that by induction on n. And since the sum of a(1) to a(n-3) is less than n, any qualifying subset must contain a(n-2) or a(n-3) or both. So our sets with extreme values really are all we have to count.

Now there's a still a trick to counting qualifying subsets that have a(n-2) as their largest element, but if you start off counting the sets with a(n-2) as the largest element the same way I did for sets with a(n-1) as the largest element, you will run into it and hopefully see the solution.

haruspex

The original statement is this:
Note: highest number in the subset (not necessarily N).
This was made clearer in post #3:
Necessarily, no subset of 1 or 2 elements can be valid.
The following are the 9 valid for N=5:
2, 3, 4; 2, 4, 5; 3, 4, 5; 1, 2, 3, 4; 1, 2, 3, 5; 1, 2, 4, 5; 1, 3, 4, 5; 2, 3, 4, 5; 1, 2, 3, 4, 5;

There is an easy connection between the two interpretations. If OP(N) is the answer to the original problem and OPN(N) is the answer when the highest term in each subset is required to be N then
OP(N+1) = OP(N) + OPN(N+1)
E.g. OP(4) = 2.

Presumably the same misunderstanding has arisen regarding the a(n) version of the problem; luckily the corresponding relationship applies: AP(N+1) = AP(N) + APN(N+1) where N is the number of elements in the full set.

I agree this version of the problem looks far more amenable.

SeventhSigma

ClifDavis I think we may be talking about different problems. There are possible valid subsets where values aren't from extremities at all, or they may be from all over the place, and so on. You can't just count from extremity cases.

Look at the solution for N=10:

http://pastebin.com/jr6cr7q1

I don't think the approach you are describing emulates the nature of this output. It's looking at a subset and checking the sum of inner elements against the highest element of that subset.

N=10 means S goes up to a(10), or S = [1, 2, 3, 4, 6, 9, 13, 19, 28, 41]
one valid subset might be (1, 6, 13, 19) because 1+6+13 = 20, which is larger than 19.



haruspex: Those solutions aren't right either because your subsets include numbers (namely 5 in this case) that aren't in S.

haruspex

As I said, I believe ClifDavis' interpretation ("APN(N)", where a(N) is the highest in the set) is readily mapped to what you intended ("AP(N)") according to: AP(N+1) = AP(N) + APN(N+1). I.e. AP(N) = sum APN(1) to APN(N).

Quite so - at #31 I was answering the problem as originally posted. I came into the thread just at the point where you added the explanation about a(n) and posted my input without reading that update.

SeventhSigma

I don't think so, because in his earlier analysis he compares subset sums to 5, which is not a valid comparison. You need to compare the highest number of the subset against the sum of the rest of the subset

haruspex

Sorry, you've lost me. Which post is that in? If you mean post #37, that's where ClifD was saying I had the wrong answer to your original question (1, 2... n, rather than a(1), ... a(n)).

ClifDavis

haruspex is quite right. I had gotten the statement of the problem confused from looking at other people's posts and programs rather than yours. Essentially I was showing how to count the new elements for n and not all the elements for n. And I wasn't putting the last term in the subset. Which doesn't effect the count. However it means that my explanation of what I was doing is totally confusing.

To rephrase what he was saying into the notation I was using, if count(n) gives the count for all the qualifying subsets of {a(1),...a(n)} and countnew(n) gives the count of just those qualifying subsets that contain a(n), then count(n)=countnew(n)+count(n-1)

Or conversely countnew(n)=count(n)-count(n-1) which is something that is handy to know.

But what it means is if you have an equation for countnew(n)=stuff then you also have a valid recurrence relationship count(n)=count(n-1)+stuff.

But now that we're on the same page, I'll go back and cover what I was doing for the general case and use smaller arguments for illustration which may make it easier to follow. But not tonight. Time will be tight Sunday and Monday, so it may be Tuesday before I can run through a reasonable explanation, though I'll try to slip it in earlier. If you solve it in the meantime or if haruspex can give you useful clues then it won't matter.

But the important points are still the same. Your a(n)'s are positive and increasing. a(1)+a(2)+a(3)+...a(n-3)<a(n) so any subset to be counted that contains a(n) as the largest element must contain a(n-1) or a(n-2) or both. And if you look at the different subsets containing a(n) as the largest element where the other elements add up to a(n), this will guide you to the different categories of subsets that you can count without having to explicitly create them.

haruspex

Fwiw, I had a go at this simpler problem:
Sn = {A(1), .. , A(n)}, where the A(n) satisfy the recurrence relation A(n) = A(n-1) + A(n-3), etc.
How many subsets of Sn sum to A(n) exactly?
I can't even solve that yet. The problem is that some such subsets cannot be obtained by repeated application of the recurrence relation to break down the target sum. E.g. A(1)+A(2) = A(3). So instead I'll just go for the lower bound which only counts the subsets that can be obtained in this way.

Let T(n,P) = number of subsets that add up to the same as the terms indicated by the bit pattern P, e.g.
P = 1 stands for just the term A(n)
P = 11 stands for A(n-1)+A(n)
P = 101 stands for A(n-2)+A(n)
etc.
T(n,1) = 1 + T(n-1,101)
T(n,101) = T(n-1,111) + T(n-2,1)
T(n,1111) = T(n-1,111) = T(n-2,11)
T(n,11) = T(n-1,1) + T(n-1,1111)
whence
T(n,1) = 1 + T(n-2,111) + T(n-3,1)
T(n,111) = T(n-2,1) + T(n-3,111)
For the general solution we drop the "1+" and try λ[itex]^{n}[/itex].
This yields the polynomial equation:
λ[itex]^{3}[/itex] +/- λ - 1 = 0
Bringing the "1+" back in, the particular solution to be added on is T(n,1) = 0, T(n,111) = -1.
The general solution is therefore
[itex]\Sigma^{6}_{i=1} k_{i}λ_{i}^n[/itex]
where the λ[itex]_{i}[/itex] are the roots of the polynomial.

haruspex

OK, here's my attempt at the actual problem. Methods and results largely the same.

Let C(n) be the number of subsets of Sn that sum to more than A(n).
Let D(n) be the number of subsets of Sn that sum to more than A(n)+A(n-1).

Starting with a summation target of A(n)+1 (or higher):
1. Suppose we use A(n). We now only have to use one other, i.e. any of 2^(n-1)-1 subsets. OTOH,
2. if we don't use A(n) we know we must use either A(n-1) or A(n-2) or both.
2a. If we use both then we can use any combination of A(1) to A(n-3), 2^(n-3) subsets.
2b. If we use A(n-1) but not A(n-2) then we have a remaining target of A(n)+1-A(n-1) = A(n-3)+1, for which there are C(n-3) possibilities.
2c. If we use neither A(n) nor A(n-1) then we have a target of A(n)+1 = A(n-2)+A(n-3)+A(n-4)+1. We must use A(n-2). That leaves a target of A(n-3)+A(n-4)+1, for which there are D(n-3) possibilities.
Putting this together:
C(n) = 2^(n-1)-1 + 2^(n-3) + C(n-3) + D(n-3)

Similarly, with D(n), we can use A(n), leaving a target of A(n-1)+1; or not use A(n), leaving a target of A(n)+1 = A(n-2) + A(n-3) + A(n-4) + 1.
D(n) = C(n-1) + D(n-3)

The homogeneous solution is λ[itex]^{n}[/itex], where λ satisfies the same equation as in the previous post: λ[itex]^{3}[/itex] +/- λ - 1 = 0.
The particular solution is now:
C(n) = (2^n)*7/9; D(n) = (2^n)*4/9 + 1.

SeventhSigma

I don't think that's right... doesn't return 501 for N=10 although the logic seems to be headed in the right direction

SeventhSigma

Again I think I maybe haven't made it clear what this problem entails:

If we have N=5 that means S has the first five terms a(1) through a(5): [1, 2, 3, 4, 6]
The answer here is 7 because
(2,3,4) because the internal sum of 5 is greater than 4
(3,4,6) because the internal sum of 7 is greater than 6
(1,2,3,4) because the internal sum of 6 is greater than 4
(1,2,4,6) because the internal sum of 7 is greater than 6
(1,3,4,6) because the internal sum of 8 is greater than 6
(2,3,4,6) because the internal sum of 9 is greater than 6
(1,2,3,4,6) because the internal sum of 10 is greater than 6

A valid subset of S is one where the highest element of that subset is less than the sum of the rest of that subset.

"Starting with a summation target of A(n)+1 (or higher):
1. Suppose we use A(n). We now only have to use one other, i.e. any of 2^(n-1)-1 subsets. OTOH, "

Implies the first summation target we look at for N=5 is A(5)+1 = 6+1 = 7
Now suppose we use A(5) or 6 in our subset: (6)
You say that including anything from the rest of S, (1,2,3,4), is valid here, but it isn't. I could use one other (1,2) giving me (1,2,6) which is not valid because 1+2 is < 6. It is true that 1+2+6 >= 7, but that isn't what we're trying to solve for here.

haruspex

SeventhSigma, Sorry, I forgot to point out that this is not quite the problem as you stated it, but that it should be mappable to it fairly easily.
First, if you exclude the use in the sum of the top term in the set, that just subtracts 2^(n-1)-1 possibilities. That gets us to the version ClifDavis considered. (I probably could have got straight to that by modifying the argument a little. You might care to try that.) Now you have to sum the counts for n = 1 to N to get the solution to the correct version.

SeventhSigma

I tried to do that but was getting erroneous values. Would you be able to show how it works for something like N=10 in terms of setup? (I know the answer is 501 there)

N=1, 2, 3: Answer 0
N=4: Answer 2
N=5: Answer 7
N=6: Answer 19
N=7: Answer 47
N=8: Answer 108
N=9: Answer 236
N=10: Answer 501

haruspex

So you found all the roots and coefficients? I haven't tried to do that. Could you post them? Or did you just run through the logic recurrence to see if it gave the right answer?