July 2018 little math problem
07-25-2018, 08:52 PM (This post was last modified: 07-25-2018 08:53 PM by pier4r.)
Post: #1
 pier4r Senior Member Posts: 2,248 Joined: Nov 2014
July 2018 little math problem
I should really collect all those little problems in one place :/

The problem should be solved ideally with pen and paper. Of course computing devices are allowed as last resort.

One has the numbers 1,2,3,4,5,6,7,8,9 and should arrange them in the following position without repetition.

Code:
 a b c     d     e f g         h         i
The arrangement should be such that the four sides will have numbers that summed together, will produce the same value.

What are the arrangements? How many are there? Of course would be nice to know the way you picked to solve the problem.

Code:
 you can give your answer using spoilers like this RPL! RPL! RPL!

Wikis are great, Contribute :)
07-25-2018, 09:33 PM (This post was last modified: 07-25-2018 09:35 PM by Voldemar.)
Post: #2
 Voldemar Senior Member Posts: 314 Joined: Mar 2014
RE: July 2018 little math problem
Code:
  9 3 1       8       4 7 2            6            5
07-25-2018, 10:27 PM (This post was last modified: 07-25-2018 10:40 PM by Thomas Klemm.)
Post: #3
 Thomas Klemm Senior Member Posts: 1,993 Joined: Dec 2013
RE: July 2018 little math problem
I just used brute force.
Code:
Spoiler alert! a b c d e f g h i | ∑ ------------------+--- 3 9 1 8 4 7 2 5 6 | 13 5 6 2 7 4 8 1 3 9 | 13 6 7 1 5 8 4 2 3 9 | 14 5 8 1 6 7 4 3 2 9 | 14 3 9 2 4 8 5 1 6 7 | 14 4 8 2 9 3 5 6 1 7 | 14 2 9 3 4 7 6 1 5 8 | 14 1 9 4 8 2 7 5 3 6 | 14 2 8 4 9 1 7 6 3 5 | 14 3 6 5 7 2 8 4 1 9 | 14 1 7 6 5 3 9 2 4 8 | 14 3 5 6 7 1 9 4 2 8 | 14 5 7 4 3 9 1 6 2 8 | 16 3 9 4 5 7 1 8 2 6 | 16 4 7 5 3 8 2 6 1 9 | 16 2 8 6 1 9 3 4 5 7 | 16 1 9 6 2 8 3 5 4 7 | 16 1 8 7 6 3 4 9 2 5 | 16 2 6 8 1 7 5 4 3 9 | 16 1 7 8 6 2 5 9 3 4 | 16 2 5 9 4 3 6 7 1 8 | 16 3 4 9 5 2 6 8 1 7 | 16 4 5 8 3 6 2 9 1 7 | 17 1 7 9 2 6 3 8 4 5 | 17 These are 24 solutions. But we can swap a and b and swap h and i. This leads to a total of 4*24 = 96 solutions. Edit: Just noticed that we can mirror a solution. Thus these are the 12 fundamental solutions with c < g: a b c d e f g h i | ∑ ------------------+--- 3 9 1 8 4 7 2 5 6 | 13 2 8 4 9 1 7 6 3 5 | 14 1 9 4 8 2 7 5 3 6 | 14 4 8 2 9 3 5 6 1 7 | 14 5 8 1 6 7 4 3 2 9 | 14 6 7 1 5 8 4 2 3 9 | 14 1 7 8 6 2 5 9 3 4 | 16 1 8 7 6 3 4 9 2 5 | 16 3 9 4 5 7 1 8 2 6 | 16 4 7 5 3 8 2 6 1 9 | 16 5 7 4 3 9 1 6 2 8 | 16 4 5 8 3 6 2 9 1 7 | 17
07-26-2018, 12:16 AM (This post was last modified: 07-26-2018 04:53 PM by Albert Chan.)
Post: #4
 Albert Chan Senior Member Posts: 2,516 Joined: Jul 2018
RE: July 2018 little math problem
(07-25-2018 10:27 PM)Thomas Klemm Wrote:  I just used brute force.

I did solved Thomas third solution by hand.

If using computer is allowed, I would use Picat Programming Language
It is great for puzzle solving, and very fast (below code take 0.12 second to run)

