Problem 103

[rayfil]

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

Yes to both.

[rouge6789]

Bonsoir.
Pour 4, vous indiquez que l'optimum est 3,5,6,7 soit un total de 21
Mon algorithme trouve : 2,3,4 8 pour un total de 17 !!
Je vois pas mon erreur ?
Cordialement.

[TheEvil]

Bonsoir.
Pour 4, vous indiquez que l'optimum est 3,5,6,7 soit un total de 21
Mon algorithme trouve : 2,3,4 8 pour un total de 17 !!
Je vois pas mon erreur ?
Cordialement.

Condition ii.:
B={2,3}
C={8}
|B|=2 > 1=|C|
although 2+3<8, which is contradiction

Sorry, for not speaking French.

[rouge6789]

Ah ok.
thanck you very much

[Sh4pe]

I'd like to complain a bit about the wording of the problem.

1) You should write where the elements of the sets live in. We know that one should be able to add the elements and that there should be a partial ordering on the set they live in (so that one could compare their sum). We don't even know that the set must have a smallest or a minimal element. From the given examples, I guess that all the elements are natural numbers greater or equal than 1, but this should be stated in the text in my opinion.

2) Perhaps a bit pedantic, but {3,4} = {4,3}. For the set string, you seem to assume that the set is written increasingly ordered, however. I wouldn't mind to have it in the problem description.

3) For me, it is not obvious that the optimum special sum sets are unique. From the text, however, I get the impression that they are. Are they unique?

These points confused me, I thought I should share my thoughts But this is - as usual - a very nice problem! Thank you!

[gary.paduana]

Can someone please explain why n = 4: {3, 5, 6, 7} and not {1,2,3,5}?

Code: Select all

B: (1,), Bsum: 1; C: [2, 3, 5], Csum: 10
B: (2,), Bsum: 2; C: [1, 3, 5], Csum: 9
B: (3,), Bsum: 3; C: [1, 2, 5], Csum: 8
B: (5,), Bsum: 5; C: [1, 2, 3], Csum: 6
B: (1, 2), Bsum: 3; C: [3, 5], Csum: 8
B: (1, 3), Bsum: 4; C: [2, 5], Csum: 7
B: (1, 5), Bsum: 6; C: [2, 3], Csum: 5
B: (2, 3), Bsum: 5; C: [1, 5], Csum: 6
B: (2, 5), Bsum: 7; C: [1, 3], Csum: 4
B: (3, 5), Bsum: 8; C: [1, 2], Csum: 3
B: (1, 2, 3), Bsum: 6; C: [5], Csum: 5
B: (1, 2, 5), Bsum: 8; C: [3], Csum: 3
B: (1, 3, 5), Bsum: 9; C: [2], Csum: 2
B: (2, 3, 5), Bsum: 10; C: [1], Csum: 1

As seen above, this set seems to satisfy the two rules.

edit: NEVERMIND, it appears as though len(B) + len(C) does not need to equal len(A)

[haihun]

because 2+3=5, it doesn't obey the second rule.

[dchaudh]

Why isn't the following the optimal subset of size 5?: [14,11,9,8,7]

sum [14,11,9,8,7] = 49
sum [6,9,11,12,13] = 51 (this is the optimal subset of size 5 as per the problem text)

I'm sure I'm missing something obvious but it seems like it does obey both rules...

P.S. I can confirm that my algorithm's output matches the other optimal sets provided in the problem text (i.e., sets of size 2, 3, 4 and 6).

[rayfil]

You seem to have forgotten the 2nd rule, i.e.
ii . If B contains more elements than C then S(B) > S(C).

7+8+9 = 24 while 11+14 = 25

[dchaudh]

Thank you sir

[Euler103]

Hi all, hopefully someone is still checking this thread haha.
How can n=1 {1} be a valid optimum special sum set? How can you make two disjoint, non-empty subsets from this? you could have S(B)={1} but then S(C) would have to be empty, unless you can repeat a set number in the subset?
Thanks

[dawghaus4]

Hi all, hopefully someone is still checking this thread haha.
How can n=1 {1} be a valid optimum special sum set? How can you make two disjoint, non-empty subsets from this? you could have S(B)={1} but then S(C) would have to be empty, unless you can repeat a set number in the subset?
Thanks

