构造奇数阶超级幻方的两种方法
Two Approaches to Establish Ultra-Magic Squares of Odd Order
DOI: 10.12677/AAM.2021.109328, PDF, HTML, XML, 下载: 518  浏览: 774 
作者: 徐向东:乌兰察布职业学院,内蒙古 乌兰察布
关键词: 幻方构造区组设计超级幻方正交拉丁方超级拉丁方Magic Square Structure Block Design Ultra-Magic Square Orthogonal Latin Square Ultra-Latinsquare
摘要: 幻方是组合数学区组设计研究的一个新领域,与正交拉丁方存在天然联系。构造奇数阶超级幻方具有诸多约束条件,引起研究者兴趣。分别利用两个正交奇数阶超级拉丁方和中国象棋马步及兵步结合的排序方式,给出了两种构造奇数阶超级幻方的方法。在文末给出5,7,9阶超级幻方的例。
Abstract: Magic square is a new field of combinatorial block design, which has a natural relationship with orthogonal Latin square. The construction of odd order ultra-magic square has many constraints, which attracts the interest of researchers. Using two orthogonal odd order ultra-Latin squares and the combination of the Chinese chess horse and pawn steps, led to two methods of constructing odd order ultra-magic squares. At the end of the paper, we give examples of ultra-magic square of order 5, 7, 9.
文章引用:徐向东. 构造奇数阶超级幻方的两种方法[J]. 应用数学进展, 2021, 10(9): 3141-3147. https://doi.org/10.12677/AAM.2021.109328

1. 引言

幻方(又称纵横图)及其构造研究在我国传统数学中是一个重要课题,历史悠久,成果丰富。洛书是世界上最古老的三阶幻方,起源于中国。 [1] 在学界颇有影响的美国学者著《组合数学》说:“组合数学,也称组合分析或组合学,是一门起源于古代的数学学科,据传说中国皇帝禹(约公元前2200年)在一个神龟的背上观察到纵横图,大约公元前1100年,排列开始在中国萌芽……” [2] 三阶幻方配置九个数字的均衡性、完美性。产生了一种审美的效果,使得古人认为其中包含了至高无上的原则,因而,最早出现的幻方,既是古代数学的杰作,也是具有哲学意义的创造。

数学发展到今天,有人觉得幻方只是数字游戏,不足以登大雅之堂,但伴随着计算机科学和人工智能的发展,人们吃惊地发现,这些古老的数学问题,包含着早期的排列、配置、对称、均衡、集合,以及分类原则、约束条件、序关系等非常深刻的内容,其数学思想熠熠生辉。现代离散数学中,把幻方问题归于计数、组合设计、图论、人工智能的领域,随着研究的深入,又给它找到了新含义、新应用,进入了数学研究的新领域。

所谓区组设计(Block design,简写为BD)是组合数学一个分支,解决按照规定的要求或条件来安排、配置一定事物的问题。洛书(三阶幻方)即最古老的区组设计。

拉丁方(Latin Square)是用n个不同的拉丁字母排成nn列的方阵,若每行每列的字母既无重复、也无遗漏,就称为一个n阶拉丁方。因扑克牌中16张J、Q、K、A可排成4阶拉丁方而闻名,被认为是中世纪西方的发明;但实际上早在战国时代,我国先民就在构造玄戈占星表时构造出世界上第一个拉丁方。 [3] 拉丁方发展为正交拉丁方,成为BD的一个基本内容,数学家欧拉(L. Euler, 1707~1783)提出著名的三十六军官问题就是六阶正交拉丁方的存在性问题。区组设计有重要应用,如1930年美国数学家费舍尔(R. A. Fisher, 1890~1962)将正交拉丁方用于实验设计;1983年我国组合数学家陆家羲证明了百余年的“大集定理”是BD的基本定理,获得1989年国家自然科学奖一等奖,也利用了正交拉丁方的性质。

幻方的编制程序被收入美国电脑协会主编的CACM程序汇编中。有建筑学家发现幻方的对称性质极为丰富,其中有许多美丽的图案,可用于轻工业品、封面包装等设计。加拿大滑铁卢大学的学者发现拉丁方与幻方的内在联系,《现代代数及其应用》 [4] 把幻方列为专门题材。幻方与双随机矩阵相关,受到组合数学家的关注,双重幻方 [5] (double magic square,每行、列、对角线之和为定值,其积亦为定值)、完全幻方(又称纯幻方,泛对角线幻方等,将幻方平面卷成圆筒使首列与末列相接,这时任一对角线都可视为主对角线,其和皆与纵列、横行之和相等)、素数幻方、广义幻方、幻体等都由它推广而来。

