共有回帖数 0 个
-
幻方(MagicSquare)是最古老最流行的数学游戏之一,人类对于其研究也有几千年的历史,早在公元前173年,中国就已经出现了幻方模型的雏形,而最早描述三阶幻方构造法的是我国南宋时期的数学家杨辉,其在其《续古摘奇算法》一书中提及.
幻方的定义:
一个n阶幻方是由n^2个整数按下述方式组成n*n方阵:
该方阵每行,每列,以及两条对角线中每条对角线上的整数的和都相等,记这个和为S,通常的,我们称这个S为幻方的幻和.
在此我们仅讨论当n^2个整数为1,2,3...n^2时的情况.
很显然,一个n阶幻方中的所有整数的和为
1+2+3+...+n^2= ((n^2 + 1)*n^2)/2
而由于一个幻方共有n行,因而我们可以得到
幻和S= n(n^2 + 1)/2;
不难看出,任意两个n阶幻方都具有相同的幻和.
幻和S的计算公式是非常重要的一个基本公式,等下在很多分析中会用到.
接着,我自作主张的定义一个名词,幻性(Magic):
若在一个n阶方阵中,其某一行/列/对角线上的元素和等于该阶幻方的幻和,我们称此行/列/对角线具有幻性(Magic).
作此自作主张实在是不得已而为,由于手头能够搜集到的资料实在是太少,对于英文书籍中的Magic一词实在是没能找到官方的中译词,还望见谅,若大家有相关的资料,请务必发给我.不胜感激.
有了幻方的定义,如何构造一个n阶幻方也就显得尤为迫切,今天要做的事情,就是对主流的构造方法进行一些小小的分析,探索为何这些方法能够构造一个n阶幻方.
如果你对构造幻方有些了解,那么你肯定知道,对于构造幻方而言,当n=2m+1,2(2m+1),4m(m是某一非负整数)时构造的方法并不相同,某种程度上来说,一个比一个复杂.
P { margin-bottom: 0.21cm; }A:link { }
那么,我们首先来看最简单的幻方构造,当n=2m+1时.
这个构造方法想必也是最广为人知的方法,斜排法,其基本描述如下:
将整数1放在第一行的正中间的位置,其后的整数沿着自左下至右上的这条对角线按照自然顺序放置,但同时做出如下修正:
1.在到达顶行时,下一个整数要放在底行,所放位置就是把底行当作顶行上边一行时该数应该放在的位置.
2.当到达最右一列时,下一个整数要放在最左边的一列上,所放的位置就是把左边的一列当作最右边那列的右边列时该数应该放在的位置.
3.当要放的位置上已经填好了整数,或上一个整数已经放在了幻方的右上角时,则当前要摆的数放在紧挨上述位置的正下方.
例如以此法构造的五阶幻方如下:
17_24_1_8_15
23_5_7_14_16
4_6 _13_20_22
10_12_19_21_3
11_18_25_2_9
下面我们来分析一下,为何此法可以构造一个奇数阶的幻方(此法不能构造偶数阶幻方的原因很显然:你把1安置在哪里呢?).
细心分析可以发现,此法似乎仍然是每排列n个数(n阶幻方而言)即要执行一次”换行”,即构造法所要遵循的第三法则.由此我们做这样一个变换:
我们将每个整数”拆分”,对于n阶方阵,我们将其以n为基数进行拆分,即将某个数m拆分为如下形式:
m= kn + r; 其中k=0,0r=n;
那么上述五阶方阵拆分后的形式如下:
15+2_20+4_0+1_5+3_15+0
20+3_0+5_5+2_10+4_15+1
0+4_5+1_10+3_15+5_20+2
5+5_10+2_15+4_20+1_0+3
10+1_15+3_20+3_0+2_5+4
Itisamazing!这样一下子就体现出了此构造法的本质,他通过某种及其特殊的顺序排列1-n^2个数,使得在每行,每列,两条对角线上,0,n,2n...n^2以及1,2,3...n每个数仅出现一次,因而也恰到好处的保证了幻方所应该具有的幻性(Magic),为什么会这样?再回过头去观察”斜排法”的步骤,对于为什么”斜排”以及核心的”换行法则”细心分析,我想你会有所领悟.
事实上对于组合数学中关于”方”的构造有一定了解的人可能会发现,此构造法构造出的奇数阶幻方,实际上是0,n...n^2以及1,2,3...n这两组数的某个拉丁方(LatinSquare)以某种形式组合在一起,在这里就有了一个疑问,是否能由这两个拉丁方来得到此幻方的其他形式呢?答案是肯定的,不过今天我们仅仅探讨幻方的问题,对于拉丁方的探讨,如果大家喜欢,可以私信亦或是发邮件给我.zz940521@gmail.com.
说到这里,在利用幻方构造同阶幻方方面,其实还有一个更简单的方法.
如果用n^2+1-a替换n阶幻方中的每一个整数a,则可以得到一个新的幻方;
接下来我们来证明,替换之后方阵仍然是幻方.
任意选取一行(列与对角线证明类似),则有该行的元素和S1= (n^2+1)*n^2 - sigma(for every a in this row) = 2S - S = S;
由归纳法可知,对于任意一行/列/对角线,其元素和依然是幻和,因而此方阵仍然为幻方.
接下来我们探讨复杂一些的幻方构造,当n是偶数的情况.
由于直到现在,鄙人也没能搞定对于构造n=2(2m+1)的方法-RalphStrachey法-的正确性的证明,因此在此只给出构造方法,不提供理论证明,望海涵.若大家对于此法的证明有什么看法,可以给我留言.
首先我们来看当n=4m时的情况.
这种情况的构造方法,我们一般称之为”对称法”,其基本描述如下:
1.将1,2,3...n^2按照自然顺序依次排入一个n阶方阵中.
2.将n阶方阵以n/2为分界线分成四小块A,B,C,D.
3,将得到的四个小方阵按同样的方法再次分成四小块1,2,3,4.
如下图所视:
____这样我们就能得到一个4m阶的幻方了.下面来分析为何此构造方法是奏效的.
首先我们注意到,如果我们取某一行X(以下记做Xth,且不妨设0X=n/2),那么此行的关于中心中心对称的行应该是(n-X+1)th,我们称这两行为互补的(complementary),由于方阵是按照自然顺序排列的,我们不难得到Xth的元素和为 ((X-1)*n+1+X*n)*n/2 (考虑到Xth的第一个元素是(X-1)*n+1),因而其互补行的元素和为((n-X)*n+1+(n-X+1)*n)*n/2.
两式相加得到:((X-1)*n+1+X*n)*n/2+ ((n-X)*n+1+(n-X+1)*n)*n/2
_______________=(n^2+1)* n
将上式除以2,得到两式和的平均值,即(n^2+ 1) * n/2
也就是幻和.
因而,我们幻和值为S,由于S同样还是互补行和的平均,因而我们将两行的元素和相减,得到
((n-X)*n+1+(n-X+1)*n)*n/2- ((X-1)*n+1+X*n)*n/2
=n(n^2- 2Xn +2n)
则有Xth的元素和为S[x]= S - n(n^2 - 2Xn +2n)/2
其互补行的元素和为S[n-x+1]= S + n(n^2 - 2Xn +2n)/2
同一列上Xth与其互补行的元素之差为:
A= (n-X)n+1+c - (X-1)n-1-c = n^2-2x+1;其中c代表某一列的列号;
则有S[x]- S[n-x+1] = nA;
再结合上面的分析,我们可以看到,为了让互补行的元素和均为幻和,我们需要对调n/2个数,对于列也是如此,因而才有了算法中的中心对称的变换,而之所以选择分块的中间两块,是为了避免打乱了对角线上的元素,因为对角线已经满足了幻性(此留给读者自己分析).
楼主 2016-04-09 18:21 回复
Copyright © 2010~2015 直线网 版权所有,All Rights Reserved.沪ICP备10039589号
意见反馈 |
关于直线 |
版权声明 |
会员须知