Code:
import cp.                   % zigzag4.pi, 4 sums added to same number S main => go, fail; true.      % fail forced Picat to search all solutions go => Vars = [A,B,C,D,E,F,G,H,I],       Vars :: 1..9,       all_different(Vars),       A + B + C #= S,       E + D + C #= S,       E + F + G #= S,       I + H + G #= S,       solve(Vars),        writeln(Vars). % % *** solutions below *** %       1    [1,7,6,5,3,9,2,4,8]      2    [1,7,6,5,3,9,2,8,4]      3    [1,7,8,6,2,5,9,3,4]      4    [1,7,8,6,2,5,9,4,3]      5    [1,7,9,2,6,3,8,4,5]      6    [1,7,9,2,6,3,8,5,4]      7    [1,8,7,6,3,4,9,2,5]      8    [1,8,7,6,3,4,9,5,2]      9    [1,9,4,8,2,7,5,3,6]     10    [1,9,4,8,2,7,5,6,3]     11    [1,9,6,2,8,3,5,4,7]     12    [1,9,6,2,8,3,5,7,4]     13    [2,5,9,4,3,6,7,1,8]     14    [2,5,9,4,3,6,7,8,1]     15    [2,6,8,1,7,5,4,3,9]     16    [2,6,8,1,7,5,4,9,3]     17    [2,8,4,9,1,7,6,3,5]     18    [2,8,4,9,1,7,6,5,3]     19    [2,8,6,1,9,3,4,5,7]     20    [2,8,6,1,9,3,4,7,5]     21    [2,9,3,4,7,6,1,5,8]     22    [2,9,3,4,7,6,1,8,5]     23    [3,4,9,5,2,6,8,1,7]     24    [3,4,9,5,2,6,8,7,1]     25    [3,5,6,7,1,9,4,2,8]     26    [3,5,6,7,1,9,4,8,2]     27    [3,6,5,7,2,8,4,1,9]     28    [3,6,5,7,2,8,4,9,1]     29    [3,9,1,8,4,7,2,5,6]     30    [3,9,1,8,4,7,2,6,5]     31    [3,9,2,4,8,5,1,6,7]     32    [3,9,2,4,8,5,1,7,6]     33    [3,9,4,5,7,1,8,2,6]     34    [3,9,4,5,7,1,8,6,2]     35    [4,3,9,5,2,6,8,1,7]     36    [4,3,9,5,2,6,8,7,1]     37    [4,5,8,3,6,2,9,1,7]     38    [4,5,8,3,6,2,9,7,1]     39    [4,7,5,3,8,2,6,1,9]     40    [4,7,5,3,8,2,6,9,1]     41    [4,8,2,9,3,5,6,1,7]     42    [4,8,2,9,3,5,6,7,1]     43    [5,2,9,4,3,6,7,1,8]     44    [5,2,9,4,3,6,7,8,1]     45    [5,3,6,7,1,9,4,2,8]     46    [5,3,6,7,1,9,4,8,2]     47    [5,4,8,3,6,2,9,1,7]     48    [5,4,8,3,6,2,9,7,1]     49    [5,6,2,7,4,8,1,3,9]     50    [5,6,2,7,4,8,1,9,3]     51    [5,7,4,3,9,1,6,2,8]     52    [5,7,4,3,9,1,6,8,2]     53    [5,8,1,6,7,4,3,2,9]     54    [5,8,1,6,7,4,3,9,2]     55    [6,2,8,1,7,5,4,3,9]     56    [6,2,8,1,7,5,4,9,3]     57    [6,3,5,7,2,8,4,1,9]     58    [6,3,5,7,2,8,4,9,1]     59    [6,5,2,7,4,8,1,3,9]     60    [6,5,2,7,4,8,1,9,3]     61    [6,7,1,5,8,4,2,3,9]     62    [6,7,1,5,8,4,2,9,3]     63    [7,1,6,5,3,9,2,4,8]     64    [7,1,6,5,3,9,2,8,4]     65    [7,1,8,6,2,5,9,3,4]     66    [7,1,8,6,2,5,9,4,3]     67    [7,1,9,2,6,3,8,4,5]     68    [7,1,9,2,6,3,8,5,4]     69    [7,4,5,3,8,2,6,1,9]     70    [7,4,5,3,8,2,6,9,1]     71    [7,5,4,3,9,1,6,2,8]     72    [7,5,4,3,9,1,6,8,2]     73    [7,6,1,5,8,4,2,3,9]     74    [7,6,1,5,8,4,2,9,3]     75    [8,1,7,6,3,4,9,2,5]     76    [8,1,7,6,3,4,9,5,2]     77    [8,2,4,9,1,7,6,3,5]     78    [8,2,4,9,1,7,6,5,3]     79    [8,2,6,1,9,3,4,5,7]     80    [8,2,6,1,9,3,4,7,5]     81    [8,4,2,9,3,5,6,1,7]     82    [8,4,2,9,3,5,6,7,1]     83    [8,5,1,6,7,4,3,2,9]     84    [8,5,1,6,7,4,3,9,2]     85    [9,1,4,8,2,7,5,3,6]     86    [9,1,4,8,2,7,5,6,3]     87    [9,1,6,2,8,3,5,4,7]     88    [9,1,6,2,8,3,5,7,4]     89    [9,2,3,4,7,6,1,5,8]     90    [9,2,3,4,7,6,1,8,5]     91    [9,3,1,8,4,7,2,5,6]     92    [9,3,1,8,4,7,2,6,5]     93    [9,3,2,4,8,5,1,6,7]     94    [9,3,2,4,8,5,1,7,6]     95    [9,3,4,5,7,1,8,2,6]     96    [9,3,4,5,7,1,8,6,2]
07-26-2018, 12:57 AM (This post was last modified: 07-28-2018 04:36 PM by John Keith.)
Post: #5
 John Keith Senior Member Posts: 1,019 Joined: Dec 2013