超级幻方(定义见下文)具有十分迷人的数学性质,与上述幻方、平方幻方、实数幻方以及富兰克林幻方等一样,派生性强,颇具吸引力。幻方和拉丁方关系密切,都是区组设计的传统内容,但幻方的重要性还没有引起足够重视。本文以线性代数为手段构造超级幻方,获得区组设计的成果,在计数理论和密码学领域,可望找到新的应用。

2. 奇数阶超级幻方的定义和分类

幻方是组合数学区组设计研究的一个新领域,与正交拉丁方存在天然联系。偶数阶幻方构造法较易,成果很多;奇数阶超级幻方的构造具有诸多约束条件,比较复杂,引起研究者兴趣,已找到某些方法。本文另辟蹊径,提出两种构造方法。

李立把奇数阶幻方分为3类:6m − 1阶,6m + 1阶,6m + 3阶幻方 [6] ,(这里m为正整数)。

定义1 所谓超级幻方,就是把自然数数列{n2} (数列 { 1 , 2 , 3 , , n 2 } 的简写)这n2个数排成nn列的

方阵 M n = ( m k , j ) n × n ,每行每列,每条对角线及每条泛对角线的和都等于一个定值 μ = n 2 ( n 2 + 1 ) ,并且还

满足任意与幻方中心对称的两个数之和都等于一个定值 ν = n 2 + 1 。 [7] 即幻方Mn满足如下条件(1)~(5):设{n}表示数列 { 1 , 2 , 3 , , n }

k = 1 n m k , j = μ , j = { n } (1)

j = 1 n m k , j = μ , k = { n } (2)

k = 1 n m k , k j + 1 n = μ , j = { n } (3)

k = 1 n m k , j k n = μ , j = { n } (4)

其中 k n 为{n}中的元素, 0 n = n n n = n ,当 0 < k < n 时, k n = k

k n = n k mod n n + k n = k

m k , j + m n + 1 k , n + 1 j = ν (5)

3. 构造奇数阶超级幻方

本文规定排列 S = ( n 1 , n 2 , , 2 , 1 , 0 ) ,逆排列 S 1 = ( 0 , 1 , 2 , , n 1 )

S 2 = ( [ 0 ] n , [ 2 ] n , [ 4 ] n , , [ 2 ( n 1 ) ] n ) S 3 = ( [ 0 ] n , [ 3 ] n , [ 6 ] n , , [ 3 ( n 1 ) ] n )

S 2 = ( [ 2 ( n 1 ) ] n , [ 2 ( n 2 ) ] n , , [ 2 ] n , [ 0 ] n ) S 3 = ( [ 3 ( n 1 ) ] n , [ 3 ( n 2 ) ] n , , [ 3 ] n , [ 0 ] n )

(其中 [ k ] n k mod n )。

定义2 一个每行、每列都分别由数列S−1中n个不同的数字组成的n阶拉丁方,如果满足条件(1)~(5),

即每行、每列及每条对角线和泛对角线的n个数字之和均为同一定值 L = n 2 ( n 1 ) ,并且满足任意与拉丁

方中心对称的两个数之和等于定值 l = n 1 ,则称此拉丁方为n阶超级拉丁方。如果两个n阶超级拉丁方是正交的,称之为一对正交超级拉丁方。

定理1 利用一对奇数阶正交超级拉丁方,可以构造奇数阶超级幻方。

首先构造一对正交超级拉丁方。

x k = ( x 1 , x 2 , , x n ) T x 1 = k 的S-循环排列。(T表示转置), x k i = ( x 1 i , x 2 i , , x n i ) T

x 1 i = k S i -循环排列。(其中 i = 1 , 2 , 3 , 2 , 3 )还是S中的n个元素。当 n = 6 m ± 1 时,

令矩阵 A n = ( x [ 0 ] n , x [ 2 ] n , x [ 4 ] n , , x [ 2 ( n 1 ) ] n ) ,则显然An为n阶拉丁方。

n = 6 m 1 时,令 B n = ( x [ 3 m ] n , x [ 3 ( m + 1 ) ] n , x [ 3 ( m + 2 ) ] n , , x [ 3 ( 7 m 2 ) ] n ) ,则显然Bn为n阶拉丁方。

