第2周-数学的巧妙运用

数学的巧妙运用例1棋子颜色的变化

任意拿出黑白两种颜色的棋子共n个,排成如图所示的一个圆圈.然后在两颗颜色相同的棋子中间放一颗黑色棋子,在两颗颜色不同的棋子中间放一颗白色棋子,放完后撤掉原来所放的棋子.再重复以上的过程,这样放下一圈后就拿走前次的一圈棋子,问这样重复进行下去各棋子的颜色会怎样变化呢?n=8有结论：设黑子用+1表示，白子用-1表示。记8颗分别为a1,a2,…,a8,(

ai=+1,-1)第0次：a1a2a2a3a4a5a6a7a8第1次：a1a2a2a3a3a4…a7a8a8a1第2次：a1a22a3a2a32

a4…a8a12

a2.。。。.。。。.第8次：a1a28a328

a456a570a656a728a88

a1,…至多经过8次变换，棋子的颜色全变黑。问题：对任意整数n，棋子的颜色能全变黑吗？例2某人由A处到B处去，途中需到河边取些水，如下图。问走那条路最近？（用尽可能简单的办法求解。）dAB河例3将形状质量相同的砖块一一向右往外叠放，欲尽可能地延伸到远方，问最远可以延伸多大距离。设砖块是均质的，长度与重量均为1，其重心在中点1/2砖长处，现用归纳法推导。Zn(n－1)n(n＋1)由第n块砖受到的两个力的力矩相等，有1/2-Zn=(n－1)Zn故Zn=1/(2n)，从而上面n块砖向右推出的总距离为，故砖块向右可叠至任意远，这一结果有点出人意料。通常，1公斤面，1公斤馅，包100个汤圆，有一次馅多了0.4kg，问能否将汤圆包大一些或小一些将这些馅仍用1kg面用完?问题圆面积为S的一个皮，包成体积为V的汤圆,若分成n个皮，每个圆面积为s，包成体积为vV和nv哪个大?讨论题:包汤圆Ssss…Vvvv(共n个)定性分析V比nv大多少?定量分析讨论题:包汤圆假设1.皮的厚度一样2.汤圆的形状一样模型应用若100个汤圆（饺子）包1公斤馅,则50个汤圆(饺子)可以包公斤馅R~大皮半径V是nv是倍1.4r~小皮半径两个k1（和k2）一样(1),(2),(3)

奇偶校验方法及相关问题

证明：

采用反证法，设，其中p、q互素，则有p2=2q2。因为2|p2，故2|p。记p=2p1，可得4p12=2q2，即2p12=q2，故又有2|q，与p、q互素矛盾。例4证明是无理数。同样方法可以证明：若m是大于1的素数，n是大于1的整数，则必为无理数。例5拟用40块方形瓷砖铺设如下图所示的地面，但商店只有长方形瓷砖，其大小为方形的两块。问购买20块长方形瓷砖后，是否可能不裁开而直接铺好地面？解

将图11.4中的(a)(b)黑白相间染色。显然，如长方形瓷砖不裁开，只能用来复盖相邻的两格，故复盖的两格必为一白一黑。下图(a)中共有21个黑格和19个白格，故不可能直接铺好，下图(b)中黑白格各为20个，大家很容易找到直接铺设的方法。图(a)图(b)讨论题拟将一批尺寸为1×2×4的的商品装入尺寸为6×6×6的正方体包装箱中，怎样才能使所装的商品最多?讨论题拟将一批尺寸为1×2×4的的商品装入尺寸为6×6×6的正方体包装箱中，怎样才能使所装的商品最多?

解

将正方体剖分成27个2×2×2的小正方体，并按下图所示黑白相间地染色。再将每一2×2×2的小正方体剖分成1×1×1的小正方体。易见，27个2×2×2的正方体中，有14个是黑的，13个是白的（或13黑14白），故经两次剖分，共计有112个1×1×1的黑色小正方体和104个1×1×1的白色小正方体。虽然包装箱的体积恰好是商品体积的27倍，但容易看到，不论将商品放置在何处，它都将占据4个黑色和4个白色的1×1×1小正方体的位置，故商品不可能充满包装箱。解

将正方体剖分成27个2×2×2的小正方体，并按下图所示黑白相间地染色。解

将正方体剖分成27个2×2×2的小正方体，并按下图所示黑白相间地染色。解

将正方体剖分成27个2×2×2的小正方体，并按下图所示黑白相间地染色。解

将正方体剖分成27个2×2×2的小正方体，并按下图所示黑白相间地染色。解

将正方体剖分成27个2×2×2的小正方体，并按下图所示黑白相间地染色。再将每一2×2×2的小正方体剖分成1×1×1的小正方体。例1在每一次人数不少于6人的聚会中必可找出这样的3人，他们或者彼此均认识或者彼此均不认识。

利用图的方法来描述该问题。将人看成顶点，两人彼此都认识用实线连，否则虚线。证明：

图论法及相识问题（拉姆齐问题）

问题转化为在一个6阶图中必存在实线三角形或虚线三角形。请大家一起画图证明υ2

υ1

υ3

υ4

υ6

υ5

υ1

υ2

υ3υ4

任取一顶点，不妨υ1考察υ2υ3、υ2υ4和υ3υ4υ2υ3、υ2υ4和υ3υ4只能是虚线，否则得证但这样三角形υ2υ3υ4的三边均为虚线不妨取υ1υ2、

υ1υ3、