When is the conditional "if p, then q" true? If the hypothesis is false, the conditional is true. (Note: that does not say, when p is false, q is true.)

Thus, {1} vacuously satisfies the conditional.

Interpret the conditional this way, "Whenever you have two nonempty disjoint subsets, the following properties ae true...."

Tom

[Euler103]

When is the conditional "if p, then q" true? If the hypothesis is false, the conditional is true. (Note: that does not say, when p is false, q is true.)

Thus, {1} vacuously satisfies the conditional.

Interpret the conditional this way, "Whenever you have two nonempty disjoint subsets, the following properties ae true...."

Tom

Hi Tom, thanks for the reply. Not sure I quite follow the first two lines I'm afraid.
Your re-writing of the conditional doesn't seem to address the issue I had: how does one make two non-empty disjoint subsets with only one number in the superset? I'm sure I'm missing something obvious, I think it would help if you could show me what S(B) and S(C) are for n=1 please.
Thanks again for your help.

[jaap]

When is the conditional "if p, then q" true? If the hypothesis is false, the conditional is true. (Note: that does not say, when p is false, q is true.)

Thus, {1} vacuously satisfies the conditional.

Interpret the conditional this way, "Whenever you have two nonempty disjoint subsets, the following properties ae true...."

Tom

Hi Tom, thanks for the reply. Not sure I quite follow the first two lines I'm afraid.
Your re-writing of the conditional doesn't seem to address the issue I had: how does one make two non-empty disjoint subsets with only one number in the superset? I'm sure I'm missing something obvious, I think it would help if you could show me what S(B) and S(C) are for n=1 please.
Thanks again for your help.

Any statement one makes about things that do not exist will be automatically true, because there is no counterexample.
The only way it could be shown false would be to find one of those non-existent things and show it does not have the properties that the statement claims such things must have.

[dawghaus4]

When is the conditional "if p, then q" true? If the hypothesis is false, the conditional is true. (Note: that does not say, when p is false, q is true.)

Thus, {1} vacuously satisfies the conditional.

Interpret the conditional this way, "Whenever you have two nonempty disjoint subsets, the following properties ae true...."

Tom

Hi Tom, thanks for the reply. Not sure I quite follow the first two lines I'm afraid.
Your re-writing of the conditional doesn't seem to address the issue I had: how does one make two non-empty disjoint subsets with only one number in the superset? I'm sure I'm missing something obvious, I think it would help if you could show me what S(B) and S(C) are for n=1 please.
Thanks again for your help.

In your original post you asked, "How can n=1 {1} be a valid optimum special sum set? How can you make two disjoint, non-empty subsets from this?" The answer to the second question is, "you can't; no two such subset exists" And that is exactly why {1} is an optimum special sum.

You want to read the problem as saying that a set is a optimum special sum set only if it has two nonempty disjoint subsets that satisfy properties I. and II. But that is not what it says. The correct reading is "If it has two nonempty disjoint subsets, they satisfy properties I. and II.

I go back to my original question: When is the conditional statement, "if p, then q" true? It will be false only when p, the hypothesis, is true and q, the conclusion, is false. if a set has two nonempty disjoint subsets and not both properties i. and II. are met, the set is not optimum. Here, the hypothesis (it has two nonempty disjoint subsets) is false. Thus the statement, "If it has two nonempty disjoint subsets properties I. and II are satisfied" is true.

That is the bane of many a math student, not understanding that the statement "if false hypothesis, then false conclusion" is classified as a true statement.

Tom

[Euler103]

Hi Tom, Jaap.
They were both very nice explanations, I feel I've got my head round the issue a lot more now. I haven't really come across that wording before so it's a really cool thing to understand for future problems.
Thanks again.

[md-geist]

I enjoy solving Project Euler puzzles from time to time. Of all the problems I have solved this is the first problem that might be wrong in the problem description. It didn't have any effect on solving the actual problem.

Shouldn't the optimum set for n = 6 be A = {8, 12, 14, 15, 16, 32}, with S(A) = 97?

Or am I missing something.

[v6ph1]

If B contains more elements than C then S(B) > S(C).

8+12+14 < 16+32

[md-geist]

If B contains more elements than C then S(B) > S(C).

8+12+14 < 16+32

Of course. Thanks for pointing it out.