n = 6 m + 1 时,令 B n = ( x [ 3 m + 1 ] n , x [ 3 ( m + 1 ) + 1 ] n , x [ 3 ( m + 2 ) + 1 ] n , , x [ 3 ( 7 m ) + 1 ] n ) ,则显然Bn为n阶拉丁方。

n = 6 m + 3 时,设逆排列 S 1 = ( 0 , 1 , 2 , , n 1 ) = ( t 0 , t 1 , t 2 , , t n 1 ) ,引进变换

C S 1 : t 1 c 2 , t 2 c 1 , t 6 m c 6 m + 1 , t 6 m + 1 c 6 m , t 6 k 2 c 6 k , t 6 k c 6 k 2 , ( 1 k m )

t i c i , ( i 1 , 2 , 6 m , 6 m + 1 , 6 k 2 , 6 k , ( 1 k m ) , i S 1 )

C = ( c n 1 , c n 2 , , c 1 , c 0 ) ,为 S 1 的一个对称变换,满足

i = 1 2 m + 1 c 3 ( i 1 ) = i = 1 2 m + 1 c 3 i 2 = i = 1 2 m + 1 c 3 i 1

y k = ( y 1 , y 2 , , y n ) T y 1 = c k 的C-循环排列。令矩阵

A n = ( y [ 0 ] n , y [ 2 ] n , y [ 4 ] n , , y [ 2 ( n 1 ) ] n ) B n = ( y [ 3 m + 2 ] n , y [ 3 ( m + 1 ) + 2 ] n , y [ 3 ( m + 2 ) + 2 ] n , , y [ 3 ( 7 m + 2 ) + 2 ] n )

显然,当n为奇数时(n > 3),An和Bn为一对正交n阶拉丁方。当n为奇数时(n>3),

M n = n A n + B n + E n (其中En为元素全为1的n阶方阵),则Mn是n阶超级幻方。

4. 奇数阶超级幻方的证明

定理1的证明:首先证明当 n = 6 m ± 1 时,An是满足条件(1)~(5)的超级拉丁方。

x k x k i 分别表示 x k x k i 中n个元素之和,( i = 1 , 2 , 3 , 2 , 3 )

令上面构造的一对正交拉丁方分别为 A n = ( a k , j ) n × n B n = ( b k , j ) n × n L = n 2 ( n 1 ) l = n 1

A(1): k = 1 n a k , j = x [ 2 ( j 1 ) ] n = L , j = { n } (6)

A(2): j = 1 n a k , j = x [ n k + 1 ] n 2 = L , k = { n } (7)

A(3): k = 1 n a k , k j + 1 n = x [ n j + 1 ] n = L , j = { n } (8)

A(4): k = 1 n a k , j k n = x [ 2 n j 1 ] n 3 = L , j = { n } (9)

(9)式左端各条对角线的起始元素和右端同一条相应对角线的起始元素并非一一对应,但总和相等。

A(5): a k , j + a n + 1 k , n + 1 j = l , k = { n } , j = { n } (10)

其次证明当 n = 6 m 1 时,Bn是满足条件(1)~(5)的超级拉丁方。

B(1): k = 1 n b k , j = x [ 3 ( m + j 1 ) ] n = L , j = { n } (11)

B(2): j = 1 n b k , j = x [ 3 m k + 1 ] n 3 = L , k = { n } (12)

B(3): k = 1 n b k , k j + 1 n = x [ 3 m j + 1 ] n 2 = L , j = { n } (13)

B(4): k = 1 n b k , j k n = x [ 3 ( 7 m 2 ) j + 1 ] n 3 = L , j = { n } (14)

(14)式左端各条对角线的起始元素和右端同一条相应对角线的起始元素并不是一一对应的,但是总和是相等的。

B(5): b k , j + b n + 1 k , n + 1 j = l , k = { n } , j = { n } (15)

类似可得,当 n = 6 m + 1 时,Bn是满足条件(1)~(5)的超级拉丁方。

n = 6 m + 3 时,类似可得,An和Bn为分别满足条件(1)~(5)的一对正交超级拉丁方。

以A(1)为例,

k = 1 n a k , j = y [ 2 ( j 1 ) ] n = L , j = { n } (16)

特别地,

B(2): j = 1 6 m + 3 b 3 k 2 , j = 3 i = 1 2 m + 1 c 3 i 1 = L , k = { 2 m + 1 } (17)

