第25题磨光变换

《第25题磨光变换》由会员分享，可在线阅读，更多相关《第25题磨光变换（8页珍藏版）》请在装配图网上搜索。

1、第25题磨光变换画一个圆，沿圆周均匀放上8个围棋子，放法随机，然后按以下规 则调整。 若原来相邻两棋子颜色相同，贝恠它们所在孤的中点处放上一个 黑子。(2) 若原来相邻两棋子颜色相异，则在它们所在弧的中点处放上一个 白子。(3) 上述操作完毕后，取走原先放着的 8个棋子。调整后得到沿圆周均匀分布的新的 8个棋子。问：能否经过有限次调整后，使 8个棋子全部都成黑子？若行，则 至多要调整几次。分析：先特例探索图 25-1图25-1是经过8次调整后使8个棋子全部都变成黑子的特例。经过多次尝试后发现：每次尝试都能经过不多于8次调整后，使8个棋子全部变成黑子。由此产生了如下猜测：对任一种放法都可经过不多

2、于8次调整后，使8个棋子全部变成黑 子。如何判别上述猜测的真伪呢？因为不同分布是有限的，至多不超过 28即256种，所以我们可以采 用穷举法，列举所有可能放法，一一验证。这种方法可行，但工作量很 大。是否还有更简便的方法，利用一些数学工具，将这个问题转化为一 个数学问题呢？倘若能建立起黑、白子与特定的2个数字间的对应，使调整后的结 果与对应数字的相应运算结果相对应。那么黑白子的调整可以转化为对 应数字的运算。从而可以通过数字运算来解决原有问题。经过联想与对比发现只要将黑子与 1对应，白子与-1相对应，即黑 子一- 1;白子一- -1那么黑白子的变换就相当于对土 /进行乘法运算。正如下表所示:变

3、换黒白黑白白白黑对应以上对应就将原问题转化成一个数学问题。解：先建立集合黑子，白子与集合-1,1间对应黑子一- 1白子一- -1那么黑白子的调整可转化成对应数字的乘法运算。设第一次均匀放置在第i位上的棋子对应数为xi(i=1，2, 3, 4, 5,6, 7, 8)，则 Xi -1, 10用表药门表示各次棋子调整状态对应数(在岀现时，因为故省略不写 k = 1, 2, 3f 4, 5, 6, 7, 8)表25 1状态i234初始态xix2网策一次调整态丸緬沁昭5第二欢调整老第三次调整态第四坎週整臺第五次调整态屯轡那1调整倉第七次调整态IlXii-l 1认i1-1 1仏ii_i 1认i1 1第八次

4、调整恵1111续表置状态、5678初赔态x7策一次调整态哪1第二校调整窸叽第三次调楚态施勺勺第四次调整恳歹1第五次凋整态i x51x2巧停3嗨第六次调整态切陶花陶V3X5X7第七次调整悲TTjT ii 1nnrUL 111 XjJIU XjUL 1第儿次调整态11118由上表可知：不管初始状态如何，至多经过 8次调整后能使8子变 成全黑。回顾：从上表中还可以得到以下结论：(1) 经过七次调整后，必成同色；(2) 经过六次调整后，必成同色或黑白相间。此外能利用上表构造经过3次至6次调整变成全黑状态的实例。下面构造经六次调整成全黑状态的实例。要达到此目的，只要使第四次调整态为黑白相间状态。为此可取

5、Xi X5=X3 - X7 = 1，且 X2 X6=X4 X8=-1 ；于是可取 X2=X4二 1，Xl=X3=X5=X6=X7=X8=1。即当原始状态呈图25-2时，一定可以经过六次调整后，变成全黑状 态。團 25-2上述“调整”用数学术语来说就称作变换。若变换具有缩小差别达到平衡的性质，则称这种变换为“磨光变换”上述结论可表示成“当n=8时，变换是磨光变换”。这个问题是有它的实际背景的。很多自然现象都可以说是在进行某 种局部调整。例如水总是由高处向低处流；电子总是从高电位移到低电位。很多 自然现象都可通过局部调整来达到一种平衡状态。从而相应变换就具有“磨光”性质。上述问题是否可以从8子推广

6、到n子呢？即沿圆周均匀放n个不同 色的子，作相同变换，这时是否也具有磨光性质？我们需要分析：当 n 为何值时，肯定没有；当n为何值时，可能没有；当n为何值时，肯定 有。下面分两种情况进行讨论。(1)n为奇数时：当n=3时，原状态不同色时肯定不能磨光。于是，猜测n为奇数时，肯定不能磨光。实际上，由于初始态中既有黑子，又有白子所以经过一次变换，由 规则(2)可知仍有白子。又因为总的子数是奇数，原始状态不可能是黑白 相间的。故原始态中一定有同色子相邻的情况，经过一次变换，由规则(1) 可知仍有黑子。所以经过一次变换后的态图中仍有白子， 且不是全白 这一性质在变换过程中一直保持。因此 n为奇数时变换不

