《游戏中的数学模型》由会员分享，可在线阅读，更多相关《游戏中的数学模型（48页珍藏版）》请在金锄头文库上搜索。
1、数学模型与游戏,2011年2月21日,过河问题是世界名题，有很多种说法。最早引进中国的是中国数学会第一届理事，扬州中学的数学教师陈怀书先生。后我国数学科普作家、哈军工大教授薛鸿达先生曾写过一篇专文渡河难题，对此进行了全面介绍。 我们将介绍三种不同的形式。,例1 商人们怎样安全过河,问题(智力游戏), 3名商人 3名随从,随从们密约, 在河的任一岸, 一旦随从的人数比商人多, 就杀人越货.,乘船渡河的方案由商人决定.商人们怎样才能安全过河?,问题分析,多步决策过程,决策 每一步(此岸到彼岸或彼岸到此岸)船上的人员,要求在安全的前提下(两岸的随从数不比商人多),经有限步使全体人员过河.,模型构成,
2、xk第k次渡河前此岸的商人数,yk第k次渡河前此岸的随从数,xk, yk=0,1,2,3;k=1,2,sk=(xk , yk) 过程的状态,S=(x , y) x=0, y=0,1,2,3; x=3, y=0,1,2,3; x=y=1,2,S 允许状态集合,uk第k次渡船上的商人数,vk第k次渡船上的随从数,dk=(uk , vk) 过程的决策,D 允许决策集合,uk, vk=0, 1, 2;k=1,2,sk+1=sk dk,+(-1)k,状态转移律,D=(u , v) u+v=1, 2,状态因决策而改变,穷举法 编程上机,图解法,状态s=(x,y) 16个格点,允许决策 移动1或2格; k奇
3、,左下移; k偶,右上移.,s1,sn+1,d1, d11给出安全渡河方案,允许状态,模型构成,模型求解,求dkD(k=1,2, n), 使skS, 并按转移律 sk+1=sk+(-1)kdk 由 s1=(3,3)到达 sn+1=(0,0).,问题归结为由状态 (3,3)经奇数次可取运算，即由可取状态到可取状态的转移，转化为(0,0)的转移问题。,商人和随从人数增加或小船容量加大;,商人们怎样安全过河,智力游戏,多步决策过程(数学模型),易于推广:,考虑4名商人各带一随从的情况.,多步决策模型:,恰当地设置状态和决策, 确定状态转移律及目标(目标函数).,便于求解 (计算机编程等),在本问题中
4、，可采取如下方法：一物在此岸时相应分量为1，而在彼岸时则取 为0，例如（1,0,1,0）表示人和鸡在此岸，而狗和米则在对岸。,（i）可取状态：根据题意，并非所有状态都是允许的，例如（0,1,1,0）就是一个不可取的状态。本题中可取状态（即系统允许的状态）可以用穷举法列出来，它们是： 人在此岸 人在对岸 (1，1，1，1) (0，0，0，0) (1，1，1，0) (0，0，0，1) (1，1，0，1) (0，0，1，0) (1，0，1，1) (0，1，0，0) (1，0，1，0) (0，1，0，1) 总共有十个可取状态，对一般情况，应找出状态为可取的充要条件。 （ii）可取运算：状态转移需经状态
5、运算来实现。在实际问题中，摆一次渡即可改变现有状态。为此也引入一个四维向量（转移向量），用它来反映摆渡情况。例如 （1，1，0，0）表示人带狗摆渡过河。根据题意，允许使用的转移向量只能有（1，0，0，0，）、（1，1，0，0）、（1，0，1，0）、（1，0，0，1）四个。,规定一个状态向量与转移向量之间的运算。规定状态向量与 转移向量之和为一新的状态向量，其运算为对应分量相加， 且规定0+0=0，1+0=0+1=1，1+1=0。 (解释),在具体转移时，只考虑由可取状态到可取状态的转移。问题化为： 由初始状态（1，1，1，1）出发，经奇数次上述运算转化为（0，0，0，0）的转移过程。,我们可以
6、如下进行分析 ：（第一次渡河）,（第二次渡河）,以下可继续进行下去，直至转移目的实现。上述分析实际 上采用的是穷举法，对于规模较大的问题是不宜采用的。,人在此岸 人在对岸 (1，1，1，1) (0，0，0，0) (1，1，1，0) (0，0，0，1) (1，1，0，1) (0，0，1，0) (1，0，1，1) (0，1，0，0) (1，0，1，0) (0，1，0，1),图解法,问题转化为求点(1,1,1,1)到点(0,0,0,0)的一条通路。,1,1,1,0,0,1,0,1,1,1,0,1,0,0,0,1,0,1,0,0,1,0,1,1,1,1,1,1,0,0,1,0,1,0,1,0,0,0,
7、0,0,例3：高塔逃生：铁匠海乔90，公主安娜50，侍女40，铁链30,原则：人下来时两个筐子必须都有人或铁链，并且重量相差10公斤。两个筐子装的总重量不超过170公斤。,转化：用向量表示状态:如(9,5,4,3)表示四者均在上面，(9,4)表示海乔和侍女在上面，其余在下面。从(9,5,4,3)开始，到(3)结束。,方案之一： 开始 铁链下去 侍女下去铁链上来 铁链拿到筐外 公主在下面可把铁链拿到筐里 (9,5,4,3) (9,5,4) (9,5,3) (9,5)(9,4)(5,4,3) (5,4) (5,3) (5)(4)(3)。,注意不同于过河问题，此过程是不可逆的。共有八种不同的方案，可
8、试着做一下。,德国著名的艺术家Albrecht Drer(1471-1521)于1514年曾铸造了一枚名为“Melencotia I”的铜币。令人奇怪的是在这枚铜币的画面上充满了数学符号、数字及几何图形。这里，我们仅研究铜币右上角的数字问题,所谓的魔方是指由1n2这n2个正整数按一定规则排列成的一个n行n列的正方形 。n称为此魔方的阶 。,Drer魔方：4阶，每一行之和为34，每一列之和为34，对角线（或反对角线）之和是34，每个小方块中的数字之和是34，四个角上的数字加起来也是34,什么是Drer魔方,多么奇妙的魔方！,铜币铸造时间：1514年,构造魔方是一个古老的数学游戏，起初它还和神灵联
9、系在一起，带有深厚的迷信色彩。传说三千二百多年前（公元前2200年），因治水出名皇帝大禹就构造了三阶魔方（被人们称“洛书”），至今还有人把它当作符咒用于某些迷信活动，大约在十五世纪时，魔方传到了西方，著名的科尼利厄斯阿格里帕（1486-1535）先后构造出了39阶的魔方 。,如何构造魔方,奇数（不妨n=5）阶的情况,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,你想构造Durer魔方吗？ 如何构成所有的Durer魔方？Durer魔方有多少？,魔方数量随阶数n增长的速度实在是太惊人了！,同阶魔方的个数,定义：如
10、果44数字方，它的每一行、每一列、每一对角线及每个小方块上的数字之和都为一确定的数，则称这个数字方为 Durer魔方。,R=C=D=S,仍以4阶方阵为例,其中：R为行和，C为列和，D为对角线和，S为小方块和,设D为所有满足R=C=D=S的Durer魔方的集合。,允许取相同的数字，并且允许数字在某个数域里任意取值。,A=,B=,类似于矩阵的加法和数乘，定义魔方的加法和数乘。 易验证，D 对加法和数乘封闭，且构成一线性空间。,记 M =所有的44数字方 ，则其维数为16。 而D是M的子空间，则D是有限维的线性空间。,根据线性空间的性质，如果能得到D的一组基， 则任一个Durer方均可由这组基线性表
11、示。,1在第一行中共有4种取法，为保持上述性质的成立，第二行中的1还有两种取法。当第二行的1也取定后，第三行与第四行的1就完全定位了，故一共可作出8个不同的最简方阵，称之为基本魔方并记之为Q1， ，Q8,R=C=D=S=1的方阵构成的线性空间具有什么样的性质？（这是非常必要的，因为我们一般取的是整数。）,类似于构造n维欧氏空间的标准基，利用0和1我们来构造一些R=C=D=S=1的最简单的方阵。,Durer魔方的维数和生成集,由 0,1 数字组合，构造所有的R=C=D=S=1的魔方。共有8 个，记为Qi, i=1,2,8。,Q1=,Q2=,Q3=,Q4=,Q5=,Q6=,Q7=,Q8=,可以证明
12、， Drer空间（简称D空间）中任何一个元素都可以用Q1，Q2，Q8来线性表示，但它们能否构成D空间的一组基呢？,等号两边对应元素相比较，得r1=r2=r7=0， 所以 是线性无关,是D空间的最小生成集。,令D即解方程组：,=,解得 D=8Q18Q27Q36Q42Q53Q64Q7,研究Albrecht Drer铸造的铜币,D空间的子空间和D空间的扩展,（1）要求数字方的所有数都相等这是集合G=rE,rR，G是以G=E为基的一维向量空间,进一步讨论,（4）仅要求行和与列和相等得到10维向量空间基向量B=Q1，Q2，Q7，N1，N2，N3其中Q1，Q2，Q7是D的基，而,（5）对数字没任何要求所有
13、44数字方组成16维向量空间M基向量MB的元素应是标准基（即仅有一个 元素为1，其余元素均为0的阵）。,Botsch（1976年）证明了对于1与16之间的每一个数K，都存在K维的44方的向量空间,由上可知，有下式成立 ： （向量空间） （维数） 0 1 5 7 8 10 16,练习,完成下面的Durer方,R=C=D=S=30,R=C=D=S=100,证明： 采用反证法，设 ，其中p、q互素，则有 p2=2q2。因为2|p2，故2|p。记p=2p1，可得4p12=2q2 ，即 2p12=q2 ，故又有2|q，与p、q 互素矛盾。,例 证明 是无理数。,同样方法可以证明：若m是大于1的素数，n是
14、大于1的整数，则 必为无理数。,例1：拟用40块方形瓷砖铺设如下图所示的地面，但商店只有长方形瓷砖，其大小为方形的两块。问购买20块长方形瓷砖后，是否可能不裁开而直接铺好地面？,解 将图11.4中的(a) (b)黑白相间染色。,显然，如长方形瓷砖不裁开，只能用来复盖相邻的两格，故复盖的两格必为一白一黑。 图(a)中共有21个黑格和19个白格，故不可能直接铺好； 图(b)中黑白格各为20个，大家很容易找到直接铺设的方法。,铺瓷砖,证明: 显然有4|mn，故m、n中至少有一个为偶数，不妨 设n为偶数，将棋盘按列黑白相间染色，如下图 (a ) ，由于n为偶数，黑、白列的数目相同，故黑白格数相同，设各为2k个。,板块可以有许多种拼凑法，但容易看出，每一板块放 置的方向（称之为定向）只有八种可能的选择，如下图(b)所示。,容易看出，不论按什么方向放置板块，每一板块均盖住 奇数个黑格（1格或3格），故盖住棋盘的板块必有偶数个，从而，mn的棋盘必能被8整除。,例3：拟将一批尺寸为124的商品装入尺寸为666的正方体包装箱中，问是否存在一种装法，使装入的该商品正好充满包装箱。,解 将正方体剖分成27个222的小正方体，并按下图所示黑白相间地染色。,
