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,076 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 Member Posts: 222 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,447 Joined: Dec 2013
RE: July 2018 little math problem
I just used brute force.
Code:

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: 1,676 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: 739 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:

\<< 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: 1,676 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,447 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: 835 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:

\<<
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,076 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: 739 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: 835 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:

\<<
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,447 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:

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:

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:

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: 1,676 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:
Re-reading Thomas last post. My code had exactly the same idea.
Symmetry reduce the problem to one eighth its size ...
07-26-2018, 10:45 PM
Post: #14
 Albert Chan Senior Member Posts: 1,676 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: 777 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: 1,676 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:

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,076 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: 1,676 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: 1,676 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: 1 Guest(s)