RE: July 2018 little math problem
(07-25-2018 10:27 PM)Thomas Klemm Wrote:  I just used brute force.

So did I!

Emulated HP 50g with the ListExt Library took 3437 seconds on an ancient WinXP laptop. Same results.

Edit: my original code was atrociously bad. New "brute force" code is shorter and trims execution time down to 1272 seconds.

Code:
 Spoiler alert! \<< 9. LSEQ 9.   \<< DUP 3.     \<< + + NSUB 2. MOD NOT DROPN     \>> DOSUBS LEQ NOT DROPN   \>> DOPERM \>>
07-26-2018, 02:39 AM
Post: #6
 Albert Chan Senior Member Posts: 2,516 Joined: Jul 2018
RE: July 2018 little math problem
Code:
I noticed the middle number e cannot be 5, below is the prove. Prove by looking at the computer solutions does not count If you like to prove it yourself, don't peek ... s = a + b + c s = e + d + c s = e + f + g s = i + h + g add all of above, note that a+b+c+d+e+f+g+h+i = (1+9)(9)/2 = 45 4s = 45 + c + e + g Prove by contradiction: assume e = 5 4s = 50 + c + g min(50 + c + g) <= 4s <= max(50 + c + g) 53 <= 4s <= 67 Possible s = 14, 15, 16 For s = 14, c+g = 4s - 50 = 6 = 2 + 4 (only possibility) d = s-e-c = 9-c = 7 (only possibility) f = s-e-g = 9-g = 7 (only possibility)   --> impossible to have s = 14 For s = 15, c+g = 4s - 50 = 10 c + d = s - e = 10 --> imply d = g       --> impossible to have s = 15 For s = 16, c+g = 4s - 50 = 14 = 6 + 8 (only possibility) d = s-e-c = 11-c = 3 (only possibility) f = s-e-g = 11-g = 3 (only possibility)  --> impossible to have s = 16 No solution for e = 5 QED
07-26-2018, 03:42 AM
Post: #7
 Thomas Klemm Senior Member Posts: 1,993 Joined: Dec 2013
RE: July 2018 little math problem
(07-26-2018 12:16 AM)Albert Chan Wrote:  If using computer is allowed, I would use Picat Programming Language
Interesting. Never heard of that language.

I just used Python:
Code:
from itertools import permutations def check(a, b, c, d, e, f, g, h, i):     return len(set([a+b+c, c+d+e, e+f+g, g+h+i])) == 1 print [x for x in permutations(range(1, 10), 9) if check(*x)]
07-26-2018, 04:03 AM
Post: #8
 DavidM Senior Member Posts: 979 Joined: Dec 2013
RE: July 2018 little math problem
(07-26-2018 12:57 AM)John Keith Wrote:  So did I!

