Post Reply 
Little math challenge (no complete automatism allowed)
04-26-2018, 04:11 PM (This post was last modified: 09-09-2023 08:55 AM by pier4r.)
Post: #1
Little math challenge (no complete automatism allowed)
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).

Wikis are great, Contribute :)
Find all posts by this user
Quote this message in a reply
04-26-2018, 08:51 PM (This post was last modified: 04-27-2018 01:23 AM by SlideRule.)
Post: #2
RE: Little math challenge (no complete automatism allowed)
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
Find all posts by this user
Quote this message in a reply
04-26-2018, 09:20 PM
Post: #3
RE: Little math challenge (no complete automatism allowed)
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.

Wikis are great, Contribute :)
Find all posts by this user
Quote this message in a reply
04-26-2018, 10:17 PM
Post: #4
RE: Little math challenge (no complete automatism allowed)
(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.
.

  
All My Articles & other Materials here:  Valentin Albillo's HP Collection
 
Visit this user's website Find all posts by this user
Quote this message in a reply
04-27-2018, 01:36 AM
Post: #5
RE: Little math challenge (no complete automatism allowed)
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
Find all posts by this user
Quote this message in a reply
04-27-2018, 07:27 AM
Post: #6
RE: Little math challenge (no complete automatism allowed)
(04-26-2018 10:17 PM)Valentin Albillo Wrote:  ... a few cyclic permutations ...
Why cyclic - is that obvious??
Find all posts by this user
Quote this message in a reply
04-29-2018, 12:31 AM
Post: #7
RE: Little math challenge (no complete automatism allowed)
(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.
.

  
All My Articles & other Materials here:  Valentin Albillo's HP Collection
 
Visit this user's website Find all posts by this user
Quote this message in a reply
04-29-2018, 06:45 AM
Post: #8
RE: Little math challenge (no complete automatism allowed)
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?

Wikis are great, Contribute :)
Find all posts by this user
Quote this message in a reply
04-29-2018, 02:22 PM
Post: #9
RE: Little math challenge (no complete automatism allowed)
(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.
.

  
All My Articles & other Materials here:  Valentin Albillo's HP Collection
 
Visit this user's website Find all posts by this user
Quote this message in a reply
04-30-2018, 08:35 AM
Post: #10
RE: Little math challenge (no complete automatism allowed)
Thanks Valentin!
Find all posts by this user
Quote this message in a reply
04-30-2018, 10:15 PM
Post: #11
RE: Little math challenge (no complete automatism allowed)
(04-30-2018 08:35 AM)EdS2 Wrote:  Thanks Valentin!

You're welcome. Thanks for your interest.

V.

  
All My Articles & other Materials here:  Valentin Albillo's HP Collection
 
Visit this user's website Find all posts by this user
Quote this message in a reply
Post Reply 




User(s) browsing this thread: 1 Guest(s)