υ1υ4实线与υ1相连的边必然有：实线条数不小于3或虚线条数不小于3拉姆齐问题也可这样叙述：6阶2色完全图中必含有3阶单色完全图。其他类似可推出的结果：命题任一6阶2色完全图中至少含有两个3阶单色完全图。

证明：前面证明必存在3阶单色完全图，不妨设υ1υ2υ3

为红色完全图υ1υ5、υ2υ5、υ3υ5中至少有两条黑色、故υ1υ5与υ2υ5中至少有一条是黑色若υ4υ5υ6也是红色三角形，命题已得证

故至少一边与υ1υ2υ3的边异色，不妨设υ4υ5黑色υ1υ4、υ2υ4、υ3υ4至少应有两条黑色，不妨设υ1υ4、υ2υ4黑色所以存在第二个3阶单色完全图。υ2

υ1

υ3

υ4

υ6

υ5

讨论题17位学者中每人都和其他人通信讨论3个方向的课题。任意两人间只讨论其中一个方向的课题，则其中必可找出3位学者，他们之间讨论的是同一方向的课题。讨论题:任意的9个人中一定有3个人互相认识或者有4个人互相不认识。著名的Euler“七桥问题”

东普鲁士哥尼斯堡(原苏联加里宁格勒)有一条布勒尔河，这条河有两条支流，在城中心汇合成大河，河中有一小岛，现有七座桥将它与陆地连接（图1-2）

1735年左右，哥尼斯堡大学生傍晚散步时，总想一次走过七座桥，要求每座桥只准走一遍，试来试去总未成功，于是，他们写信求教瑞士的大数学家Euler，他用了几天时间反复思考、想象，终于在1736年发表了图论的第一篇论文“哥尼斯堡的七座桥”解决了这个问题

在文中欧拉创造性地将每一块陆地用一个点代替，而将每一座桥用连接相应两点的一条线来代替，从而得到了一个“图”这样，此问题就变为“从图的某个顶点出发，经过每条线只一次最后回到原来的地方”。由于每一次通过点的边总是两条，即进入和离开该点，如果七桥问题有解，则图中与每个点相连的边应该为偶数条，而图中与各点相连的边都是奇数条，因而七桥问题无解。无向图的欧拉通路、欧拉图

（即一笔画问题）经过图中每条边一次且仅一次并且行遍图中每个顶点的通路(回路),称为欧拉通路或欧拉迹(欧拉回路或欧拉闭迹).存在欧拉回路的图,称为欧拉图.定理无向图G具有欧拉通路,当且仅当G是连通图且有零个或两个奇度顶点.若无奇度顶点,则通路为回路;若有两个奇度顶点,则它们是每条欧拉通路的端点.推论无向图G为欧拉图(具有欧拉回路)当且仅当G是连通的,且G中无奇度顶点.图中,(1-3)不是欧拉图,(4)是欧拉图.例是欧拉图；不是欧拉图，但存在欧拉通路；即不是欧拉图，也不存在欧拉通路。问题：人、狼、羊、菜均要过河，船需要人划，另外至多还能载一物，而当人不在时，狼要吃羊，羊要吃菜。问人、狼、羊、菜怎样过河，试设计一个安全渡河方案，并使渡河次数尽可能地少。穷举法

例人狼羊菜过河问题状态转移问题1）允许状态集合S人、狼、羊、菜依次用四维向量表示它们的状态，在左岸用1表示，在右岸用0表示。如（0，1，0,1)表示人、羊在右岸，狼、菜在左岸。人在左岸(1,1,1,1),(1,1,1,0),(1,1,0,1),(1,0,1,1),(1,0,1,0)人在右岸(0,0,0,0),(0,0,0,1),(0,0,1,0),(0,1,0,0),(0,1,0,1)2)允许决策集（划船方式）D用四维向量表示决策，如（1，1，0，0）表示人带狼摆渡。D={(1,0,0,0),(1,1,0,0),(1,0,1,0),(1,0,0,1)}问题转化为：由初始状态(1,1,1,1)出发，经奇数次上述运算转化为状态(0,0,0,0)的过程。规定运算：分量1+1=0,1+0=0+1=1,0+0=0如(1,1,1,1)+(1,0,1,0)=(0,1,0,1)其实际意义：人狼羊菜原均在左岸，人带羊过河，左岸为新状态，即仅剩狼和菜。s(i+1)=s(i)+d(i)1,1,1,1(1,0,1,0)0,1,0,1(1,0,0,0)1,1,0,1(1,1,0,0)0,0,0,1(1,0,0,1)0,1,0,0(1,0,1,0)1,0,1,1(1,0,1,0)1,1,1,0(1,0,0,1)(1,1,0,0)0,0,1,0(1,0,0,0)1,0,1,0(1,0,1,0)0,0,0,0例夫妻过河问题

问题：有3对夫妻过河，船最多能载2人，条件是任一女子不能在其丈夫不在的情况下与其它男子在一起，如何安排三对夫妻过河？

此类问题是古典的趣味数学问题，用穷举方法可以解决，但怎样建立数学模型用计算机解决？

模型构成：假设由北岸往南岸渡河，用向量（x，y）表示有(x,y)为状态向量；

由条件知，有些状态是可取的，有些是不可取的，

x个男子、y个女子在北岸，其中0≤x,y≤3，

称向量如状态(2,3)是不可取的，

而状态(3,1)是可取的。1)可取状态：

总共有10种可取状态具体如下：

(3,3)(3,2)(3,1)(3,0)(1,1)(0,0)(0,1)(0,2)(0,3)(2,2)

其中(i,i)表示i对夫妻。

用S表示可取状态的集合，称为允许状态集合。2)可取运载：

(0,1)(0