一种最后拿牌游戏中数学原理的研究.doc

湖北大学本科毕业论文（设计）湖 北 大 学 本科毕业论文（设计）题 目 “最后拿牌”游戏中数学原理的研究姓 名 池新平 学 号 2006221104110045 专业年级 数学与应用数学2006级 指导教师 文胜友 职 称 教授 14目 录绪论 （1）1现实问题（1）2. 问题转化（1）3. 全集与变换（2）4. 初步分析与重排变换 （2）5. 变换变小性质 （3）6. 二元非零数组的结论（引理1） （3）7. 先必输集和后必输集 （4）8. 先必输集、后必输集和全集的关系 （5）9. 现实问题的解决 （6）10.三元非零数组的研究 （8）10.1. 集合A中从一元到三元数组的公式 （8）10.2. 三元非零数组排列的对称性 （9）10.3. 三元非零数组排列的方阵的结构 （11）11. 任意三元非零数组的归属性问题的确定 （12） 论文小结 （13）参考文献 （14） “最后拿牌”游戏中数学原理的研究摘要本文对生活中的一个与数字的排列及数组的变换等有关的小游戏,进行了较为细致和严谨的分析和研究.本文主要采用了把现实问题转化为数学问题,再运用化归思想和数学归纳法等数学方法对该问题进行一层一层的解剖、分析,最终解决了一元、二元和三元非0数组的归属性和任意数组的归属性问题.并着重研究了先必输集A中三元非0数组的性质,得到了该类数组满足的条件,解决了现实问题.【关键词】 数组 化归 字典排列法 数学归纳法 变换 重排 归属性 The Mathematics Principle Research in the Game “Finally Takes the Sign”Abstract This article has been carried on a research and analysis in a small game in our life carefully and rigorously, which is related to the digital arrangement and the array transformation. This article is carried on a dissection, the analysis to this question with mainly using the transformed the realistic question to mathematics question, the mathematics methods and some other reduction thought and mathematical induction. Finally we solved Yuan, dual and three Yuan non-0 arrays ownerships and the random array ownership question. And we study the three Yuan non-0 array nature in collection A “Who has had to lose first” emphatically, we get the satisfied condition of this kind of array, So we solve the realistic problem.【Key words】Array Reduction Dictionary arrangement Mathematical induction Transformation Rearrangement Ownership .绪论生活中我们经常会玩一些小游戏,像扑克牌什么的,善于思考的人便会发现,在很多游戏中,你可以发现一些规律.而本文正是由于作者在玩生活中的一个不知名的小游戏时,感觉其中必定有些玄机,而这玄机正好可以用数学知识加以解决,故而对这个小游戏进行数学方面的分析和研究.由于作者不知该游戏的名称,也查不到相关的信息,但为了方便叙述,作者根据该游戏的是要看是谁最后把几叠牌拿完这一特点,给这个游戏起名为“最后拿牌游戏”.目前作者暂时没查到国内外关于这个游戏及相关方面的研究,所以可供参阅的资料极少.而本文主要是根据作者大学期间所学的知识和自己的一些想法,对该问题进行一步步转化和分析来研究的.本文主要的数学思想方法是先采用了把现实问题转化为数学问题,再运用化归思想和数学归纳法等方法对该问题进行一层一层的解剖、分析,最终解决了一元、二元和三元非0数组的归属问题和任意数组的归属性的确定性问题.1现实问题甲乙两人玩游戏.甲拿出一些扑克牌,放成三叠（如下图1）,各叠的个数分别为：3、4、7,对乙说：我们两人交替在这三叠牌中拿牌,每人每次必须拿走同一叠中的一张或数张,这样,只要你先拿,不管你怎样拿,我都可以保证是你最后一次把这些牌拿走后,桌上一张牌也不剩. _ _ _ _ _ _ _ _ _ _ _ 第一叠 第二叠 第三叠 图1.1 2. 问题转化为了探索其中的奥秘,我们把它转化成一个数学问题：有一组数3、4、7,经过数次变化,每次变化只能减少一个数,并且减少后得到的数为不小于0的整数,这样得到一组新数.如3、4、7,把第一个数3减少成1,得1、4、7.再以这组新数按同样的规律变化,直到变成0、0、0 为止.我们现在要做的是如何控制偶数次的变化,来保证不论奇数次怎么变,最后是经过第奇次变化后,数组才变成0、0、0 .这样便可以保证不管先拿牌的人如何拿.后拿牌的人都可以使先拿的人拿走最后的牌.为了解决这一特殊问题,我们先用数组（a1,a2,an）表示将要拿牌的人面对的牌数为a1,a2,an.其中a1,a2,an均称为数组（a1,a2,an）的元.如果解决了一般的数组（a1,a2,an）,减少成(0,0,.,0)所用步数的确定的奇偶性问题,那这一特殊问题就好解决.3. 全集与变换我们把研究对象数组的全体定义为一个全集U=所有的数组（a1,a2,an）.从三叠牌的减少过程中我们发现,三叠牌慢慢的会减少成两叠,再减少成一叠,最后减少得一张也没有.即三个不为0的数会减少成两个不为0的数,再减少成一个不为0的数,最后减少成三个全为0 的数.故我们可以先从最简单的只有一个不为0的数入手.我们把数组的减少过程定义为一个数组的变换 ， 为将数组（,.,）经一次减少后得到的数组（b1,b2,）,即（,.,）（,.,）（b1,b2,）.记数组的变换集W= 数组的所有变换 .4. 初步分析与重排变换对数组（n）,当n=1时,易知（1）（0）,即若只剩一张,则这一个拿牌的人必拿走这一张,最后剩0张,认为他输.当n1时,可经变化（n）（1）（0）,此时第一个拿牌的人能保证第二个拿牌的人拿走最后一张,认为第一个那牌的人能保证第二个拿牌的人输.即一个人,如果他面对的是（n）,当n=1时,他输；当n1时,他赢.对于二元非0数组（m,n ）,m、n N+,易知（m,n）=（n,m ）,因为它们都表示两叠牌的牌数分别为m张和n张,则他们的取法一样.故我们可以对数组（m,n）只讨论 m n的情形.先从最简单的看起,显然（0,1）、（1,0）、（1）三种情况减少成（0）, 所用步数的确定的奇偶性是一样的.因为它们都表示只剩一张牌,那么它们胜负的结果都一样.为此,我们把表示牌的相同状况相同、仅仅只有牌数的顺序不一样的几个数组视为同一个数组.我们用其中各元按从小到大的数组来表示它.先定义一个数组中各数从小到大排列的重排变换: V ： （a1,a2,an）（ai1,ai2,ain）其中ai1ai2ain,i1,i2,，in 1,2,，n,对任意数组（a1,a2,an）,我们以后只需讨论其按从小到大的重排数组V（a1，a2，an）减少步数的奇偶性,即为原数组（a1,a2,an）减少步数的奇偶性.我们按字典排列法给数组规定一个顺序,再按此顺序给所有的数组排大小.对任意的两个数组（a1,a2,an）和（b1,b2,）,设V（a1,a2,an）（ai1,ai2,ain）,V（b1,b2,）（,）. 当时,看ai1-,ai2 -,若都为0,则规定（a1,a2,an）（b1,b2,）；若不全为0,看第一个不为0的数,若0,则规定（a1,a2,an）（b1,b2,）；若0,则规定（a1,a2,an）（b1,b2,）. 当时,不妨设,则把（,）中元素前补个0,变成（0,0,）,记为（）,再按照的方法比较.5. 变换变小性质我们得到数组变换的一个重要性质：性质1 （变换变小性质） ,.证明 设V（）（a1,a2, ,an）,V（a1,a2, , ,an）,其中biai .若i = 1 ,则（b1 ,a2,an）（a1,a2,an）；若i 1 ,当,即数组中的前i-1个元均 ,V（a1,a2, , ,an ）（a1,a2, , , an）（a1,a2, ai , , an）；当时,设为数组中从左到右第一个大于bi 而排在bi前的数,则V（a1,a2, , ,an）（a1,a2, , , , an）（a1,a2, , , an）（a1,a2,an）.性质1得证.由上知（0,n）=（n,0）=（n）.若m0,且n0,先从简单的起,看（1,1）,必有（1,1）（1）（0）,则可保证第二个拿牌的输；再看（1,n）、n1,第一次变化可以是（1,n）（0,1）,再必有（1）（0）,则可保证第二个拿牌的输.面对（1,n）、n1的人,必有办法赢.6. 二元非零数组的结论（引理1）再看m2、n2的情形,还是先看简单的（2,2）,有（2,2） 0,2 1,2 ,而面对0,2，1,2的人必有方法赢,故在（2,2）的情况下,第二个人可保证第一个拿牌的人输.对（2,n）、n2的情形,第一次变化可以为（2,n）（2，2）,由上两行知,面对（2，2）的人,能被对手保证他输,故面对（2,n）的人能保证第二个人拿牌的人输.按照上面同样的分析方法,我们用数学归纳法可以得到：引理1： 面对（m,m）,m2的人,必能被对手保证他输,而面对（m ,n）,nm 2的人,必能保证对手输.证明：由两行以上部分,分析（2,2）和（2,n）、n2的过程知,m=2、nm时,上述引理成立.假设2mk时,上述引理成立,则当m=k+1时,有：减少方法必是（k +1,k +1）（l，k +1 ）、 lk.由假设知,面对（l，k +1 ）,lk的人,必能保证对手输,而此人的对手正是面对（k +1,k +1）的人,故面对（k +1,k +1）的人必能被对手保证他输,即（k +1,k +1）成立；对（k +1，n）、n k +1,可经变换（k +1，n）（k +1，k +1）,知面对（k +1,k +1）的人必能被他的对手,面对（k +1，n）、n k +1的人,保证他输.即面对（k +1,n）的人必能保证他的对手,面对（k +1，k +1）的人,输.故对（k +1，n）、n k +1,引理成立 引理得证.7. 先必输集和后必输集3.我们定义两个重要的集合：A = 数组x=（a1，a2，an）数组（a1，a2，an）不管第奇数次怎么减少,都有相应的偶数次减少方法使得数组（a1，a2，an）是在第奇数次后才减少成(0,0,.,0)的；其中a1,a2,anN,nN+,称为先必输集.B = 数组x=（a1,a2,an）数组（a1，a2，an）不管第偶数次怎么减少,都有相应的奇数次减少方法使得数组（a1，a2，an）是在第偶数次后才减少成(0,0,.,0)的；其中a1,a2,anN,nN+,称为后必输集.若某个人面对的牌数为（a1，a2，an） 时,不管他每步如何减少牌,他的对手都有办法使他输；同样,若某个人面对的牌数为（a1，a2，an）时,不管他的对手每步如何减少牌,他都有办法使他的对手输.由定义易知AB=.8. 先必输集、后必输集和全集的关系它们的关系可以通过下面我们得到的几个很重要的定理来描述：定理1 xA 1W,有 1（x）B.证明 ：（充分性）由 1W,有 1（x）B ,得面对x的人的对手,即面对 1（x）的人,必能保证面对x的人输.即xA.（必要性）由 xA 知,对 1W,面对x的人的人必能保证他的对手,即面对 1（x）的人,输.即 1（x）B.同理,我们可以得到 定理1 xB ,有 1（x） A .定理2 对 1W,（x）AB,则x AB.证明 ：若 1W,（x） B,由定理1 知,xA；若,有 1（x）,则 1（x） A,由定理1知,xB,故x AB.定理得证.以下我们得到一个很重要的性质：性质2 U AB, 即 任何数组（a1,a2,an）,必有（a1,a2,an）AB.证明 ：对（0,0,0）,认为经过0步便变成（0）的,故（0） B .对非（0）数组,我们用数学归纳法证.当数组中的非0元个数为1或为2时,由上述引理1前后部分我们可得到（a1,a2）AB.假设数组中非0元个数k时,（a1,a2,ak）AB,则 对于由k1个1组成的数组（1,1,1）,经过的变换必是把某个1变成0,均为（1,1,1）（0,1,1,1）由k个1组成的数组（1,1,1）AB .由定理2知,由k1个1组成的数组（1,1,1） AB .对于由k1个非0元组成的数组,假设对每个小于（a1,a2,）的数组（b1,b2,）均有（b1,b2,） AB,则（a1,a2,）的变换必是对V（a1,a2,）的某一个元减少,假设是第i个.为书写方便,我们仍用（a1,a2,）表示V（a1,a2,）.则数组（a1,a2, , , ）变换后的数组为（a1,a2, , ,）,由上面性质1知,（a1,a2, , , ）（a1,a2, , ,）.故（a1,a2, , , ） AB,再由上定理2知,（a1,a2, , ,） AB .又AB=,可知任意的数组（a1，a2，an）,.即面对（a1，a2，an）的人,要么能保证对手输,要么被对手保证他输.由引理1前后的讨论知,（1）,（m,m）、m2,A； （n）、n1,（1,n）、n1,（m ,n）、nm 2,9. 现实问题的解决下面来解决本文开头提出的实际问题. 从简单的入手,对（1,1,1）,必是（1,1,1）（1,1）,故（1,1,1）A；则（1,1,n）、n2（1,1,1）A,由定理1知,（1,1,n）、n2,.对（1,2,2）,可有（1,2,2）（2,2）A,得（1,2,2）.同理（1,n,n）、n2,.而（1,2,3）,故（1,2,3）A.故（1,2,n）、n4,.对（1,3,n）、n3可有（1,3,n）（1,2,3）A,得（1,3,n）、n3,.对（1,4,5）,（1,4,5）,故（1,4,5）A；可得（1,4,n）、n6,（1,5,n）、n5,.以此为基础,下面我们用数学归纳法来证明（1,2n,2n+1）A；而（1,2n,m）、m 2n+2,（1,2n+1,m）、m 2n+1,.假设对n,则（1,2k,2k+3） ,故（1,2k+2,2k+3）A；故（1,2n,m）、m 2n+2,（1,2n+1,m）、m 2n+1,.命题得证. 看（2,2,2）,有（2,2,2）,故（2,2,2）A；得（2,2,n）、n3,.对（2,3,n）、n3,可有（2,3,n）（1,2,3）A,故（2,3,n）、n3,.对（2,4,4）（4,4）A；（2,4,5）（1,4,5）A,故（2,4,4）,（2,4,5）；对（2,4,6）,故（2,4,6）A.对（2,5,7）,故（2,5,7）A.得（2,5,n）、n5,（2,6,n）、n6,.仿照上面对（1,2n,2n+1）A的证明过程,我们得到（2,4n,4n+2）,（2,4n+1,4n+3）A；而（2,4n+2,m）、m 4n+2,（2,4n+3,m）、m 4n+3,. 对（3,3,n）、n3（3,3）A；（3,4,4）（4,4）A；（3,4,5）（1,4,5）A；（3,4,6）（2,4,6）A；而（3,4,7）,故（3,4,7）A；（3,4,n）、n8,.对（3,5,6）,故（3,5,6）A；（3,5,n）、；而（3,6,m）、m 6,（3,7,m）、m 7,.仿照上面对（1,2n,2n+1）A的证明过程,我们得到（3,4n,4n+3）,（2,4n+1,4n+2）A；而（3,4n+2,m）、m 4n+2,（3,4n+3,m）m 4n+3,.由上面分析 知,（3,4,7）A,故面对（3,4,7）的人,不管他每步如何减少牌数,他的对手都有相应的减少牌数的方法,使他输.并且我们从集合A中任意拿出一个数组,和（3,4,7）有同样的上述效果.10. 三元非零数组的结构10.1. 集合A中从一元到三元数组的公式通过和以上部分类似的分析,类此地,按照上面的方法依次做下去,便可确定所有非0三元数组归属于集合A或B的问题.由AB=,我们只需确定属于集合A的数组所具有的性质,其余的便都是集合B的.具体的可见下表 10.1（主要是给出属于集合A的数组）.A 先必输集B后必输集（1）,（0）,（n）、n2,（n,n） 、n2,（1,n）、n1,（m,n）、nm+1,（1,1,1）,（1,2n,2n+1）（1,1,n）、n2,（1,n,n）、n2,（1,2n,m）、m 2n+2,（1,2n+1,m）、m 2n+1,（2,4n,4n+2）,（2,4n+1,4n+3）,（2,4n+2,m）、m 4n+2,（2,4n+3,m）、m 4n+3,（3,4n,4n+3）,（3,4n+1,4n+2）,（3,4n+2,m）、m 4n+2,（3,4n+3,m）m 4n+3,（4,8n+m,8n+m+4）、（4,8n+m,）、8n+m+4、 (5, 8n,8n+5) 、(5, 8n+1,8n+4) 、(5, 8n+2,8n+7) 、(5, 8n+3,8n+6) 、(5, 8n,m) 、m8n+ 6,(5, 8n+1,m）、m8n+5, (5, 8n+2,m）、m8n+8, (5, 8n+3,m）、m8n+6, (6, 8n,8n+6) 、(6, 8n+1,8n+7) 、(6, 8n+2,8n+4) 、(6, 8n+3,8n+5) 、(7, 8n,8n+7) 、(7, 8n+0,8n+6) 、(7, 8n+2,8n+5) 、(7, 8n+3,8n+4) 、表 10.110.2. 三元非零数组排列的对称性在上表中,抽取了一些具有代表性的数组,便得到下列数组排列图（图 (1,1,1)(1,2,3)(2,4,6)(2,5,7)(3,4,7)(3,5,6)(4,8,12)(4,9,13)(4,10,14)(4,11,15)(5,8,13)(5,9,12)(5,10,15)(5,11,14)(6,8,14)(6,9,11)(6,10,12)(7,11,13)(7,8,15)(7,9,14)(7,10,13)(7,11,12)(8,16,24)(8,17,25)(8,18,26)(8,19,27)(8,20,28)(8,21,29)(8,22,30)(8,23,31)(9,16,25)(9,17,24)(9,18,27)(9,19,26)(9,20,29)(9,21,28)(9,22,31)(9,23,30)(10,16,26)(10,17,27)(10,18,24)(10,19,25)(10,20,30)(10,21,31)(10,22,28)(10,23,29)(11,16,27)(11,17,26)(11,18,25)(11,19,24)(11,20,31)(11,21,30)(11,22,29)(11,23,28)(12,16,28)(12,17,29)(12,18,30)(12,19,31)(13,16,29)(13,17,28)(13,18,21)(13,19,30)(14,16,30)(14,17,31)(14,18,28)(14,19,29)(15,16,31)(15,17,30)(15,18,29)(15,19,28)图 10.2从图 2 中我们容易看到,如果把每个数组当成一个点,便具备一定的对称性,类似于矩阵里面的方阵的对称性和倒过来的阶梯型排列.见下图 图3 .*10.3. 三元非零数组排列的方阵的结构通过和以上表 2、图 2和图 3部分类似的分析,我们可以把所以的具有类似性质的数组抽出来,便可得到先必输集A中具有类似的对称性质的数组的倒阶梯型排列.见下图 10.3,是从图 10.2中数组中最小元为4开始抽取的排列.（具体的可参加附表先必输集A (三元非0数组) 电子表格）*图10.3从对这些有代表性的数组的观察和分析中,我们发现：竖着看,各数组的的第一个元依次增大；横着看,各数组的的第二个元也是依次增大；从整体及各块上看,每个小台阶都是一个的数组矩阵,如果单独把数组的第三个数拿出来,便容易发现从小块来看,每个的矩阵都是对称矩阵,且不同的矩阵的差是,每个的矩阵都是对称矩阵均可表示为：见下表 2,表 2 为抽取图 2 中后面的两大块数组中的第三个数,而形成的表格.12131415131215141415121315141312242526272829303125242726292831302627242530312829272625243130292828293031292831303031282931302928表 10.411. 任意三元非零数组的归属性问题的确定根据以上的分析,我们只需找出每个元都大于等于4的属于先必输集A的元,有一个小于4的数组,上面已经给出.不在A中的数组比在B中.现在我们来找出集合A中以a、b, 4ab , 作为较小元的数组（a,b,？）.先把整数a , b 用二进制表示当1时,所求数组不存在.当0时,而,则所求数组不存在；而,+.其中函数的值从下表中给出： 01230 0 1 2 31 1 0 3 22 2 3 0 13 3 2 1 0如给定数a16,b65,则由a16,b65,故？+1,即数组为（16,65,81）.而给定数a19,b58,则由a19+3,b58,其中1,故所求数组不存在.当然,我们还可以讨论出先必输集A中四元非零数组甚至更高元数组的有关性质,限于一些原因,在此就不再探究了,有兴趣的读者可以试试.论文小结：从本文对生活中的一个小游戏的分析和研究中,我们易看出,数学在生活中的作用是非常大的,掌握一些数学思想方法对我们来说是非常重要的.在本文中,我们主要采用了把现实问题转化为数学问题,再运用化归思想和数学归纳法等方法对该问题进行一层一层的解剖、分析,从易到难、由浅入深、由点及面的思考分析问题,最终我们得出了一元、二元和三元非0数组以及任意元数组的归属性即任意数组都确定的属于先必输集A或后必输集B.并着重研究了先必输集A中三元非0数组的性质,得到了该数组满足的条件.解决了现实问题.发现A 中数组经某种排列后,便具有一定的对称性,和递推性.还可以对三元的结论进行推广,按照类似的分析方法,可以去分析更高元非零数组的桂属性. 参考文献1 王萼芳,石生明.高等代数M.（第三版）2003年7月.2 孙淑玲,许胤龙.组合数学引论M.2008年.3 华东师范大学数学系数学分析上册M第三版北京: 高等教育出版社, 20014 华东师范大学数学系数学分析上册M第三版北京: 高等教育出版社, 2001 5 余元希、田万海,初等代数研究（上、下）毛宏德M.高等教育出版社,2008.6 李宏伟.数学史在数学概念教学中的应用研究.硕士学位论文.2007.47