j = 1 6 m + 3 b 3 k 1 , j = 3 i = 1 2 m + 1 c 3 i 2 = L , k = { 2 m + 1 } (18)

j = 1 6 m + 3 b 3 k , j = 3 i = 1 2 m + 1 c 3 ( i 1 ) = L , k = { 2 m + 1 } (19)

最后证明 M n = n A n + B n + E n 是满足条件(1)~(5)的超级幻方。

M(1):

k = 1 n m k , j = k = 1 n ( n a k , j + b k , j + 1 ) = n k = 1 n a k , j + k = 1 n b k , j + n = ( n + 1 ) L + n = μ , j = { n } (20)

类似可得,M(2)~M(5)。故,Mn是奇数阶超级幻方。

5. 奇数阶超级幻方的另一种构造方法

n = 6 m + 3 时,对于集合C,引进变换 D : d i = c i 1 + 1 , ( i = { n } )

令排列 D = ( d 1 , d 2 , d 3 , , d n ) ,满足 i = 1 2 m + 1 d 3 i 2 = i = 1 2 m + 1 d 3 i 1 = i = 1 2 m + 1 d 3 i

下面是利用连续摆数法,采用中国象棋马步和兵步[记为 H ( k + 2 , j + 1 ) + S ( k 1 , j ) 步],构成 n = 6 m + 3 阶超级幻方的过程。

首先将自然数数列{n2}按顺序从上到下,从左到右排成nn列方阵

Z n = ( z 1 , z 2 , , z n ) ,其中 z i = ( i , i + 1 , i + 2 , , i + n 1 ) T (T表示转置)

称为自然数序列n阶方阵。其次对Zn进行行列编码的同步变换:

Q i = ( 0 , 0 , 0 , , e d 3 i 2 , e d 3 i 1 , e d 3 i , , 0 , 0 , 0 ) n , ( i = { 2 m + 1 } )

其中ek为第k个分量为1,其余分量皆为0的单位向量。

F n = i = 1 2 m + 1 j = 1 2 m + 1 Q i T Z n Q j 。设 F n = ( f k , j ) n × n ,又设 M n = ( m k , j ) n × n

设排列 V = ( n n , 2 n , 4 n , , 3 n 2 n ) = ( v 1 , v 2 , v 3 , , v n )

W = ( n + 1 2 n , n + 3 2 n , n + 5 2 n , , 3 n 1 2 n ) = ( w 1 , w 2 , w 3 , , w n )

接着引进变换: I V = V I W = W I V : I v i = v i ; I w : I w i = w i , ( i = { n } )