Emulated HP 50g with the ListExt Library took 3437 seconds on an ancient WinXP laptop. Same results.

...and yet another "brute force" method using ListExt with a slight twist on the check.

Code:
 Spoiler alert! \<<   0. 8. NDUPN \-> a b c d e f g h i   \<<     9. DUP LSEQ     SWAP     \<<       { a b c d e f g h i } STO       a b + d e + SAME       {         c d + f g + SAME         {           e f + h i + SAME           {             { a b c d e f g h i } LRCL R\->I           }           IFT         }         IFT       }       IFT     \>>     DOPERM   \>> \>> I assumed (hopefully correctly) that the following conditions had to hold: a + b = d + e c + d = f + g e + f = h + i So I nested the above tests to short-circuit them.  If a + b ≠ d + e, then there's no reason to continue checking.  If it is, then if c + d ≠ f + g, there's no reason to continue checking, etc. The short-circuit made for a nice speed improvement over checking everything each time through.
07-26-2018, 12:36 PM (This post was last modified: 07-26-2018 02:56 PM by pier4r.)
Post: #9
 pier4r Senior Member Posts: 2,248 Joined: Nov 2014
RE: July 2018 little math problem
(07-26-2018 12:57 AM)John Keith Wrote:  Emulated HP 50g with the ListExt Library took 3437 seconds on an ancient WinXP laptop. Same results.

one hour on an emulated system that will be at least a pentium 3 and more likely a pentium 4 or the like? Woah. I was expecting the 50g to be wicked fast, of course not entirely by brute force.

When I solved it by hand (a couple of solutions) I noticed a weak pattern (n1), if I find the time I will put it on the 50g to see how much it takes to find every solution.

(n1) I do believe there is a strong pattern. Mine is pretty weak but I didn't discover the strong one yet in the post, maybe because I did not stricly check the posted code.

Wikis are great, Contribute :)
07-26-2018, 01:03 PM
Post: #10
 John Keith Senior Member Posts: 1,019 Joined: Dec 2013
RE: July 2018 little math problem
(07-26-2018 04:03 AM)DavidM Wrote:  ...and yet another "brute force" method using ListExt with a slight twist on the check.

Actually not brute force as it uses analysis of the problem. Also about 4 times as fast as mine.
07-26-2018, 03:38 PM (This post was last modified: 07-26-2018 04:14 PM by DavidM.)
Post: #11
 DavidM Senior Member Posts: 979 Joined: Dec 2013
RE: July 2018 little math problem
(07-26-2018 01:03 PM)John Keith Wrote:  Actually not brute force as it uses analysis of the problem.

Well, I was thinking that any method based on visiting every permutation would be considered "brute force", though I see your point.

Here's another method that doesn't visit every permutation. It only permutes the remaining variables if the currently selected branches qualify. You might say that it's a wee bit faster.

This one I would definitely not call "brute force".

edit: I just ran this on a real 50g, and it found the same 96 solutions in about 27 minutes. I'm sure this isn't the fastest possible approach on this platform, but it's certainly much better than my first attempt! The Prime (or a newRPL 50g) should be able to do something like this much faster.
Code:
Spoiler alert... \<<   0. 8. NDUPN \-> a b c d e f g h i   \<<     9. LSEQ     4.     \<<       { a b d e } STO       a b + d e + SAME       \<<         CRMNT         3.         \<<           { c f g } STO           c d + f g + SAME           \<<             CRMNT             2.             \<<               { h i } STO               e f + h i + SAME               \<<                 { a b c d e f g h i } LRCL R\->I               \>>               IFT             \>>             DOPERM EVAL           \>>           IFT         \>>         DOPERM EVAL       \>>       IFT     \>>     DOPERM   \>> \>>
07-26-2018, 03:43 PM
Post: #12
 Thomas Klemm Senior Member Posts: 1,993 Joined: Dec 2013
RE: July 2018 little math problem
(07-26-2018 12:36 PM)pier4r Wrote:  I do believe there is a strong pattern. Mine is pretty weak but I didn't yet see it, maybe because I did not strictly check the posted code.

We can start with $$e\in\{1\ldots9\}$$. And then let $$c$$ and $$g$$ be different digits with $$c<g$$. This gives us $$9\times\binom{8}{2}=252$$ possibilities.

