|
|
EXAMPLE
|
For n=2 the a(2)=12 solutions are:
[1, 4, 5, 2, 3] [2, 5, 1, 3, 4]
[1, 4, 5, 3, 2] [2, 5, 1, 4, 3]
[1, 5, 3, 2, 4] [3, 2, 5, 1, 4]
[1, 5, 3, 4, 2] [3, 4, 1, 2, 5]
[2, 3, 5, 1, 4] [4, 2, 3, 1, 5]
[2, 4, 3, 1, 5] [4, 3, 1, 2, 5]
The solution [1, 4, 5, 2, 3] is an encoding of the following labeling of P_2:
1 4 5 2 3
o-----o-----o
Vertices are labeled 1, 5, 3 while edges are labeled 4, 2 respectively; the magic constant of labeling h is 10 since h = 1+4+5 = 5+2+3. Notice that the author uses here the notation P_n for the path graph with n+1 vertices.
In general, for P_n the magic labeling constant h satisfies 3*(n+1) - floor(n/2) <= h <= 3*(n+1) + floor(n/2).
If n=2*k the lower bound for h is 5*k+3 and the following path graph has h=5k+3:
k+1 k+2 2k 2k+1
o o .. o o
\ /\ \ /
\ / \ \ /
o o .. o
1 2 k
Notice that the vertices labels are given by the perfect shuffle of [k+1..2k+1] and [1..k] while edge labels are 4k+1,4k,...,2k+2 respectively.
If n=2*k+1 the lower bound for h is 5*k+6 and the following path graph has h=5k+6:
1 2 k k+1
o o .. o o
| /| /| /|
|/ |/ |/ |
o o .. o o
k+2 k+3 2k+1 2k+2
Notice that the vertices labels are given by the perfect shuffle of [1..k+1] and [k+2..2k+2] while edge labels are 4k+3,4k+2,...,2k+3 respectively.
(End)
|
|
|
PROG
|
(Python)
from itertools import permutations
print("0", " ", "1")
print("1", " ", "3")
for j in range(5, 27, 2):
x = list(range(1, j+1))
sum2 = 0
for a in permutations(x):
x = list(a)
sum1 = x[0]+x[1]+x[2]
d = 1
for i in range(2, j-2, 2):
if (sum1== x[i]+x[i+1]+x[i+2]):
d = 1
else:
d = 0
break
if (d==1):
if (a[0]<a[j-1]):
sum2 = sum2+1
print((j-1)//2, " ", sum2)
(MiniZinc)
% filename: magicpn.mzn: generate solutions of size n
% usage: minizinc -a --soln-sep "" --search-complete-msg "" -D"n=5; " magicpn.mzn
include "globals.mzn";
int: n;
int: lo = 3*(n+1) - n div 2;
int: hi = 3*(n+1) + n div 2;
array[1..2*n+1] of var 1..2*n+1: x;
var lo..hi: h; % aka magic constant of labeling; lo/hi are tight bounds
constraint alldifferent(x);
constraint x[1] <= x[2*n+1];
constraint forall([h = x[2*i-1] + x[2*i] + x[2*i+1] | i in 1..n]);
solve satisfy;
output [show(x)];
|
