[superprismatic]

Take the integers from 1 to 13 and distribute

them among 4 sets such that the sum of the

products of the contents of the sets is minimal.

Each set must be non-empty. If a set contains

only one number, that number is considered to

be the product for that set.

For example, if I divided the numbers as follows:

{1,2,3,4,5,7}, {6,11,12}, {8,9,10}, and {13},

their products would be 840, 792, 720, and 13

respectively. The sum of these is 2365. So,

2365 is the sum of products for this particular

way of distributing the 13 numbers into 4 sets.

Two questions:

1. What is the minimum value for the sum of products?

2. In how many different ways can you achieve the minimum?

[Guest]

1,5,9,13 585 5,9,13 585 5,9,13 585 5,9,13 585

2,8,10 160 1,2,8,10 160 2,8,10 160 2,8,10 160

3,7,11 231 3,7,11 231 1,3,7,11 231 3,7,11 231

4,6,12 288 4,6,12 288 4,6,12 288 1,4,6,12 288

1264 1264 1264 1264

Take the integers from 1 to 13 and distribute

them among 4 sets such that the sum of the

products of the contents of the sets is minimal.

Each set must be non-empty. If a set contains

only one number, that number is considered to

be the product for that set.

For example, if I divided the numbers as follows:

{1,2,3,4,5,7}, {6,11,12}, {8,9,10}, and {13},

their products would be 840, 792, 720, and 13

respectively. The sum of these is 2365. So,

2365 is the sum of products for this particular

way of distributing the 13 numbers into 4 sets.

Two questions:

1. What is the minimum value for the sum of products?

2. In how many different ways can you achieve the minimum?

[superprismatic]

1,5,9,13 585 5,9,13 585 5,9,13 585 5,9,13 585

2,8,10 160 1,2,8,10 160 2,8,10 160 2,8,10 160

3,7,11 231 3,7,11 231 1,3,7,11 231 3,7,11 231

4,6,12 288 4,6,12 288 4,6,12 288 1,4,6,12 288

1264 1264 1264 1264

Good try, but you can get a bit lower! By the way, use spoilers so others can look at the posts without seeing answers which might spoil their experiences working on the problems. Another thing: You can use the code /code tags to make sure your columns align correctly.

Edited December 19, 2009 by superprismatic

[Guest]

1124

Don't know if it's a minimum though.

[Guest]

(1,2,11,12)(3,9,10)(4,5,13)(6,7,8) = 1130

1124

Don't know if it's a minimum though.

Edited December 20, 2009 by jruel

[Guest]

(1,2,11,12)(3,9,10)(4,5,13)(6,7,8) = 1130

switching your 5 and 6 ←1 (drops 4) and then

switching your 12 and 13 ←1 (drops 2))

[Guest]

I can't get less than 1124.

Here is my sequence:

{13,11,2,1}

{12,8,3}

{10,7,4}

{9,6,5}

Of course the number 1 can be put in any set so this makes 4 different sequences

[superprismatic]

I can't get less than 1124.

Here is my sequence:

{13,11,2,1}

{12,8,3}

{10,7,4}

{9,6,5}

Of course the number 1 can be put in any set so this makes 4 different sequences

1124 is the lowest, but there's a little more than 4 of them. Of course, it will be a multiple of 4 because you can move the 1 around.

[Guest]

1124 is the lowest, but there's a little more than 4 of them. Of course, it will be a multiple of 4 because you can move the 1 around.

Well, I found 12 different groups that make the minimum, but didn't find a systematic way of making sure I have them all.

Good puzzle superprismatic -- did you make this one up?

Edited December 23, 2009 by xamdam

[superprismatic]

Well, I found 12 different groups that make the minimum, but didn't find a systematic way of making sure I have them all.

Good puzzle superprismatic -- did you make this one up?

Yes, I made it up. Thanks for telling me you liked it.

I only found 8 which is actually 2 different ones with the 1s moving around. I thought I had exhausted the possibilities with a program but maybe there's a small bug. Anyway, I'd like to see your 12 which I suppose is 3 with the 1s moving around.

[Guest]

Yes, I made it up. Thanks for telling me you liked it.

I only found 8 which is actually 2 different ones with the 1s moving around. I thought I had exhausted the possibilities with a program but maybe there's a small bug. Anyway, I'd like to see your 12 which I suppose is 3 with the 1s moving around.

I'd like to see that third one too! Seems I have two, not three. Two I had were basically the same -- didn't notice.

Here are the two I got (without the 1s):

#1 ---- (13,11,2) ; (12,6,4); (10,3,9); (8,7,5)

#2 ---- (13,11,2); (3,8,12); (6,9,5); (4,10,7)

I got them by trying to get the four sums close to each other -- I think they were between 270 and 288.

But I didn't have a strategy to make sure I had 'em all.

What was your program?

[superprismatic]

I'd like to see that third one too! Seems I have two, not three. Two I had were basically the same -- didn't notice.

Here are the two I got (without the 1s):

#1 ---- (13,11,2) ; (12,6,4); (10,3,9); (8,7,5)

#2 ---- (13,11,2); (3,8,12); (6,9,5); (4,10,7)

I got them by trying to get the four sums close to each other -- I think they were between 270 and 288.

But I didn't have a strategy to make sure I had 'em all.

What was your program?

My program? Well, I wrote it in FORTRAN.

Basically, I wrote a subroutine to enumerate

all ways of breaking a set up into n subsets.

I simply used this subroutine to generate all

ways to break up {1,2,3,4,5,6,7,8,9,10,11,12,13}

into 4 subsets. I computed the sum of products

of each one and printed it out if its sum

did at least as well as the best so far.

The program ran in about a second and the last

eight things printed out had a sum of 1124.

That's when I saw the roving 1 phenomenon.

I also notice that there were some which had

a sum of 1125 printed out before the 1124 ones.

[Guest]

My program? Well, I wrote it in FORTRAN.

Basically, I wrote a subroutine to enumerate

all ways of breaking a set up into n subsets.

I simply used this subroutine to generate all

ways to break up {1,2,3,4,5,6,7,8,9,10,11,12,13}

into 4 subsets. I computed the sum of products

of each one and printed it out if its sum

did at least as well as the best so far.

The program ran in about a second and the last

eight things printed out had a sum of 1124.

That's when I saw the roving 1 phenomenon.

I also notice that there were some which had

a sum of 1125 printed out before the 1124 ones.

Very good. Ah yes, I remember writing a FORTRAN program to find Magic Squares.

Those punch cards were fun. It took a day or so to have the programs returned.

The printout would be wrapped around the card deck with a rubber band.

Often there would be a message like "Syntax error in line 30."