But since $$s=a+b+c=c+d+e=e+f+g=g+h+i$$ and $$a+b+c+d+e+f+g+h+i=\sum_{k=1}^{9}k=45$$ we know that their sum is $$4s=45+c+e+g$$ which must be divisible by 4.
This reduces the possibilities further down to 60.

We can now calculate $$d=s-c-e$$ and $$f=s-e-g$$ and check that both are digits.
And of course each element of $$\{c,d,e,f,g\}$$ must be unique.

With this we're down at 12 possibilities:
Code:
Spoiler alert! c d e f g | s ----------+--- 4 9 1 7 6 | 14 4 8 2 7 5 | 14 8 6 2 5 9 | 16 2 9 3 5 6 | 14 7 6 3 4 9 | 16 1 8 4 7 2 | 13 8 3 6 2 9 | 17 1 6 7 4 3 | 14 4 5 7 1 8 | 16 1 5 8 4 2 | 14 5 3 8 2 6 | 16 4 3 9 1 6 | 16

Now it's easy to find $$a$$ and $$b$$ so that $$a+b+c=s$$ and similarly find $$h$$ and $$i$$ so that $$g+h+i=s$$.

Code:
Spoiler alert! from itertools import combinations digits = set(range(1, 10)) for e in digits:     E = digits.copy()     E.remove(e)     for c, g in combinations(E, 2):         t = 45 + c + e + g         if t % 4:             continue         s = t / 4         d = s - c - e         if d not in digits:             continue         f = s - e - g         if f not in digits:             continue         used = set([c, d, e, f, g])         if len(used) != 5:             continue         rest = digits - used         for a, b in combinations(rest, 2):             if a+b+c != s:                 continue             h, i = rest - set([a, b])             if g+h+i != s:                 continue             print a, b, c, d, e, f, g, h, i

Checking only 252 instead of 9! = 362,880 possibilities speeds us up by the factor 1,440.
Even checking that 45+c+e+g is divisible by 4 is rather simple.

Thus here's a program for the HP-42S that lists possible tuples "c:d:e:f:g".
You have to weed some of them out though.
But that's still easier than doing the whole calculation manually.

Code:
Spoiler alert! 9 STO 00 LBL 00 9 STO 01 LBL 01 9 STO 02 LBL 02 RCL 01 RCL 02 X≤Y? GTO 09 + RCL+ 00 45 + 4 ÷ RCL- 00 ENTER IP X≠Y? GTO 09 RCL-02 X<>Y RCL- 01 CLA ARCL 01  ⊦":" ARCL ST X  ⊦":" ARCL 00  ⊦":" ARCL ST Y  ⊦":" ARCL 02 AVIEW LBL 09 DSE 02 GTO 02 DSE 01 GTO 01 DSE 00 GTO 00

Make sure to have the display mode set to ALL.

This will lead to a list like this:

6:2:9:0:8 → discard since f=0 is not valid
5:3:9:-1:9 → discard since f=-1 is not valid
4:3:9:1:6 → this is a valid solution
...

Cheers
Thomas
07-26-2018, 06:16 PM (This post was last modified: 07-26-2018 07:21 PM by Albert Chan.)
Post: #13
 Albert Chan Senior Member Posts: 2,516 Joined: Jul 2018
RE: July 2018 little math problem
(07-26-2018 03:42 AM)Thomas Klemm Wrote:
(07-26-2018 12:16 AM)Albert Chan Wrote:  If using computer is allowed, I would use Picat Programming Language
Interesting. Never heard of that language.

Picat is a declarative language, based on B-Prolog.
All you need is to describe the problem, and it take care of the rest.

Using symmetry, sum constraint, the program now run much faster.
Picat solved a 9-sided zigzag under 2 minutes: 33452 * 8 = 267616 solutions.

If result saved to file, Picat only take 51 seconds.

My computer pre-dated Win-XP, so is not fast (I later upgraded Win-XP on it)
My guess is Picat does not go brute force by visiting all permutations ...

