资源预览内容
第1页 / 共48页
第2页 / 共48页
第3页 / 共48页
第4页 / 共48页
第5页 / 共48页
第6页 / 共48页
第7页 / 共48页
第8页 / 共48页
第9页 / 共48页
第10页 / 共48页
亲,该文档总共48页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
数学模型与游戏,2011年2月21日,过河问题是世界名题,有很多种说法。最早引进中国的是中国数学会第一届理事,扬州中学的数学教师陈怀书先生。后我国数学科普作家、哈军工大教授薛鸿达先生曾写过一篇专文渡河难题,对此进行了全面介绍。 我们将介绍三种不同的形式。,例1 商人们怎样安全过河,问题(智力游戏), 3名商人 3名随从,随从们密约, 在河的任一岸, 一旦随从的人数比商人多, 就杀人越货.,乘船渡河的方案由商人决定.商人们怎样才能安全过河?,问题分析,多步决策过程,决策 每一步(此岸到彼岸或彼岸到此岸)船上的人员,要求在安全的前提下(两岸的随从数不比商人多),经有限步使全体人员过河.,模型构成,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奇,左下移; 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名商人各带一随从的情况.,多步决策模型:,恰当地设置状态和决策, 确定状态转移律及目标(目标函数).,便于求解 (计算机编程等),在本问题中,可采取如下方法:一物在此岸时相应分量为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)可取运算:状态转移需经状态运算来实现。在实际问题中,摆一次渡即可改变现有状态。为此也引入一个四维向量(转移向量),用它来反映摆渡情况。例如 (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)的转移过程。,我们可以如下进行分析 :(第一次渡河),(第二次渡河),以下可继续进行下去,直至转移目的实现。上述分析实际 上采用的是穷举法,对于规模较大的问题是不宜采用的。,人在此岸 人在对岸 (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,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)。,注意不同于过河问题,此过程是不可逆的。共有八种不同的方案,可试着做一下。,德国著名的艺术家Albrecht Drer(1471-1521)于1514年曾铸造了一枚名为“Melencotia I”的铜币。令人奇怪的是在这枚铜币的画面上充满了数学符号、数字及几何图形。这里,我们仅研究铜币右上角的数字问题,所谓的魔方是指由1n2这n2个正整数按一定规则排列成的一个n行n列的正方形 。n称为此魔方的阶 。,Drer魔方:4阶,每一行之和为34,每一列之和为34,对角线(或反对角线)之和是34,每个小方块中的数字之和是34,四个角上的数字加起来也是34,什么是Drer魔方,多么奇妙的魔方!,铜币铸造时间:1514年,构造魔方是一个古老的数学游戏,起初它还和神灵联系在一起,带有深厚的迷信色彩。传说三千二百多年前(公元前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增长的速度实在是太惊人了!,同阶魔方的个数,定义:如果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方均可由这组基线性表示。,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=,可以证明, 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)对数字没任何要求所有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是大于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的小正方体,并按下图所示黑白相间地染色。,
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号