7、可能具有磨光 性质。(2)n为偶数时：不难证明n=2、4时，肯定能磨光。n=6时证明遇困难，于是我们设 法找反例。图25-3是n=6时，磨光的反例。因为第一次调整态图与第五次调整态图是对偶图 (即黑白色相反)， 所以第六次调整图同第二次调整图，第七次调整态图同第三次调整态 图，即出现循环，所以这一特例不能磨光。因为存在n=6时，可以磨光的特例。所以n=6时不一定能磨光。因此当n为偶数时也不一定能 磨光。是否存在特殊性质的偶数k，使n=k时一定能磨光呢？利用杨辉三角 形的性质，可以证明：当k=2m(m N)时一定能磨光。由于证明复杂这里就 不详加讨论。综上讨论可知：如果原始状态的n子不同色，那么

8、(1)当n为奇数时，一定不能磨光； 当n为2m(m N)型偶数时，一定能磨光；(3) 当n为不呈2m(m N)型偶数时，存在着不能磨光的可能。注：在解决这一问题过程中用1, -1所构成的集合，与它们间的乘法 这一数学结构，将原问题中的主要特征，主要关系抽象出来，归结成为 数学问题，然后通过解决该数学问题，从而解决原实际问题。这种利用 一定的数学结构来解决实际问题的方法，称为“数学模型的方法”。其 中所用的数学结构，称为数学模型。数学模型的方法简称MM&法(Mathematical Modelli ng Method) 。我们所学过的各种数学概念：如实数、函数、集合、各种方程、公 式都可以作为数

9、学模型。具体讲一次函数是匀速直线运动的数学模型。一般的正弦函数是简 谐振动的数学模型。二元一次方程是鸡兔同笼问题的数学模型。数学史上著名的“哥尼斯堡七桥问题”就是由著名数学家欧拉，用 数学模型方法解决的，并由此导致了新兴数学分支一一图论的诞生。18世纪，东普鲁士有个城市叫哥尼斯堡(即现在的加里宁格勒)，帕 瑞格尔河从城中穿过，河中有两个岛A与D,河上有七座桥连结这两个岛 及河的两岸B、C。如图25-4所示。图 25-4河中心的岛A上有一所古老的哥尼斯堡大学。每天傍晚，大学生总 要在这七座大桥之间散步。当时的大学生们热衷于解决这样二个难题：(1) 一个散步者能否经过每座桥恰好一次，既无重复也无遗

10、漏。能否经过每座桥恰好一次，并且最后能够回到原来出发点。大学生们百思不解，百试不成。写信求助于当时大数学家欧拉，1736 年欧拉终于解决了这个问题。欧拉运用的就是数学模型法。他先将七桥问题抽象化成为一个数学 问题。他把岛和陆地抽象成一个点，把桥抽象成一条线，从而将原来地图 抽象成图25-5图形。图 2S-5于是，原问题 转化成图25-5能否不重复地一笔画出来。原问题 转化成图25-5能否从某一顶点出发，不重复地一笔画出来，且最后又回 到起点。欧拉进一步考察一笔画问题时发现：一笔画总有起点和终点。它的 中途经过的点有进线必有相应出线，所以所有这样点必有偶数条线和其 它点相连，只有起点和终点可以例

11、外。为此一个图形可以一笔画成的必 要条件是与其他点有奇数条线相连的点只能 0个或2个。现图25-5中点 A、B、C D与其它点的连线都是奇数条。由此欧拉得出七桥问题(1)，(2) 都无解结论。七桥问题求解过程，可用框图表示如下：用数学模型方法解决问题的基本步骤为： 从实际问题中抽象出数学模型，将原问题归结为数学问题。(2) 在数学模型上进行推理或演算，求得数学问题的解。(3) 把研究数学模型所得结论返回实际问题中去进行检验、修正，直 至得到实际问题的解答。EJ 25-6團 25-7练习251证明n=8时，围棋子在圆周上的均匀随机分布有且只有 36种。2当n=8时，举出七次调整成全黑状态的特例。3原有糖块个数不相同的三个小孩围坐成一圈做游戏。规则是：通 过向阿姨至多要一块糖的方法变手中的糖块数为偶数，然后再折半分糖。 即每人把手中糖的半数分给自己的右邻，也从他的左邻手中接过他（她） 手中糖块数的一半。实施一次规则，则称进行一次“变换”。试问：这一变换能否磨光？若能给出证明，若不能请举出反例。