Code:
import cp.                  % zigzag9.pi, all 9 sides sum to same S main => go, fail; true. go => Vars = [A1, A2, A3, A4, A5, A6, A7, A8, A9, A10,               A11, A12, A13, A14, A15, A16, A17, A18, A19],       Vars :: 1..19,        % zigzag with 9 sides       Total := 19 * 10,     % sum(Vars)       all_different(Vars),              A1 #< A2,             % 2X solutions by swap head pairs       A18 #< A19,           % 2X solutions by swap tail pairs       A3 #< A17,            % 2X solutions by flip the zigzag            % sum of below equations, speed up by tightten constraint on S       Total + A3 + A5 + A7 + A9 + A11 + A13 + A15 + A17 #= 9*S,              A1 + A2 + A3 #= S,       A5 + A4 + A3 #= S,       A5 + A6 + A7 #= S,       A9 + A8 + A7 #= S,       A9 + A10 + A11 #= S,       A13 + A12 + A11 #= S,       A13 + A14 + A15 #= S,       A17 + A16 + A15 #= S,       A17 + A18 + A19 #= S,       solve(Vars),       writeln(Vars). % each solution is actually 8 (head swap, tail swap, flipping zigzag) % this should be the first solution (side sum to 30) % % [1,10,19,5,6,13,11,17,2,16,12,14,4,18,8,15,7,3,20,9]

Edit:
Symmetry reduce the problem to one eighth its size ...
07-26-2018, 10:45 PM
Post: #14
 Albert Chan Senior Member Posts: 2,516 Joined: Jul 2018
RE: July 2018 little math problem
I have solved the puzzle by hand (no calculator)

Code:
To reduce the permutations, I force c < g, and ignore the edges a, b, h, i (for now) This reduce permutations to at most 5! / 2 = 60 4 s = 45 + c + e + g     = (45 + 1+2+3) to (45 + 7+8+9)     = 51 to 69     = 52, 56, 60, 64, or 68 --> s = 13, 14, 15, 16, 17 To simplify further, as in tic-tac-toe, try center first (impossible e bracketed) For s = 13: c + e + g = 7 = [1] + [2] + 4 1(8)4(7)2 <-- ok For s = 14: c + e + g = 11  = [1] + [2] + 8  = [1] + [3] + 7  = 1 + 4 + 6  = 2 + 3 + 6  = 2 + 4 + 5 4(9)1(7)6 <-- ok 3 2(6)6 4(8)2(7)5 <-- ok 2(9)3(5)6 <-- ok 1 4(4)6 2 4(5)5 2 5(5)4 1 6(4)4 2(6)6 3 1(6)7(4)3 <-- ok 1(5)8(4)2 <-- ok For s = 15, c + e + g = 15 But s = 15 also imply c + d + e = 15, which imply d = g, thus s != 15 For s = 16: c + e + g = 19 = 2 + [8] + [9] = 3 + [7] + [9] = 4 + 6 + 9 = 4 + 7 + 8  = 5 + 6 + 8 8(6)2(5)9 <-- ok 7(6)3(4)9 <-- ok 6(6)4 9 7 4(4)8 6(5)5 8 4(6)6 9 5(5)6 8 4(5)7(1)8 <-- ok 4(4)8 7 5(3)8(2)6 <-- ok 4(3)9(1)6 <-- ok For s = 17: c + e + g = 23 = 6 + [8] + [9] 8(3)6(2)9 <-- ok Add back missing digits to confirm above 12 cases. All confirmed ! Each solution actually represent 8 solutions, by head swap, tail swap and reverse the digits. SUM   SOLUTIONS ===   ========= 13    391847256 14    284917635 14    194827536 14    482935617 14    581674329 14    671584239 16    178625934 16    187634925 16    394571826 16    475382619 16    574391628 17    458362917
07-27-2018, 01:30 AM
Post: #15
 Valentin Albillo Senior Member Posts: 1,098 Joined: Feb 2015
RE: July 2018 little math problem
.
Hi, Albert Chan:

I'm on the very verge of going on a trip to start my summer vacations so I haven't had much time, if any, to devote to this nice problem by pier4r.

From the top of my head I just had the time to concoct a quik'n'dirty 6-lines of HP-71B code (main program) which calls another simple 6-line subprogram to perform an essentially brute-force search with a few refinements, which finds all solutions very quickly but I have no time to post it here right now, I must go.

Nevertheless, a cursory read of the already existing posts made me realize that yet another symmetry is lacking from all solutions so far (if I read the posts correctly, read them really fast).

Albert Chan Wrote:Add back missing digits to confirm above 12 cases. All confirmed ! Each solution actually represent 8 solutions, by head swap, tail swap and reverse the digits.

