Problem 103

[Phibonacci]

I realize that I need to minimize the number of tests I need to make to ensure I have a special sum set. So far it seems that I can minimize the tests by assuming the second requirement and only testing for the first requirement of S(B) != S(C). By doing this for n = 3 the tests I need to make for {a1, a2, a3} would be:

{a1} != {a2}
{a1} != {a3}
{a2} != {a3}
so for my first special set to test of {1, 2, 3} this clearly doesn't work as {a1, a2} == {a3}

is this not the correct way to minimize the tests I need to make to ensure a special sum set without having to test all possible combination's?

Also, once I found a way to minimize the tests, can someone give me a hint as to how to pick sets to test. the simplest way i can think of would be something such as
{1, 2, 3}
{1, 2, 4}
{1, 2, 5}
etc...
this obviously doesn't work because I don't know when to stop and increment a2 to start over again at
{1, 3, 4}
{1, 3, 5}
{1, 3, 6}

can someone point me in the right direction?

[PsssT]

So, I have this nifty algorithm to generate "nice" small tuples, I haven't proved that is supplies me with minimal ones, but it looks like that at the moment.

The problem is that my algorithm spits out A={11,16,19,21,22,23} for n=6 with S(A) = 111.
The problem states that the optimal tuple for n=6 is A={11,18,19,20,22,25}, with S(A) = 115.

So it may be that my tuple is invalid, but i cant see why or that the program that generated tuples for the problem is erroneous. Anyhow, this renders me suspicious about my answer to n=7 (which the page stated was wrong).

So, can somebody verify that A={11,16,19,21,22,23} is a valid tuple?

[harryh]

It's not a valid tuple because 11+22+23=16+19+21, whereas Problem 103 (View Problem) states :

S(B) ≠ S(C); that is, sums of subsets cannot be equal.

[PsssT]

Oh... god...
thats what happens when you look at the same numbers for too long.
Thanks for spotting the obvious

[xe3tec]

Heh,

I dont get why A = {11, 18, 19, 20, 22, 25} is the Optimum. How do I get there? what woule n5 look like?

[ldesnogu]

I dont get why A = {11, 18, 19, 20, 22, 25} is the Optimum. How do I get there?

I know that won't help, but telling you that would break the problem...

what woule n5 look like?

n=5 is given in the problem, it is optimal.

Your issue perhaps is that the problem states a rule to generate Sn from Sn-1, but the rule doesn't provide the optimum set for n>5.

[xe3tec]

edit: ah.."it seems" so I dont have to obey that rule?

so I have to find a new rule which works for n>5?

or is there a rule which works for all?

[rayfil]

or is there a rule which works for all?

As far as we know at this time, the answer is ..... NO .

[xe3tec]

But if there are different rules for different n, how is a optimum set defined?!

[ldesnogu]

But if there are different rules for different n, how is a optimum set defined?!

S(A) defines the optimum, it has to be minimised. This is clearly stated in the text.

[xe3tec]

I dont get it.

Why is n=4 min not {1,2,3,4}? Its minimized and the sums of subset are not equal

[jaap]

I dont get it.

Why is n=4 min not {1,2,3,4}? Its minimized and the sums of subset are not equal

1+4 = 2+3
1+3 = 4
1+2 = 3
So there are several equal subset sums.

[ldesnogu]

Why is n=4 min not {1,2,3,4}? Its minimized and the sums of subset are not equal

This violates rule i: pick B={1,2}, C={3}; the sum of their elements are equal.

EDIT: jaap beat me to it

[xe3tec]

oh true...kind of forgot the other subsets, now its clear

[PurpleBlu3s]

Can someone point out what the pair of disjoint subsets is that invalidates this as a solution for n=6?

A = {11,16,19,21,22,23}, S(A) = 112

I cannot anything wrong with it, though obviously there must be (at least) one pairing.

Thanks.

[jaap]

Can someone point out what the pair of disjoint subsets is that invalidates this as a solution for n=6?

A = {11,16,19,21,22,23}, S(A) = 112

I cannot anything wrong with it, though obviously there must be (at least) one pairing.

Thanks.

11+22+23 = 56 = 16+19+21

[PurpleBlu3s]

Thank you. I was going mad thinking my algorithm was wrong when I was so sure it was correct - I had a silly problem with an array operation!

[vstastny]

Hi,
I was playing around with problem 103 and my algorithm gave me an answer 19,31,37,38,39,41,44 with the sum of 249.
This is not the correct solution, however I can not find out why, since
1) a1 + a2 > a7
2) a1 + a2 + a3 > a6 + a7
3) a1 + a2 + a3 + a4 > a5 +a6 + a7
I would highly appreciate if anyone could give me an example of the incorrectness of the solution.
Thanks.

[TheEvil]

Hi,
I was playing around with problem 103 and my algorithm gave me an answer 19,31,37,38,39,41,44 with the sum of 249.
This is not the correct solution, however I can not find out why, since
1) a1 + a2 > a7
2) a1 + a2 + a3 > a6 + a7
3) a1 + a2 + a3 + a4 > a5 +a6 + a7
I would highly appreciate if anyone could give me an example of the incorrectness of the solution.
Thanks.

You checked the second condition only, but the problem is with the first one, since 31+44=37+38.

[rockstome]

{23, 40, 41, 42, 44, 47, 54}
and
{23, 34, 41, 44, 46, 47, 48}
satisfies i & ii proporties?