Problem 103

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.

This forum is NOT meant to discuss solution methods for a problem.

In particular don't post any code fragments or results.

Don't start begging others to give partial answers to problems

Don't ask for hints how to solve a problem

Don't start a new topic for a problem if there already exists one


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
User avatar
rayfil
Administrator
Posts: 1406
Joined: Sun Mar 26, 2006 5:30 am
Location: Quebec, Canada
Contact:

Re: Problem 103

Post by rayfil »

rockstome wrote:{23, 40, 41, 42, 44, 47, 54}
and
{23, 34, 41, 44, 46, 47, 48}
satisfies i & ii proporties?
Yes to both.
When you assume something, you risk being wrong half the time.
rouge6789
Posts: 4
Joined: Thu Aug 16, 2012 3:17 pm

Re: Problem 103

Post by 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.
User avatar
TheEvil
Posts: 84
Joined: Sun Nov 13, 2011 10:38 am
Location: Szeged, Hungary

Re: Problem 103

Post by TheEvil »

rouge6789 wrote: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.
Image
rouge6789
Posts: 4
Joined: Thu Aug 16, 2012 3:17 pm

Re: Problem 103

Post by rouge6789 »

Ah ok.
thanck you very much
Sh4pe
Posts: 1
Joined: Wed Apr 03, 2013 3:04 pm

Re: Problem 103

Post by 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!
Image
gary.paduana
Posts: 1
Joined: Tue Oct 08, 2013 1:45 pm

Re: Problem 103

Post by 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
Posts: 1
Joined: Fri Jan 10, 2014 9:41 pm

Re: Problem 103

Post by haihun »

because 2+3=5, it doesn't obey the second rule.
dchaudh
Posts: 4
Joined: Mon Dec 15, 2014 7:57 am

Re: Problem 103

Post by 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).
User avatar
rayfil
Administrator
Posts: 1406
Joined: Sun Mar 26, 2006 5:30 am
Location: Quebec, Canada
Contact:

Re: Problem 103

Post by 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
When you assume something, you risk being wrong half the time.
dchaudh
Posts: 4
Joined: Mon Dec 15, 2014 7:57 am

Re: Problem 103

Post by dchaudh »

Thank you sir
Euler103
Posts: 3
Joined: Fri Jan 06, 2017 6:39 pm

Re: Problem 103

Post by 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
User avatar
dawghaus4
Posts: 56
Joined: Fri Nov 29, 2013 2:22 am

Re: Problem 103

Post by dawghaus4 »

Euler103 wrote: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
Posts: 3
Joined: Fri Jan 06, 2017 6:39 pm

Re: Problem 103

Post by 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.
User avatar
jaap
Posts: 554
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: Problem 103

Post by jaap »

Euler103 wrote:
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.
User avatar
dawghaus4
Posts: 56
Joined: Fri Nov 29, 2013 2:22 am

Re: Problem 103

Post by dawghaus4 »

Euler103 wrote:
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
Posts: 3
Joined: Fri Jan 06, 2017 6:39 pm

Re: Problem 103

Post by 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
Posts: 2
Joined: Thu Jul 06, 2017 8:24 am

Re: Problem 103

Post by 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
Posts: 128
Joined: Mon Aug 25, 2014 7:14 pm

Re: Problem 103

Post by v6ph1 »

If B contains more elements than C then S(B) > S(C).
8+12+14 < 16+32
Image
md-geist
Posts: 2
Joined: Thu Jul 06, 2017 8:24 am

Re: Problem 103

Post by md-geist »

v6ph1 wrote: Thu Jul 06, 2017 8:54 am
If B contains more elements than C then S(B) > S(C).
8+12+14 < 16+32
Of course. Thanks for pointing it out.
Post Reply