Close but no cigar. Actually there are only 6 primary solutions, not 12, each one of them representing 16 derived solutions, not 8.

You mention head swap, tail swap and reverse the digits but you missed 10's-complementing the digits:
• if (d1)(d2)...(d9) is a solution with sum S then (10-d1)(10-d2)...(10-d9) is a solution as well, with sum 30-S.
This halves the number of primary solutions from 12 to just 6, all the remaining 90 are directly derived from this 6.

Albert Chan Wrote:SUM SOLUTIONS
=== =========
13 391847256
14 284917635
14 194827536
14 482935617
14 581674329
14 671584239
16 178625934
16 187634925
16 394571826
16 475382619
16 574391628
17 458362917

Your first 6, say, can be considered the 6 primary solutions. But the remaining 6 are actually derived from them and so aren't primary. For instance, your first solution is:

13 391847256

and your last (12th) solution can be derived from it by simply 10-complementing it (and in your case, reversing the digits), like this:

[13, 391847256 ] -> [30-13, (10-3)(10-9)(10-1)...(10-2)(10-5)(10-6)] -> [17, 719263854]

and after reversing the digits we get: 17 458362917, which is your 12th solution indeed. In the same fashion you can derive your 11th solution from the 2nd primary, the 10th solution from the 3rd primary, and so on until deriving your 7th solution from the 6th primary.

Sorry but absolutely no time for more, will be back next September, have a nice summer.

Regards.
V.
.

All My Articles & other Materials here:  Valentin Albillo's HP Collection

07-27-2018, 03:06 AM (This post was last modified: 07-27-2018 12:23 PM by Albert Chan.)
Post: #16
 Albert Chan Senior Member Posts: 2,516 Joined: Jul 2018
RE: July 2018 little math problem
(07-27-2018 01:30 AM)Valentin Albillo Wrote:  your last (12th) solution can be derived from it by simply 10-complementing it (and in your case, reversing the digits), like this:

[13, 391847256 ] -> [30-13, (10-3)(10-9)(10-1)...(10-2)(10-5)(10-6)] -> [17, 719263854]

and after reversing the digits we get: 17 458362917, which is your 12th solution indeed.

Hi, Valentin,

Nice catch. That shorten my hand calculations by half. :-)

For this puzzle, center (sum = 15) has no solution, so N-complement symmetry has a clean cut.

But, if center has solution, and other symmetries are involved, it is hard.

A sure way is to build all the center solutions first, go through the list, and remove its N-complement.
Unfortunately, it may be hard to spot, possibly mask by other symmetry.

Each center solution has to check if it's N-complement equivalent had already shown.
That may be more trouble than it is worth ...

Note: zigzag side must have the same length, otherwise N-complement symmetry is gone.
07-27-2018, 08:20 AM
Post: #17
 cyrille de brébisson Senior Member Posts: 1,047 Joined: Dec 2013
RE: July 2018 little math problem
Hello,

Prime version: Brute force, executes in ~7s on my prime.

Code:
 Spoiler alert lstResult; export recurse(l, p) begin   local p1;   if (p>=6) then      p1:= l(1)+l(2)+l(3);     if (p==6) and (p1 <> l(3)+l(4)+l(5)) then return; end;     if (p==8) and (p1 <> l(5)+l(6)+l(7)) then return; end;     if p==9 then       if p1 == l(7)+l(8)+l(9) then print(string(l)+"->"+p1); lstResult(0):= l; end;       return;     end;   end;   for p1 from p to size(l) do     local l2= l;     l2(p):= l(p1); l2(p1):= l(p);     recurse(l2, p+1);   end; end; export mth() begin   lstResult:= {};   print("Executed in "+time(recurse(makelist(X, X, 1, 9), 1)));   print("found "+size(lstResult)+" solutions");   lstResult; end;

Cyrille

Although I work for the HP calculator group, the views and opinions I post here are my own. I do not speak for HP.
07-27-2018, 10:03 AM
Post: #18
 pier4r Senior Member Posts: 2,248 Joined: Nov 2014
RE: July 2018 little math problem
(07-26-2018 03:43 PM)Thomas Klemm Wrote:  But since $$s=a+b+c=c+d+e=e+f+g=g+h+i$$ and $$a+b+c+d+e+f+g+h+i=\sum_{k=1}^{9}k=45$$ we know that their sum is $$4s=45+c+e+g$$ which must be divisible by 4.
This reduces the possibilities further down to 60.