P V : P v 1 = v n 1 n , P v i = v i 1 1 n , ( { i = { 2 , 3 , , n } )

P j V = P ( P j 1 V ) , P 0 V = I V , ( j = { n } )

H W : H w i = w i 1 , H w 1 = w n , ( i = { 2,3, , n } )

H j W = H ( H j 1 W ) , H 0 W = I W , ( j = { n } )

做变换: f k , j m P j 1 v k , H j 1 w k , ( k = { n } , j = { n } ) ,于是Mnn阶超级幻方。

以M9的构造过程为例,首先将自然数序列方阵Z9进行行列编码的同步变换,Z9→F9,然后从m9,5开始按中国象棋马步[ H ( k + 2 , j + 1 ) 步]排列F9的第一列“1,3,2,6,5,4,8,7,9”,此时“3”已在方阵M9的最下边之外的2行上,可将方阵M9上下两边连成一圆筒,则“3”按马步走,放在m2,6的位置上,接着排列“2,6,5,4”,此时“4”已在M9的最下边与最右边之外的格子上,可将方阵上下两边连成一圆筒,再将左右两边连成一圆筒,于是“4”摆放在m1,1的位置上,接着按照马步继续摆放“8,7,9”,F9的第一列已排完;从“9”到“19”(F9第二列第一个数),按中国象棋兵步[ S ( k 1 , j ) 步]排列(兵步称为列与列之间的过渡步);F9第二列从“19”到“27”均用马步排列,马步称为内连续步;一直排到F9的最后一个数“81”。就得到一个9阶超级幻方M9。用同样的方法可以构造15阶,21阶, ,6m + 3阶超级幻方。

n = 6 m ± 1 时,设自然数序列方阵 Z n = ( z k , j ) n × n ,直接做变换:

z k , j m P j 1 v k , H j 1 w k , ( k = { n } , j = { n } )

于是Mnn阶超级幻方。

n为奇数(n > 3)时,将上述构造的的所有元素都减“1”,得到一个新的方阵 M n 1 ,将 M n 1 的每个元素按n进位,就得到两位数[高位数和低位数,其中 0 , 1 , 2 , , n 1 表示为 00 , 01 , 02 , , 0 ( n 1 ) ],其中高位数方阵就是An,是一个超级拉丁方;低位数方阵就是Bn,也是一个超级拉丁方,而且An和Bn正交。

于是, M n = n A n + B n + E n ,(其中En为所有元素全为“1”的n阶方阵)是n阶超级幻方。两种构造方法是殊途同归的。

6. 奇数阶超级幻方举例

以下是据所述方法构造的5阶,7阶,9阶超级幻方及正交超级拉丁方示例。

M 5 = ( 4 12 25 8 16 23 6 19 2 15 17 5 13 21 9 11 24 7 20 3 10 18 1 14 22 ) A 5 = ( 0 2 4 1 3 4 1 3 0 2 3 0 2 4 1 2 4 1 3 0 1 3 0 2 4 ) B 5 = ( 3 1 4 2 0 2 0 3 1 4 1 4 2 0 3 0 3 1 4 2 4 2 0 3 1 )

M 7 = ( 5 15 32 49 10 27 37 46 14 24 41 2 19 29 38 6 16 33 43 11 28 30 47 8 25 39 3 20 22 39 3 20 30 44 12 21 31 48 9 26 36 4 13 23 40 1 18 35 45 ) A 7 = ( 0 2 4 6 1 3 5 6 1 3 5 0 2 4 5 0 2 4 6 1 3 4 6 1 3 5 0 2 3 5 0 2 4 6 1 2 4 6 1 3 5 0 1 3 5 0 2 4 6 ) B 7 = ( 4 0 3 6 2 5 1 3 6 2 5 1 4 0 2 5 1 4 0 3 6 1 4 0 3 6 2 5 0 3 6 2 5 1 4 6 2 5 1 4 0 3 5 1 4 0 3 6 2 )

M 9 = ( 4 18 38 67 81 20 49 36 56 77 25 48 32 61 3 14 43 66 60 8 10 42 71 73 24 53 28 65 76 27 47 31 63 2 13 45 30 59 7 12 41 70 75 23 52 37 69 80 19 51 35 55 6 17 54 29 58 9 11 40 72 74 22 16 39 68 79 21 50 34 57 5 26 46 33 62 1 15 44 64 78 ) A 9 = ( 0 1 4 7 8 2 5 3 6 8 2 5 3 6 0 1 4 7 6 0 1 4 7 8 2 5 3 7 8 2 5 3 6 0 1 4 3 6 0 1 4 7 8 2 5 4 7 8 2 5 3 6 0 1 5 3 6 0 1 4 7 8 2 1 4 7 8 2 5 3 6 0 2 5 3 6 0 1 4 7 8 )

B 9 = ( 3 8 1 3 8 1 3 8 1 4 6 2 4 6 2 4 6 2 5 7 0 5 7 0 5 7 0 1 3 8 1 3 8 1 3 8 2 4 6 2 4 6 2 4 6 0 5 7 0 5 7 0 5 7 8 1 3 8 1 3 8 1 3 6 2 4 6 2 4 6 2 4 7 0 5 7 0 5 7 0 5 )

参考文献

[1] 罗见今. 世界上最古老的三阶幻方——关于组合学起源的讨论[J]. 自然辩证法通讯, 1986(3): 49-57+80.
[2] Ryser, H.J. (1962) Combinatorial Mathematics. The Mathematics of America, New York.
[3] 罗见今. 睡虎地秦简《日书》玄戈篇构成解析[J]. 自然辩证法通讯, 2015, 37(1): 65-70.
[4] Gibert, W.J. (1976) Mordern Algebra with Application. John Wiley & Sons, New York.
[5] 梁培基. 双重幻方[J]. 数学研究与评论, 1982(2): 14.
[6] 李立. 6m ± 1阶全对称幻方的一些构造方法[J]. 内蒙古大学学报(自然科学版), 1985, 16(2): 143-169.
[7] Chan, C.-Y.J., Mainkar, M.G., Narayan, S.K., et al. (2014). A Construction of Regular Magic Squares of Odd Order. Linear Algebra and Its Applications, 457, 293-302.
https://doi.org/10.1016/j.laa.2014.05.032