从“切蛋糕问题”谈到欧拉在图论上的贡献

《从“切蛋糕问题”谈到欧拉在图论上的贡献》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、北清桥东中培训中心从“切蛋糕问题”谈到欧拉在图论上的贡献从圣诞节到新年之间，我们有几天假期。我们几个老朋友就选择一个晚上，各自准备点吃的东西欢聚在一起。吃吃喝喝完后，大家各出一些需要动脑筋想的问题消遣，于是字谜啦、数学游戏等都出场了。当晚，煮一手好菜的老黎和我都各出一个问题，后来我发现这二个问题都和一门正在蓬勃发展的数学——图论（GraphThe－ory）有关系。于是今天就打算谈谈这二个问题，顺便也介绍一下这门在国内正受到数学工作者注意的数学。切蛋糕问题我先提出这样的一个斗智比赛：现在有一盘蛋糕在面前，给你一把刀子，你要一刀一刀切下去，不可以用手挪动蛋糕，谁能六刀切出最多块的谁就是胜利

2、者。我们的面前有大华姐制成的香喷喷的蛋糕，但是我们并不是真的就拿刀子在上面切割起来，如果是那样大华姐准会气得呱呱叫。而是在一张纸上，画一个差不多像那个可怜的阿Q所画的那个圆，然后画一直线割这个圆代表刀痕。这个问题有很多答案。同一个家庭里的成员就有不同的结果。许太太说只能切出12块，而一向做事细心的老许说他能切出22块！公说公有理、婆说婆有理，你说我这个裁判该听谁的？小鬼——小郑喊道：“我切出也是12块！少数服从多数应该是12块。”让我们看看他们的结果吧！很明显的许先生应该是胜利者，你看他只用五刀就已切出16块来，再加上一刀不是更“犀利”？老许说如果你小心的切应该是可以切出22块出来，那

3、么读者请你自己试试看吧！15www.bqbridge.cnTel：（010）86527976/81698308北清桥东中培训中心从小郑和许太太的结果，我们可以看出一个这样的事实，如果期望能多切出一些蛋糕，要“规规矩矩”像孔老夫子那样肉割不正不吃的方法是行不通的。不应该有二刀平行割，也不要有三刀都通过同一点的现象出现。那么你就有法子割出较多块了。我这里要提一个问题：现在想像我们的蛋糕是很大，可以一刀一刀的继续切下去，能不能找到一个数学公式来计算每一次后应该有多少块数出现？我们现在就来解决这个问题：我们令f（n）表示n刀下去后出现的蛋糕的块数。从实际经验中，我们知道f（1）=2，f（2）=

4、4。15www.bqbridge.cnTel：（010）86527976/81698308北清桥东中培训中心但是f（3）不是6，而是7！大家请看看本文上面列出的三个切法。如果第三刀切时不和任何先前一刀平行，或者通过二刀的交点（数学家可能建议这样讲：三个刀痕的直线不共点），它就能比原先多切出了三块出来。因此，f（3）＝f（2）＋3＝4＋3＝7如果第四刀也是照这样的方法切，它就切出比原先的数目多出4块来，即f（4）＝f（3）＋4=7＋4=11如此类推，一般我们有f（n）=f（n-1）＋n。因此如果能知道前面第n-1刀后的块数，我们就可以算出f（n）了。有没有直接公式表示f（n）呢？以下我们

5、介绍一个巧妙的方法算出这个公式。f（1）=2f（2）＝f（1）＋2f（3）=f（2）＋3…  …f（n-1）＝f（n-2）＋（n-1）＋）f（n）＝f（n-1）＋nf（1）＋f（2）＋…＋f（n-1）＋f（n）＝f（1）＋f（2）＋f（3）＋…＋f（n-1）＋2＋2＋3＋…＋（n-1）＋n在上面的算式中，我们消去二边都出现的数，可以得到f（n）＝2＋2＋3＋…＋（n-1）＋n15www.bqbridge.cnTel：（010）86527976/81698308北清桥东中培训中心＝1＋（1＋2＋3＋…＋n）这就是我们的切蛋糕的公式了！你说巧不巧？妙不妙？这个问题可以再推广，而且能用类似以

6、上的方法获得更一般的公式读者有兴趣可以看后面的“动脑筋问题”里的问题。 老黎提的问题 现在让我们回到那新年前的晚会吧！我们的老黎，也是一个数学爱好者，他出的问题就是一般数学上称为：“一笔画问题”。你看他在一张纸上画了一个图，然后要我们大家也一笔画出来。我看了看就对老黎喊道：“喂！老黎！你的图不可能一笔画出来的。你看是不是画错了？”老黎想想就说：“对不起！我的图画错，现在改一改。”结果是一个平日靠画图为生的老章师傅，妙手一挥一笔画出了老黎的第二个图，当然我也画出来。为什么我知道老黎第一次画的图是不能一笔画成的呢？读者如果不相信请你试试看能不能一笔画成，我敢和你赌一万元你画不成。我把老黎的

7、第一个图看成是由点以及线组成的一种集合。在那图里直线的交点就用一个小圆圈表示，我把那图变成这样的图三。这图画的并不像老黎的图那样好看，可是用数学（拓扑学Topology）的观点来看，这二个图是一样的（即同胚homeomor－phic）。这个图（graph）的小圈圈就称为顶点（vertex），顶点和顶点的联线就称为边（edge）。15www.bqbridge.cnTel：（010）86527976/81698308北清桥东中培训中心这个图是联通的