This was the same point I reached, then I worked on the multiples of 4. I was not expecting such an healthy thread (n1) for a problem apparently simple.

n1: thanks to this thread I also realize that even if someone posted already a super efficient solution, having other point of views - even with less efficient solutions - gives other perspective and increase the possibility to confront/compose ideas. Thus making the thread more enjoyable.

Wikis are great, Contribute :)
07-27-2018, 03:37 PM (This post was last modified: 07-27-2018 03:41 PM by Albert Chan.)
Post: #19
 Albert Chan Senior Member Posts: 2,516 Joined: Jul 2018
RE: July 2018 little math problem
Discover a way to add Complement Symmetry to solve zigzag puzzles.
Removing center solutions complement equivalent is hard, so the trick is ... not remove it !

This Picat program solve all zigzag puzzles, with sides > 2:
Each solution actually represent 8, by head swap, tail swap, or reversing digits.

Code:
import cp.                  % Usage: picat zigzag.pi [Sides = 4] main => main(4).            % Default: 4-sided zigzag main([Sides]) => main(to_integer(Sides)). main( Sides ) => Sides > 2, (zigzag(Sides), fail; true). zigzag(Sides) =>   N = 2*Sides + 1,          % number of numbers (always Odd)   A = new_list(N),          % unknown variables   A :: 1..N,   all_different(A),     A[1] #< A[2],             % 2X solutions by swap head pairs   A[N-1] #< A[N],           % 2X solutions by swap tail pairs   A[3] #< A[N-2],           % 2X solutions by flip the zigzag      C = N + 1,                % C-complement Symmetry   Center = C * 3 // 2,      % C-Complement Sum Center   S #<= Center,             % Symmetry with slight over-count      Total = N*(N+1) // 2,     % Speed-up by tighter constraint on S   Total + sum([A[I]: I in 3..2..N-2]) #= S * Sides,   foreach(I in 1..2..N-2)   % All sides sum to S     A[I] + A[I+1] + A[I+2] #= S   end,      solve(A),   writeln(A),      % Add C-Complement Symmetry Solution   S < Center, writeln([C-I: I in A]).

For a 4-sided zigzag: I still got 12, but Picat really solved only 6:
Complement Symmetry is internalized for a nice speedup.

[1,9,4,8,2,7,5,3,6]
[9,1,6,2,8,3,5,7,4]
[2,8,4,9,1,7,6,3,5]
[8,2,6,1,9,3,4,7,5]
[3,9,1,8,4,7,2,5,6]
[7,1,9,2,6,3,8,5,4]
[4,8,2,9,3,5,6,1,7]
[6,2,8,1,7,5,4,9,3]
[5,8,1,6,7,4,3,2,9]
[5,2,9,4,3,6,7,8,1]
[6,7,1,5,8,4,2,3,9]
[4,3,9,5,2,6,8,7,1]

I tried zigzag program with other sides:

Code:
Sides Time(s) solns x 8 3     0.12    56 4     0.12    96 5     0.12    480 6     0.18    1888 7     0.60    10688 8     3.71    46816 9     30.2    267616 10    263.    1502016
07-27-2018, 09:50 PM (This post was last modified: 07-27-2018 10:40 PM by Albert Chan.)
Post: #20
 Albert Chan Senior Member Posts: 2,516 Joined: Jul 2018
RE: July 2018 little math problem
Turns out, my not trying to untangle the complement symmetry was dead on.

If there are any solutions at the center, it is unlikely to reduce primary solutions in half.

While playing around with my zigzag.pi, I wanted to see if there is a simple way
to "cut" primary solution in half, as suggested by Valentin ... it cannot be done.

Code:
side  primary solutions at the center (sum = 3 * (side + 1)), all solutions is 8X 3     3 4     0 5     20 6     64 7     524 8     1186 9     7386 10    30746

3-sided zigzag is impossible to cut solutions in half. (3 is odd)

4-sided zigzag can apply complement symmetry because there is nothing in the center.
It is actually the exception case.

5-sided zigzag 20 center solutions can be reduced to 16, but not enough to cut in half.
 « Next Oldest | Next Newest »

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