Little math challenge (no complete automatism allowed)

[pier4r]

having
\[ 1^{2}, 2^{2}, 3^{2}, ... , 27^{2} \]

divide them in 3 groups (no duplicates) with the same sum.
Surely you can go and write programs to find the solution. The idea is, though, you solve it with pen and paper (or, dunno, drawings). At most one can use the equivalent of a simple calculator (no iterations or programmability).

[SlideRule]

Is this on the right track?

⅓(n³) + ½(n²) + ¹/₆(n)
3
where n=27

= 6930/3
= 2310

BEST!
SlideRule

ps: a boo=boo somewhere along the line would be very embarrassing

[pier4r]

Are you trying the closed form for the sum of the integer squares? If yes (I'm not sure ) I don't see how it helps . Maybe it does and it is just me.

[Valentin Albillo]

(04-26-2018 04:11 PM)pier4r Wrote:  having
\[ 1^{2}, 2^{2}, 3^{2}, ... , 27^{2} \]
divide them in 3 groups (no duplicated) with the same sum.

By the usual formula, the sum of the squares of integers from 1 to 27 is 6930 so each group's sum must be 6930/3 = 2310.

Knowing this, the rest is just a simple matter of trying by hand a few cyclic permutations of 9-element sets and, in order not to spoil the fun for others, I'll give here just the first, middle and last element for each group:

1^2 + ... + 15^2 + ... + 26^2 = 2310
2^2 + ... + 13^2 + ... + 27^2 = 2310
3^2 + ... + 14^2 + ... + 25^2 = 2310

I've only considered the case of equal-size groups (9 elements each) but perhaps unequally-sized groups having the same sum are possible as well.

Regards.
V.
.

[SlideRule]

A little help from another perspective?

1² = 01 = 1
2² = 04 = 1 + 3
3² = 09 = 1 + 3 + 5
4² = 16 = 1 + 3 + 5 +7
5² = 25 = 1 + 3 + 5 +7 + 9
6² = 36 = 1 + 3 + 5 +7 + 9 + 11
7² = 49 = 1 + 3 + 5 +7 + 9 + 11 + 13
8² = 64 = 1 + 3 + 5 +7 + 9 + 11 + 13 + 15
9² = 81 = 1 + 3 + 5 +7 + 9 + 11 + 13 + 15 + 17
etc.

BEST!
SlideRule

[EdS2]

(04-26-2018 10:17 PM)Valentin Albillo Wrote:  ... a few cyclic permutations ...

Why cyclic - is that obvious??

[Valentin Albillo]

(04-27-2018 07:27 AM)EdS2 Wrote:  Why cyclic - is that obvious??

Well, I have lots of experience solving 'combinatorial' math puzzles (like the many such in Project Euler) and I've developed the heuristic of trying cyclic permutations first, whether I solve them using a computer or not.

That said, and as I've already solved the challenge as per Pier's requirements, I've done a little computer-assisted research to see whether the 1-27 sequence of integers can be rearranged in 3 groups of unequal length that nevertheless still add up to 2310 each.

To help me in that regard, I've coded a 5-line generalized subprogram for the HP-71B which accepts a list of integers, the value they should add up to (no repeated values allowed), and the maximum element allowable, and outputs each solution sequence in order and the number of solutions found. For instance:

- decompositions of 200 as a sum of squares from 1\(^2\) up to 10\(^2\):

>RUN
? 200,10

1 : 1 2 3 4 5 8 9 (i.e.: 1\(^2\)+2\(^2\)+3\(^2\)+4\(^2\)+5\(^2\)+8\(^2\)+9\(^2\) = 200)
2 : 1 3 4 5 6 7 8
3 : 1 3 4 5 7 10
4 : 3 5 6 7 9
5 : 6 8 10

- same but with elements up to 14\(^2\):

>RUN
? 200,14

1 : 1 2 3 4 5 8 9
2 : 1 2 3 4 7 11
3 : 1 2 5 7 11
4 : 1 3 4 5 6 7 8
5 : 1 3 4 5 7 10
6 : 2 4 6 12
7 : 2 14
8 : 3 5 6 7 9
9 : 6 8 10

Applying it to Pier's problem, i.e.: solutions which add up to 2310 using squares up to 27\(^2\), we get:

>RUN
? 2310,27

1 : 1 2 3 4 5 6 7 8 9 10 11 12 13 17 19 20 21
2 : 1 2 3 4 5 6 7 8 9 10 11 12 14 16 18 20 22
3 : 1 2 3 4 5 6 7 8 9 10 11 12 15 16 17 19 23
4 : 1 2 3 4 5 6 7 8 9 10 11 13 14 15 17 21 22
5 : 1 2 3 4 5 6 7 8 9 10 11 13 14 15 18 19 23
6 : 1 2 3 4 5 6 7 8 9 10 11 13 15 16 23 25
7 : 1 2 3 4 5 6 7 8 9 10 11 13 16 17 19 27
8 : 1 2 3 4 5 6 7 8 9 10 11 15 17 19 20 23
9 : 1 2 3 4 5 6 7 8 9 10 11 17 19 23 25
10 : 1 2 3 4 5 6 7 8 9 10 12 13 14 16 22 26
... ... ... ... ...
29256 : 13 14 16 17 18 20 26
29257 : 13 14 16 22 23 26
29258 : 14 15 22 26 27
29259 : 14 16 17 18 19 20 22
29260 : 14 17 18 21 22 24
29261 : 15 16 18 20 23 24
29262 : 15 20 22 24 25
29263 : 16 18 23 24 25
29264 : 16 19 21 24 26
29265 : 16 20 21 22 27

So we get 29265 solutions in all of various lengths, all of which add up to 2310 and use no squares greater than 27\(^2\). Now it's just a matter of writing a simple routine to scan them and check whether there are three (or more) which share no common elements and there you are. I won't spoil the fun by providing the solution, of course.

By the way, I said "generalized subprogram" because it works for any arbitrary sequence of integers (such as cubes, Fibonacci numbers, primes, ...), not just squares.

Last, some trivia:

There are 154 solutions to express 2310 as a sum of 4 squares or less but all of them require either elements greater than 27\(^2\) or else repeated elements. If no repetitions are allowed, there are just 142 solutions, the last being:

2310 = 19\(^2\)+21\(^2\)+22\(^2\)+32\(^2\)

Finally, using my subprogram to find decompositions of 2018 using squares up to 18\(^2\), finds the following three solutions:

>RUN
? 2018,18

1 : 2 3 6 8 9 10 11 12 13 14 15 16 17 18
2 : 2 4 5 6 7 8 10 11 12 13 14 15 16 17 18
3 : 7 8 9 10 11 12 13 14 15 16 17 18

and the last is particularly noteworthy as it's the sum of 12 consecutive squares beginning with 7\(^2\) and ending with 18\(^2\):

2018 = 7\(^2\)+8\(^2\)+9\(^2\)+10\(^2\)+11\(^2\)+12\(^2\)+13\(^2\)+14\(^2\)+15\(^2\)+16​\(^2\)+17\(^2\)+18\(^2\)

Regards.
V.
.

[pier4r]

Nice Valentin!

A question, does your program check the entire search space (dropping combinations that overflow the limit)? In short is it brute forcing or is it smarter than brute force?

[Valentin Albillo]

(04-29-2018 06:45 AM)pier4r Wrote:  Nice Valentin!

I think you're missing a comma but thanks.

Quote:does your program check the entire search space (dropping combinations that overflow the limit)?

Yes. Else you'd not be able to guarantee finding each and every solution.

Quote:In short is it brute forcing or is it smarter than brute force?

It's "smarts" consist in a simple depth-first iterative search with early pruning, which allows it to find and display all 29265 solutions in reasonable time despite dealing with 27 variables which can each individually go from 0 (doesn't appear in the solution) to 27, without using either FOR-NEXT loops or REPEAT/LOOP/WHILE constructs, or (Heaven forbid !) GOTO, all in just 5 lines.

Whether that's smart enough it's up to you (New York, New York ...)

Regards.
V.
.

[EdS2]

Thanks Valentin!

[Valentin Albillo]

(04-30-2018 08:35 AM)EdS2 Wrote:  Thanks Valentin!

You're welcome. Thanks for your interest.

V.