荔园在线
荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: zhulin (风清云淡), 信区: NORC
标 题: 趣题巧解
发信站: 荔园晨风BBS站 (Fri Jun 21 16:48:49 2002), 转信
天堂首页│数学竞赛│数学建模│图象处理│数学游戏│数学网站│MATLAB
1.泡泡糖问题
可怜的琼斯夫人路过泡泡糖出售机时,尽量不使她的双胞胎儿子有所察觉.
大儿子:"妈妈,我要泡泡糖."
二儿子:"妈妈,我也要,我要和比利拿一样颜色的."
分币泡泡糖出售机几乎空了,里面只有4粒白色的和6粒红色的泡泡糖.说不准下
一粒是什么颜色.琼斯夫人如果要得到两粒同种颜色的泡泡糖,需要准备花多少钱
?
是不是琼斯夫人需要花6分钱,准可以得到2粒红色的糖----就算所有白色的糖花
去4分钱,还有两分钱可以买到2粒红色的糖.或者她花去8分钱准可得到2粒白色的糖
,所以她需要花8分钱是吗?如果你这样算,那就错了,因为琼斯夫人并不要求必须得
到两粒红色的糖或者两粒白色的糖,她只要求两粒同色的糖,即使先取到两粒不同色
的糖,第三粒必定与前两粒中的一粒同色.所以她最多只需要花3分钱.
如果出售机内有6粒红色的,4粒白色的,5粒蓝色的.琼斯夫人最多要花多少钱?显
然只要花4分钱即可.
如果琼斯夫人的孩子是三胞胎,那该怎样呢?最坏的情况是她拿到了2粒红的,2粒
白的和2粒兰的,第七粒肯定与前六粒中的两粒同色,所以她最多需要花7分钱.
如果只有一粒蓝色的泡泡糖,那么显然只要花6分钱即可买到三粒同色的糖.
假如琼斯夫人是幼儿园的老师,她带着 k 个孩子路过泡泡糖出售机,出售机中有
n 组同色的泡泡糖,且每组糖至少有 k 粒,她需要花多少钱呢?
最坏情况是她每种颜色的泡泡糖都买了 k-1 粒,那么再买一粒即可,所以她最多
需要花 n(k-1)+1 分钱.
如果 n 组糖中有一组或几组同色的糖少于 k 粒,又是什么情况呢?
让我们假设有 m 组同色的泡泡糖少于 k 粒,并且设其中第 i 组糖有 ai 粒,那
么琼斯夫人最倒霉的事情是,她把所有少于 k 粒的同色糖都买了,并且其他种类的
糖每种都买了 k-1 粒,最后再买一粒才能得到 k 粒同色的糖.所以她最多需要花:
m
(n-m)(k-1)+1+∑ai
i=1
分钱.
这种类型的题目很多,又比如从52张纸牌中抽出7张同花的牌,那么最多需要抽多
少张牌呢?显然需要 4(7-1)+1=25 张.
------------------------------------------------------------------------
--------
2.乒乓球赛问题
某中学将举行乒乓球比赛,小明他们班有5人先进行淘汰赛,选出一人参加学校的
决赛,班主任杨老师计算了一下比赛的次数:"嗯,由于5是奇数,所以第一轮有一个队
员轮空,第二轮中还得出现一次轮空,一共需要进行4场比赛.选拔出一个队员后,学
校共有37个班级参加决赛,也采用淘汰赛,你知道需要多少场比赛吗?你还没有算出
来吗?哈哈!还在画表格呀?告诉你吧,每场比赛淘汰一名队员,一共要淘汰36名队员
,所以要进行36场比赛.不过,如果你想轻易地算出轮空的次数却没有这么容易,那么
,怎样计算轮空的次数呢?,请看如下的分析:
不知道你注意了没有,如果比赛人数正好是2的幂,那么轮空次数就是0,也就是说
,如果比赛人数是2,4,8,16,32等等,就不会出现轮空,如果不是这样类型的数,则至
少要有一次轮空.假设有n个队员参赛,如果是奇数,那么第一轮就有一名队员要轮空
,从第二轮开始的轮空数与(n+1)/2个队员参赛的轮空数是一样的,所以这时总的轮
空数是:(用L(n)表示n个队员参赛的轮空数)
L(n)=1+L((n+1)/2)
如果n是偶数,那么,第一轮没有轮空,从第二轮开始的轮空数与n/2个队员参赛的
轮空数是一样的,所以有:
L(n)=L((n)/2)
我们可以统一处理以上两个公式:
L(n)=a0+L((n+a0)/2)
其中a0为1或为0取决于n的奇偶性,下面的a1,a2,a3...也一样,假定2k<n<2k+1,并
且规定n>=2,因为最后总是冠亚军决赛,所以最后一场比赛总是2名队员.继续往下推
,我们有:
L(n)=a0+a1+L(a0/4+a1/2+n/4)
=a0+a1+a2+L(a0/8+a1/4+a2/2+n/8)
=a0+a1+a2+...+ak-1+L(a0/2k+a2/2k-1+...+ak-1/2+n/2k)
k-1 k-1
= ∑as+L(1/2k∑as2s+n/2k)
s=0 s=0
由于最后总有:
k-1
1/2k∑as2s+n/2k=2
s=0
即:
k-1
∑as2s=2k+1-n
s=0
我们看到,L(n)=a0+a1+a2+...+ak-1
所以,只要将2k+1-n化成二进制表示,其系数和就是轮空数,也就是其中1的个数.
对于n=37,我们可以算出2k+1-n=64-37=27=11011,其中有4个1,所以共有四次轮空.
------------------------------------------------------------------------
--------
3.玻璃杯问题
巴尼在汽水柜台工作,他用10只玻璃杯给两名顾客出了个难题.巴尼:"这一排有
10只玻璃杯,左边5只内有汽水,右边5只空着,请你使这排杯子变成满杯与空杯相互
交错,条件是只允许移动4只杯子."两位顾客看了看巴尼,又看了看杯子,摇了摇头,
不知道怎么办.巴尼:"好吧,我来告诉你们,只要分别把第二只杯子和第七只杯子,第
四只杯子和第九只杯子交换一下位置就成了."
这时,奎贝尔教授正好来到柜台前,看到了他们的把戏,并且来了点小花招.奎贝尔
教授:"何需移动四只杯子,我只要移动两只就行了,你行不行?"
巴尼纳闷地瞧着奎贝尔教授,不明就里.奎贝尔教授:"很简单,只要拿起第二只杯子
,把里面的汽水倒进第七只杯子,再拿起第四只杯子,把里面的汽水倒入第九只杯子
就行了."
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
■■■■■□□□□□--->■□■□■□■□■□
虽然奎贝尔教授抓住话语间的模棱两可之处解决了这个问题,但这个问题并不像
乍看上去那么简单.例如,还是这么个问题,但改成100只满杯挨着100只空杯排成一
排,请考虑一下,若要使其变成满杯和空杯交错排列,需将多少对杯子互换位置?显然
,一般地,如果有2n只杯子,n只满杯,n只空杯,需要将[n/2]对杯子互换位置,方法是
2k号杯子与2k+n号杯子互换位置即可(k=1,2,3,...)若n=100,则需互换50次.
有一个与上面分析的问题类似但困难的多的古典难题.咱们这回用两种不同颜色
的杯子作为道具,但是移动方法却大相径庭:每次只能一块儿移动一对相邻的杯子,
使结果成交错排列,以n=3为例,解题过程如下图所示:
1 2 3 4 5 6
■■■□□□
■□□□■■
■□□ ■□■
□■□■□■
普遍的解是什么呢?当n=1时,没有意义,n=2时你会发现,无解,当n>2时,解此问题
至少需要移动n次.n=4时,求解很不容易,你不妨试试,煞是有趣,或许你能够把当
n>=3时的解题过程公式化.不像上两道题比较容易,这个问题我还没有仔细研究过,
先把这道题上载,大家也可以发表意见.
根据这一难题还可以产生许多奇异的变相问题,用来测验你的智力.这里试着举几
例:
(1).仍然是同时移动两只相邻的杯子,但是如果颜色不同,则要在移动过程中
交换位置,这样一对黑白的杯子就变成一对白黑排列了.解8只杯子需要移动5次.对
于10只杯子,5次移动也够了.我还尚不知道他的普遍解,也许你能找出来.
(2).某种颜色的杯子少一个,即某种颜色的杯子有n只,另一种杯子有n+1只,
其余规则不变,已经证明(不好意思,不是我证的,我还没有仔细研究过),对于任意n
只杯子,其解须作n次移动,而且这是最少的移动次数.
(3).使用三种不同颜色的杯子.按照通常的方法移动一对相邻的杯子,使得所
有这三种颜色交相辉映.当n=3(共有9个杯子),其解需要作5次移动.在这些变相问题
中,假设在最终形成的排列中,不允许留有任何空距.如果允许留有空距,则问题的解
法就令人惊奇地变为移动4次了.
看来,尚有许多其他的变化形式,例如,假设一次可以同时移动3只或更多的杯子,
在上述各变相问题中改用这种移动方式,结果会如何呢?假如是第一次移动1只杯子
,第二次移动2只杯子,第三次移动3只杯子,依次下去,那又会怎样?给定某种颜色的
杯子n个,另一种颜色的杯子也为n个,这个问题的解是否总是作n次移动?这种种问题
都有待于人们去解决,我还没有时间来考虑这些问题,这是非常有趣非常值得人们思
考的趣题.
------------------------------------------------------------------------
--------
4.怕斯卡三角形与道路问题
苏珊很为难.她步行去学校,路上老是遇到斯廷基.斯廷基:"嘿嘿,苏珊,我可以陪
你一起走吗?" 苏珊:"不!请走开."
苏珊心想:我有办法了.每天早上我走不同的路线去学校.这样斯廷基就不知道在哪
儿找到我了.这张地图表示苏珊的住所和学校之间的所有街道.苏珊去学校时,走路
的方向总是朝南或朝东.她总共有多少条路线呢?
苏珊:"我真想知道有多少条路线可走.让我想一想.要算出多少条路线看来并不
简单.嗯.啊哈!一点不难,简单的很!"苏珊想到了什么好主意?
她的推理如下:苏珊:"在我家这个角点上写一个1,因为我只能从这一点出发.然后在
遇刺相隔一个街区的两个角点上各写一个1,因为到那里只有一条途径.现在,我在这
个角点上写上2,因为到达那里可以有两条途径.苏珊发现2是1加1之和,她忽然领悟
:若到某一个仅有一条途径,则该角点上的数字为前一个角点上的数字;若有两条途
径,则为前两个角点上的数字之和.
苏珊:"瞧,又有四个角点标上了数字,我马上把其他角点也标上数字."请你替苏
珊把剩下的角点标上数字,并且告诉她步行到学校共有多少条不同的路线.
5
学校 G
剩下的5个点,自上而下,从左至右分别标以1,4,9,4,13.最后一点上的13表示苏
珊去学校共有十三条最短路径.
苏珊所发现的是一种快速而简单的算法,用来计算从她家到学校的最短路径共有
多少条.要是她把这些路径一条一条地画出来,然后再计数,这样肯定麻烦,还容易出
错.如果街道的数目很多,那么这种方法根本就行不通.你不妨把这十三条路线都画
出来,这样你就更能体会到苏珊的算法是多么地有效了.
你对这种算法是否已经理解,可以再画一些不同的街道网络,然后用这种算法来确
定从任意点A到另一任意点B的最短路线共有多少条.网络可以是矩形网格,三角形网
格,平行四边形网格和蜂窝状的正六边形网格.也可以用其他方法(例如组合公式)求
解,但这种方法十分复杂,需要很高的技巧.
在国际象棋棋盘上,"车"从棋盘的一角到对角线上另一角的最短路径共有多少条
?就像苏珊给街道交点标上数字一样,把棋盘上所有格子也都填上数字,于是问题就
迎刃而解了."车"只能沿着右上方向朝另一个角的目标移动,便可以求出共有多少条
最短路径.如图所示:
1 8 36 120 330 792 1716 3432
1 7 28 84 210 462 924 1716
1 6 21 56 126 252 462 792
1 5 15 35 70 126 210 330
1 4 10 20 35 56 84 120
1 3 6 10 15 21 28 36
1 2 3 4 5 6 7 8
车 1 1 1 1 1 1 1
把整个棋盘正确标号,根据所标的数字,一眼就能看出在棋盘上从一个角出发到任
意一角,有多少条最短路线.右上角的数字是3432,所以"车"从一角到对角线的另一
角的最短路径共有3432条.
让我们把棋盘沿着左上至右下的对角线一截为二,使其成为如下图所示的阵列.此
三角形上的数字与著名的怕斯卡三角形(我国叫做杨辉三角形)的数字是相同的,当
然,计算街道路径条数的算法,恰恰就是构造怕斯卡三角形所依据的过程.这种同构
现象使得怕斯卡三角形成为无数有趣特性的不竭的源泉.
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
...........
利用怕斯卡三角形立即可以求出二项式展开的系数,即求(a+b)的任意次幂,同样
也可以用来解出初等概率论中的许多问题.请注意,上图中自顶部至底部,从边沿一
格来说是1,随着向中间移动,数字逐渐增加.也许你见过根据怕斯卡三角形所制成的
一种装置:在一快倾斜的板上,成百个小球滚过木钉进入各格的底部.全部小球呈现
出一条钟形的二项式分布曲线,因为到达每个底部孔位的最短路径的条数就是二项
式展开的系数.
显然,苏珊的算法同样适用于由矩阵格子组成的三维结构.设有一个边长为3的立
方体,分成27个立方体单元,把它看成棋盘,处于某一个角格上的"车"可以向三个坐
标上的任何位置作直线移动,试问"车"到空间对角线的另一个角格有多少条最短路
径?
------------------------------------------------------------------------
--------
5.错抱的婴儿
在某个医院,四个婴儿的身份标签被搞错了.两个婴儿的标签不错,其他两个婴儿
的标签弄错了.发生这种错误的情况有多少种?
一种简单的计算方法是把所有可能的情况列成一个表格,其结果表明两个婴儿搞错
的情况共有六种.现在假设标签搞乱了后,恰有三个是正确的,只有一个搞错了,问这
个问题有多少种不同情况?你是否用列表的方法求解?还是凭灵机一动想出来的?
A B D C
A D C B
A C B D
D B C A
C B A D
B A C D
这个问题许多人都茫然不解,其原因是他们作了下列错误的假设:在四个婴儿中
,三个婴儿与其标签相符的情况有许多种.但是你如果用"鸽笼原理"思索一下,情况
就一清二楚了.假设有四个鸽笼,一一标出应放物品的名称.若三样物品都放在了正
确的位置中,那么第四样物品只有一处可放,自然该处即为那件物品应放的位置,正
确的可能只有一种,即所有四样物品都放置恰当这一情况,而不可能有其他更多的情
况.一般地,如果 n 件物品,其中已经有 n-1件放对了地方,那么剩下的一件也必定
放置在正确的位置上了.
有一个关于三样东西都标签错误的古典问题.一旦领悟到可以把情况的数目缩
小为1,这个问题也就迎刃而解了.设在桌子上有三个盖着盖子的盒子,其中一个盒子
内有两粒绿豆,第二个盒子内有两粒红豆,另一个盒子内有一粒绿豆和一粒红豆,三
个盒子盖子上分别写着"红豆","红绿豆"和"绿豆",但是所有标签都标错了.你能从
任意一个盒子内取出一粒豆子后,便能判断出所有盒子内都装着什么豆子吗?
同上面的讨论一样,人们一般总是首先考虑有多少种不同的可能性,但是你如果
能够洞悉底蕴,一眼就可以看出只可能有一种情况,从误标为"红绿豆"的盒子中取出
一粒豆子,如果不是一粒绿豆就是一粒红豆,若是一粒绿豆,那么盒子里的另一粒也
必定是一粒绿豆,那么两粒红豆必定在标着"绿豆"的盒子内,反之,若取出的是一粒
红豆,那么另一粒必定也是红豆,两粒绿豆肯定放在标着"红豆"的盒子内,其他一盒
内的情况就一清二楚了.可以看出,三个盒子全都误标的情况只可能有如上两种.从
标着"红绿豆"的盒子内取出一粒便可以排除一种情况,仅剩下唯一正确的情况.
有时,上述问题也会以稍微复杂的形式出现.在三个盒子中,从任意一个盒子内
取出最少的豆子数进行试看,以此来判断三个盒子内各装有什么豆子.唯一的办法是
从标着"红绿豆"的盒子中取出一粒豆子试看.也许你能提出一些更加复杂的问题,诸
如每个盒子内不只两粒豆子,或者盒子不只三个等等.
其他许多发人深省的难题都与上面的婴儿问题有关,同样也涉及到初等概率论
.例如,假设婴儿的标签以随机的方式搞乱,那么四个标签全部正确的概率是多少?全
部弄错的概率是多少?至少有一个正确的概率是多少?恰好有一个正确的概率是多少
?至少有两个正确的概率是多少?恰好有两个正确的概率是多少?最多有两个正确的
概率又是多少?诸如此类,不一而足.
"至少一个"的问题,就一般的形式来说,属于古典趣味数学著作中的问题.这个
问题通常如下所述:在一家旅店,由 n 个人在仔细检查自己的帽子.寄存部的粗心女
郎没能使寄存牌和帽子做到一一对应,她随便地把寄存牌发了出去,问至少一人取回
自己的帽子的概率是多少呢?结果发现,当 n 增大时,其概率迅速地趋近于极限
(1-1/e),或者说比1/2稍微好一点,其中 e 是著名的欧拉常数,等于2.
71828182845904590...,在概率论问题中经常反复地出现.
------------------------------------------------------------------------
--------
6.塑料杯问题
奎贝尔教授出了个难题.奎贝尔教授:"取三个喝咖啡用的泡沫塑料空杯,把11枚
硬币投入杯子中,要求每一只杯子中的硬币数目都是奇数.奎贝尔教授:"这不难做到
,是吗?方法很多,你可以在一只杯子中放入一枚硬币,第二只杯子中放入三枚硬币,
最后一个杯子中放入七枚硬币.这的确很容易.奎贝尔教授:"但是,你能否把十枚硬
币放入同样的杯子中,使得每只杯子中的硬币数都是奇数?这也是能够办到的,不过
你得动点脑筋才行.奎贝尔教授:"但愿你还没有泄气.你只要想到把其中一只杯子放
入另一只装着偶数个硬币的杯子中,就使每只杯子中都是奇数枚硬币了."
啊哈!一旦悟出杯中套杯,同一个集合的硬币可以属于不止一只杯子,这个棘手
的问题也就迎刃而解了.用集合论的术语来说,我们的解是7个元素的集合和3个元素
的集合,后一个集合又包含1个元素的子集.此解可以用图表示出来
试求所有其余的解亦很有趣.要得到十个解并不困难,上述解法即为其中之一.但
若要发现其余的五个解,或者说十五个全部的解,却还需要花费一番精力.求出十五
个解之后,可以把硬币和杯子的数目,以及对于每只杯中放入硬币数的要求作一些改
变,从而产生一些新的问题.领悟到一个集合的部分或全部可以包含于另一个集合之
中,从而可以作两次计算,这是解决许多著名难题和悖论问题的钥匙.下面是一个趣
味问题.
一个男孩子逃学已经数周,学校考勤人员找到了他.小孩开始向他解释为何没有
时间上学:
"我每天睡觉需要8小时,8X365总共2920小时,一天有24小时,所以2920/24即
122天.
"星期六和星期日不用上学.一年总共约有104天.
"我们还有60天暑假.
"我一天吃饭需要花3小时,一年就要3X365,共有1095 小时,共有1095/24即45天
左右.
"我每天还需要2小时的课外活动.算起来一年也要有2X365,共730小时,或
730/24即30天左右."
小孩把所有这些天数相加如下:
睡觉 122
周末 104
暑假 60
用餐 45
课外活动 30
------
361天
"你瞧,"小孩说"仅剩下4天用作病假,我还没把学校每年应放的节假日算进去呢
!"
考勤人员听了后对小孩的数字研究了半天,看不出有什么破绽.请你的朋友们试
试这个悖论问题,看有多少人能够指出其谬误所在,即把子集不止一次地算进去.这
孩子所说的各项就像奎贝尔教授杯子中套杯子的硬币一样重复地作了相加.
------------------------------------------------------------------------
--------
7.炙肉片的策略
约翰逊先生在户外有个炙肉架,正好能容纳2片炙肉.他的妻子和女儿贝特西都
饥肠辘辘,急不可耐.问怎样才能在最短时间内炙完三片肉.
约翰逊先生:"瞧,炙一片肉的两面需要20分钟,因为每一面需要10分钟.我可以
同时炙两片,所以花20分钟就可以炙完两片.再花20分钟炙第三片,全部炙完需要40
分钟."
贝特西:"你可以更快些,爸爸.我刚算出你可以节省10分钟."
啊哈!贝特西小姐想出了什么妙主意?
为了说明贝特西的解法,设肉片为A,B,C.每片肉的两面记为1,2.第一个10分钟
炙烤A1,和B1.把B肉片先放到一边.再花10分钟炙烤A2和C1.此时肉片A可以炙完.再
花10分钟炙烤B2和C2,仅花30分钟就炙完了三片肉,对吗?
这个简单的组合问题,属于现代数学中称之为运筹学的分枝.这门学科奇妙地向
我们揭示了一个事实:如果有一系列操作,并希望再最短时间内完成,统筹安排这些
操作的最佳方法并非马上就能一眼看出.初看是最佳的方法,实际上大有改进的余地
.在上述问题中,关键在于炙完肉片的第一面后并不一定马上去炙其反面.
提出诸如此类的简单问题,可以采用多种方式.例如,你可以改变炙肉架所能容
纳肉片的数目,或改变待炙肉片的数目,或两者都加以改变.另一种生成问题的方式
是考虑物体不止有两个面,并且需要以某种方式把所有的面都予以"完成".例如,某
人接到一个任务,把 n 个立方体的每一面都涂抹上红色油漆,但每个步骤只能够做
到把 k 个立方体的顶面涂色.
今天,运筹学用于解决事物处理,工业,军事战略等等许多领域的实际问题.即使
是像炙肉片这样简单的问题也是有意义的.为了说明这一点,请考虑下列一些变相问
题:
琼斯先生和夫人有三件家务事要办.
1.用真空吸尘器清洁一层楼.只有一个真空吸尘器,需要时间30分钟.
2.用割草机修整草地.只用一台割草机,需要时间30分钟.
3.喂婴儿入睡,需要时间30分钟.
他们应该怎样安排这些家务,以求在最短时间内全部完成呢?你看出这个问题与
炙肉片问题是同构的吗?假设琼斯先生和夫人同时进行操作,一般人开始往往以为做
完这些家务需要60分钟.但是如果一件家务(譬如说用真空吸尘器做清洁工作)分为
两个阶段,第二阶段延后进行(像炙肉片问题那样),那么三件家务可以在3/4的时间
内即45分钟内完成.
下面有一个关于准备三片热涂奶油的烤面包问题.这个运筹学问题比较困难.烤
面包架是老式的,两边各有一扇翼门,可以同时容纳两片面包,但是只能单面烘烤.如
果要烤双面,需要打开翼门,把面包片翻过身来.
将一片面包放入烤面包架需要时间3秒钟,取出来也需要3秒钟,将面包片在烤面
包架内翻身又需要3秒钟.这些都需要双手操作,即不能同时进行放,取或把两片面包
同时翻身,也不能在放入一片面包,将其翻身或取出的同时把另一片涂抹上奶油.单
面烘烤一片面包需要30秒钟,把一片面包涂抹上奶油需要12秒钟.
每片面包仅限于单面涂抹上奶油.未经烘烤不得事先在任何一面涂抹上奶油.单
面已经烤过的和涂抹上奶油的面包片可以重新放入烤面包加内继续烘烤其另一面.
如果烤面包架一开始就是热的,试问双面烘烤三片面包丙涂抹上奶油最少需要多少
时间?
在两分钟内完成上述工作并不太难.然而,如果你领悟到:一片面包在单面烘烤
尚未结束的情况下,也可以取出,以后再放回烤面包架内继续烘烤这一面,那么全部
烘烤时间就可以缩减至111秒钟.使你想到这一点,统筹安排这些操作使效率达到最
高也远非是一件易事.在这方面,尚有无数比此更为复杂的实际问题,需要借助于与
计算机和现代图论有关的高度复杂的数学手段.
------------------------------------------------------------------------
--------
8.难铺的瓷砖
布朗先生的院子里铺有40块四方瓷砖.这些瓷砖已经破损老化,他想予以更新.
他为修整院子选购新的瓷砖.可惜,目前商店里只供应长方形的瓷砖,每块等于原来
的两块.店主:"布朗先生,您需要几块?".布朗先生:"嗯,我要更换40块方瓷砖,所以
我估计需要20块."
布朗先生试着用刚买的新瓷砖铺院子,结果弄得烦闷不堪.不管他怎样努力,总
是无法铺好.
贝特西:"出了什么问题?爸爸?" 布朗先生:"这些该死的瓷砖,真叫人恼火.最后
总是剩下两个方格没法铺上瓷砖."
布朗先生的女儿画了一张院子的平面图,并且涂上了颜色,看上去好似一张棋盘
.然后她沉思了几分钟.
贝特西:"啊哈!我看出症结的所在了.请设想每块长方形瓷砖必定盖住一个红色
的格子和一个白色的格子,问题就清楚了."
这里面有什么奥妙,你理解贝特西的意思吗?
共有19个白色的格子和21个红色的格子,所以铺了19块瓷砖后,总要剩下2个红
格没有铺,而一块长方形瓷砖是无法盖住2个红格的.唯一的办法是把最后一块长方
形瓷砖断为两块.
A A B B C
K K L L M C D
J T S U M N D
J Q S R R N E
I Q P P O O E
I H H G G F F
布朗先生的女儿利用所谓"奇偶校验"解答了铺瓷砖问题.如果两个数都是奇数
或都是偶数,则称其为具有相同的奇偶性,如果一个数是奇数,另一个数是偶数,则称
其具有相反的奇偶性.在组合几何中,经常会遇到类似的情况.
在这个问题中,同色的两个格子具有相同的奇偶性,异色的两个格子具有相反的奇
偶性.长方形瓷砖显然只能覆盖具有相反奇偶性的一对格子.布朗小姐首先说明,把
19块长方形瓷砖在院子内铺上后,只有在剩下的两个方格具有相反的奇偶性时,才能
把最后一块长方形瓷砖铺上.由于剩下的两个方格具有相同的奇偶性,因此无法铺上
最后一块长方形瓷砖.所以用20块长方形瓷砖来铺满院子是不可能的.
数学中许多著名的不可能性的证明都建立在奇偶校验上.也许你很熟悉欧几里
德的著名证明:2的平方根不可能是一个有理数.证明是这样进行的:首先假设此平方
根可以表示成一个既约的有理分数,则分子和分母不可能都是偶数,否则它就不是一
个既约分数.分子,分母可能都是奇数或者一个是奇数,另一个是偶数.欧几里德证明
接着论证此分数不可能属于上述两种情况,换句话说,分子和分母不可能具有相同的
奇偶性或相反的奇偶性.而任何有理分数是两者必居其一,因而反证了2的平方根不
可能是一个有理数.
在铺砌理论中,有许多必定要用奇偶校验才能论证其不可能性的问题.上述问题只
是个极其简单的例子,因为它仅仅涉及用多米诺骨牌,即简单的,不平凡的波利米诺
来铺砌.(一个波利米诺是一些边沿相连的单位正方形的集合)布朗小姐的不可能性
证明适用于符合下列要求的单位方格矩阵:这种矩阵若按照棋盘那样涂色后,一种颜
色的方格要比另一种颜色的方格至少多一个.
在上述问题中,可以把院子看作缺少两个同色方格的一个6X7矩阵.显然,如果缺少
的两个方格同色,20个多米诺骨牌无法覆盖其余的40个方格.一个有趣的并与此有关
的问题是:如果缺少两个颜色不同的方格,20个多米诺骨牌是否能够覆盖住那缺格的
6X7矩阵?虽然奇偶校验没有证明其不可能性,但着并不意味着一定可以覆盖.通过擦
去一对异色的方格,可以生成所有可能的图形.但若逐一加以研究则不胜其烦,因为
各种可能的情况太多,以至于无法分析.对于所有的情况来说,是否有一种简单的可
能性证明?
有的,此证明既简单又巧妙,为拉尔夫.戈莫里妙手偶得之.他同样也是利用了奇偶
原理.假设此6X7矩阵有一条波及整个内部的闭合回路,宽度为一格.假设把闭合回路
上任何两个异色方格擦去,于是该闭合回路就一断为二,每一部分都是由格数成偶数
的异色方格组成.显然,这两部分的路总是能够用多米诺骨牌覆盖(把骨牌看作可以
停在弯曲车道上的篷车).你也许愿意尝试一下,把这个巧妙的证明应用于尺寸,形状
与此不同的矩阵,也可以考虑擦去不止两个方格的情况.
┌ ─ ─ ─ ─ ─ ┐
│ ┌ ─ ─ ─ ─ ┘
│ └ ─ ─ ─ ─ ┐
│ ┌ ─ ─ ─ ─ ┘
│ └ ─ ─ ─ ─ ┐
└ ─ ─ ─ ─ ─ ┘
铺砌理论作为组合几何中的一个范围广泛的领域,越来越受到人们的注目.要铺砌
的平面可以是任何形状----"有限的或无限的",瓷砖也可以形形色色,而且问题可能
会涉及不同形状的集合,而并非要求单一模式.不可能性证明还经常涉及以某种规定
的方式,用两种或两种以上的颜色为某一平面着色.
与多米诺骨牌相似的三维物体是砖块,其单位尺寸为1X2X4.用这种砖块"堆"成(空
间铺砌)一个4X4X4的箱体并不困难,但是用这种砖块可否堆成一个6X6X6的箱体?这
个问题完全可以应用布朗先生铺砌院子的问题的解法.设想把该立方体分成27个小
立方体,每个为2X2X2.把这些阶为2的立方体交替涂上黑白两种颜色,好似一个三维
的国际象棋棋盘.如果你把每种颜色的单位立方体的个数数一下,就会发现,一种颜
色的立方体比另一种颜色的多八个.
在那大立方体中,无论怎样放置砖块,不多不少总是恰恰"盖住"相同的数目的黑色
和白色的单位立方体,但一种颜色的单位立方体比另一种颜色的多八个,最初的26块
砖无论怎样放置,总会剩下同样颜色的八个单位立方体.因此无法安置第27块砖.如
果不厌其烦地探讨所有可能的堆砌方式,以求证明这一点,这样做显然极其费事.
堆砌理论仅是三维空间堆砌理论的一部分.关于空间堆砌问题,各种资料文献正日
趋增多.它们提出了大量悬而未决,引人入胜的问题,有许多问题的解法可应用于商
品的纸箱包装和堆仓等等.
奇偶性在粒子物理学方面也起着很重要的作用.1957年,两名中国血统的美国物理
学家(指杨振宁,李政道)因为他们在推翻著名的"宇称守恒定律"方面的贡献而获得
诺贝尔奖金.但由于这一题目专业性太强,故此不做详述.但可以举一个有趣的硬币
戏法的例子来说明奇偶性守恒的一种方式.
往桌子上抛一把硬币,数一下正面朝上的有多少,若是偶数,则称正面朝上的硬币
具有偶数性;若是奇数,则称其具有奇数性.现在把一对硬币翻身,再翻第二对,第三
对,任你翻转多少对.你将惊奇地发现,无论翻转多少对,正面朝上的硬币的奇偶性始
终不变.如果原来是奇数性,那么还是保持奇数性;如果原先是偶数性,则始终保持偶
数性.
利用这一点可以耍一个巧妙的魔术.你背过身去,请人随心所欲地把硬币一对一对
地翻转,再请他用手盖住其中任何一枚.然后,你回过身来,瞧一瞧硬币,即可正确地
说出他手掌下的硬币是正面朝上还是反面朝上.秘诀是开始时数一下正面朝上的硬
币有多少,记住是奇数还是偶数.由于一对一对地将硬币翻转并不会影响其原来的奇
偶性,所以你只要在最后再把正面朝上的硬币数一下,就可确定被盖住的那枚硬币是
正面朝上还是反面朝上了.
还有一个变相的问题:请他用手盖住两枚硬币,你再说出盖住的那一对硬币其朝上
一面是否相同.许多心算扑克牌花样的巧妙魔术都是利用奇偶校验来设计的.
------------------------------------------------------------------------
--------
9.多少只动物
这是久违的奎贝尔教授.奎贝尔教授:"我又为你们想出一个问题.在我饲养的动物
中,除了两只以外所有的动物都是狗,除了两只以外,所有的都是猫,除了两只以外所
有的都是鹦鹉,我总共养了多少只动物?你想出来了吗?
奎贝尔教授只养了三只动物:一只狗,一只猫和一只鹦鹉.除了两只以外所有的都
是狗,除了两只以外所有的都是猫,除了两只以外所有的都是鹦鹉.
如果你领悟到"所有"这个词可以指仅仅一只动物的话,头脑中就有了这个问题的
答案.最简单的情况--- 一只狗,一只猫,一只鹦鹉---既是其解.然而,把这个问题用
代数形式来表示也是一次很好的练习.
令x,y,z分别为狗,猫,鹦鹉的只数,n 为动物的总数,我们可以写出下列四个联立
方程:
n=x+2
n=y+2
n=z+2
n=x+y+z
解此联立方程有许多标准方法.显然,根据前三个方程式,可得出x=y=z.由于
3n=x+y+z+6减去第四个方程,得到 n=3,因此x+2=3,所以x=1.全部答案可由x值求得
.
由于动物只数通常是正整数(谁养的猫是用分数来表示只数的?),可以把奎贝尔教
授的动物问题看作所谓刁番图问题的一个平凡例子.这是一个其方程解必须是整数
的代数问题.一个刁番图方程有时无解,有时只有一个解,有时有不止一个或个数有
限的解,有时有无穷多个解.下面是一个难度稍大的刁番图问题,同样也与联立方程
和三种不同的动物有关.
一头母牛价格10元钱,一头猪价格3元钱,一头羊价格0.5元钱.一个农夫买了一百
头牲口,每种至少买了一头,总共花了100元钱,问每种牲口买了多少头?
令x为母牛的头数,y为猪的头数,z为羊的头数,可以写下如下两个方程式:
10x+3y+z/2=100
x+y+z=100
把第一个方程中的各项都乘以2消去分数,再与第二个方程相减以便消去z,这样得
到下列方程式:
19x+5y=100
x和y可能有那些整数值?一种解法是把系数最小的项放到方程的左边:
5y=100-19x,把两边都除以5得到:
y=(100-19x)/5
再把100和19x除以5,将余数(如果有的话)和除数5写成分数的形式,结果为:
y=20-3x-4x/5
显然,表达式4x/5必须是整数,亦即x必须是5的倍数.5的最小倍数既是其自身,由
此得出y的值为1,将x,y的值带入任何一个原方程,可得z等于94.如果x为任何比5更
大的5的倍数,则y变为负数.所以,此题仅有一个解:5头母牛,一头猪和94头羊.你只
要把这个问题中牲口的价钱改变一下,便可以学到许多初等刁番图分析的知识.例如
,设母牛价钱为4元钱,猪的价钱为2元钱,羊的价钱为三分之一元钱,一个农夫准备花
一百元钱买一百头牲口,并且每种牲口至少买一头,试问他每种牲口可以买多少头?
关于这一问题,恰好有三种解.但是如果母牛价钱为5元钱,猪的价钱为2元钱,羊0.5
元钱呢?那就无解.
刁番图分析是数论的一大分支,其实际应用范围极广.有一个著名的刁番图问题,
以费马最后定理而著称:设有方程xn+yn=zn,其中n是大于2的正整数,问此方程是否
有整数解(如果n=2,则称此为毕达格拉斯三元数组,具有自32+42=52起始的无穷多组
解)?这是一个最著名的数论问题,已经由英国数学家安德鲁.威尔斯解决,他用于解
决此问题的方法可以说是大大出乎人们的意料,他应用了一种叫做椭圆函数的理论
,实际上,他证明的并不是方程本身,而是在椭圆函数领域中另一个著名的猜想: 谷
山-志村猜想.由于椭圆函数的模形式与费马最后定理同构,所以,等于是从侧面攻破
了这个300多年的大难题.
------------------------------------------------------------------------
--------
10.药品混乱
一家药店收到运来的某种药品十瓶。每瓶装药丸1000粒。药剂师怀特先生刚把药
瓶送上架子，一封电报接踵而来。怀特先生把电报念给药店经理布莱克小姐听。
怀特先生：“特急！所有药瓶须检查后方能出售。由于失误，其中有一瓶药丸每
粒超重10毫克。请即退回分量有误的那瓶药。怀特先生很气恼。
怀特先生：“倒霉极了，我只好从每瓶中取出一粒来秤一下。真是胡闹。
怀特先生刚要动手，布莱克小姐拦住了他。布莱克小姐：“等一下，没必要秤十
次，只需秤一次就够了。这怎么可能呢？
布莱克小姐的妙主意是从第一瓶中取出1粒，从第二瓶中取出2粒，第三瓶中取出
3粒，以此类推，直至从第十瓶中取出10粒。把这55粒药丸放在秤上，记下总重量
。如果重5510毫克，也就是超过规格10毫克，她当即明白其中只有一粒是超重的，
并且是从第一瓶中取出的。
如果总重量超过规格20毫克，则其中有2粒超重，并且是从第二瓶中取出的，以
此类推进行判断。所以布莱克小姐只要秤一次，不是吗？
六个月后，药店又收到此种药品十瓶。一封加急电报又接踵而至，指出发生了一
个更糟糕的错误。
这一次，对超重药丸的瓶数无可奉告。怀特先生气恼极了。怀特先生：“布莱克
小姐，怎么办？我们上次的方法不中用了。布莱克小姐没有立即回答，她在思索这
个问题。
布莱克小姐：“不错。但如果把那个方法改变一下，我们仍然只需秤一次就能把
分量有误的药品识别出来。这回布莱克小姐又有什么好主意？
在第一个秤药丸问题中，我们知道只有一瓶药丸超重。从每瓶中取出不同数目的
药丸（最简单的方式就是采用计数序列），我们就可使一组数字和一组药瓶成为一
一对应的关系。
为了解决第二个问题，我们必须用一个数字序列把每瓶药单独标上某个数字，且
此序列中的每一个子集必须有一个单独的和。有没有这样的序列？有的，最简单的
就是下列二重序列：1，2，4，8，16，。。。这些数字是2的连续次幂，这一序列
为二进制记数法奠定了基础。
在这个问题中，解法是把药瓶排成一行，从第一瓶中取出1粒，从第二瓶中取出
2粒，从第三瓶中取出4粒，以此类推。取出的药丸放在秤上秤一下。假设总重量超
重270毫克，由于每粒分量有误的药丸超重10毫克，所以我们把270除以10，得到
27，即为超重药丸的粒数。把27化成二进制数：11011。在11011中自右至左，第一
，二，四，五位上的“1”表示其权值分别为1，2，8，16。因此分量有误的药瓶是
第一，二，四，五瓶。
在由2的幂组成的集合中，每个正整数是单一的不同组合中的元素之和。鉴于这
一事实，二进制记数法极为有用。在计算机科学和大量应用数学领域中，二进制记
数法是必不可少的。在趣味数学方面，同样也有难以计数的应用。
这里有一个简单的扑克魔术，可叫你的朋友莫名其妙。这个戏法也许看上去与药
瓶问题毫无关系，但他们的依据是相同的，都是二进制原理。
请别人把一副牌洗过，然后放进你的口袋，再请人说出一个1至15以内的数字。
然后你把手插进你的口袋里，一伸手就取出一组牌，其数值相加正好等于他所说的
数字。
此秘密简单的很。在耍魔术之前，预先取出A，2，4，8各一张放入口袋。这副牌
缺少区区四张，不大可能为人察觉。洗过的牌放入口袋后，暗中将其排置于原先已
经放在口袋中的四张牌的后面。请别人说出一个数字，你用心算将此数表示成2的
幂的和。如果是10，那你就应想到：8+2=10，随即伸手入袋，取出2和8的牌示众。
卜算卡片的依据也是二进制原理，准备六张卡片，分别记为A，B，C，D，E，F。
然后将一些数字填写在卡片上，确定每张卡片上的数字集合的规则是这样的：在一
个数的二进制表示中，若右起第一位是“1”，则此数字就在卡片A上。该卡片上的
数字集合自1起始，全部数字就是1至63范围内所有的奇数；卡片B则包括1至63范围
内的二进制记数法中右起第二位为“1”的全部数字；卡片C包括1至63范围内的二
进制记数法中右起第三位为“1”的全部数字；卡片D，E，F以此类推。注意：63这
个数字的二进制记数法是“111111”，每一位都是“1”，因此每张卡片上都有这
个数字。
这六张卡片可以用来确定1至63范围内的任意一个数字。请一位观众想好此范围
内的一个数字（例如某个人的年龄），然后请他把所有上面有此数字的卡片都交给
你。你随即说出他心中所想的那个数字。秘诀就是把每张卡片上2的幂的第一个数
字相加。例如，如果把卡片C和F交给你，你只要将上面第一个数字4和32相加，便
知道别人心中所想的数字是36。
有时，魔术师为了使得这个戏法显得更加玄妙，故意把每张卡片涂上各种不同的
颜色。他只需记住每种颜色所代表的2的幂。例如，红卡片代表1，橙卡片代表2，
黄卡片代表4，绿卡片代表8，兰卡片代表16，紫卡片代表32（可依据彩虹的诸色顺
序）于是，魔术师站在大房间的一头，请人想好一个数字，并且把上面有此数字的
卡片置于身旁，他即可根据那人身旁的卡片的颜色随口说出别人心中所想的数字。
------------------------------------------------------------------------
--------
11.巧断金链
一位来自阿肯色州的年轻太太格罗丽亚,正在加利福尼亚州旅行.她想在旅馆租用
一个房间,租期一周.办事员此时正心绪不佳.办事员:"房费每天20元,要付现钱.格
罗丽亚:"很抱歉,先生,我没带现钱.但是我有一根金链,共7节,每节都值20元以上.
办事员:"好吧,把金链给我." 格罗丽亚:"现在不能给你.我得请珠宝匠把金链割
断,每天给你一节,等到周末我有了现钱再把金链赎回.办事员终于同意了,但格罗丽
亚必须决定如何断开金链的方法.格罗丽亚:"我该三思而行,因为珠宝匠是按照他所
切割和以后重新连接的节数来索价的.格罗丽亚想了一下,悟到她不必把每一节都割
断,因为她可以把一段段金链换进换出,以这种方式来付房费.当她算出需要请珠宝
匠割断的节数时,她几乎不能自信.你想一想需要割开多少节?
只需要割开一节.这一节应是从一端数起的第三节.把金链断开成1节,2节,4节这
样三段后就能以换进换出的方式每天付给办事员一节作为房费.
啊哈!领悟到下列两点才能解题.第一,至少需要有1节,2节,4节这样三段(即其节
数成二重级数的一些段),这样才能以各种不同的组合方式组成1节,2节,3节,4节,5
节,6节和7节.我们在药品混乱问题中已经知道,这就是作为二进制记数法基础的幂
级数.
第二,只需要割开一节就可以把金链分成符合要求的三段.关于这个问题,若把金
链的长度增加,则可以想出一些新的问题.例如,假设格罗丽亚有一根63节的金链,她
想把金链割开,以上面那种方式来付63天的房费(价格不变).要达到此种目的只需要
割开三节.你想出来了吗?你能否根据金链的不同长度设计一个通用的解题程序,要
求分割开的节数为最少?
有一个有趣的变相问题:若所经手的 n 节首尾相连的闭合回路,例如说格罗丽亚
有一串金项链,由79节相连而成,若每天房费为一节,试问最少需要分割开几节才能
支付79天房费?
所有这些问题都跟二进制记数法有密切的关系.比如格罗丽亚的63节金项链如何
分割?只要将63化成二进制表示:等于"111111"即63=1+2+4+8+16+32只要将从第二节
开始的两节割开,再将从第八节开始的八节割下来,和从第32节开始的32节割下来即
可,这样就有了从1,2,3,4,5,6,直到63的所有节数.一般地,若有 n 节金链, n 是形
如 2k-1类型的数,将 n 化成二进制表示,再将所有"1"的位置所代表的2的幂的数相
间隔地割开即可达到目的.但是对于其他任意类型的数,却不能奏效,比如对于格罗
丽亚的79节金项链,79的二进制记数法表示为"1001111".即79=1+2+4+8+0+0+64,这
样从1到15都能表示,可是从16到63都没法表示,我把这个问题做到这里,也一时糊涂
起来,但这个问题毕竟不是很复杂,咱们也学一学闵科夫斯基在课堂上口出狂言要解
决四色问题的劲头,摸索着来解决一把.咱们可以这样:你不是要求节数最少吗?假设
n=a+b 其中 a 是已经找到的最大的那一节数,b 是比 n 小的已经解决了的金链问
题,由于 b 已经解决,因此 b 的拆分能够表示从1,2,3,...b-1,b 的所有金链节数
,而再大一些的数就不能够表示了,比如 b+1,所以必须要 a 参加进来,如果 n 是奇
数,可令 a=b+1,这样 n=2b+1,所以 b=(n-1)/2,a=(n+1)/2,这样就找到了最大的一
节的节数 a ,然后对 b=(n-1)/2继续应用如上的办法,即可解决问题.如果 n 是偶
数,可令 a=b ,这样虽然 a 本身不能表示出 b+1,但是可以从 b 的拆分中拿出一个
1来(这个1是必须存在的,因为要表示从1,2,3,...b-1,b的所有数)与 a 组成 a+1
也就是 b+1.所以 n=a+b=2a=2b,a=b=n/2.这样也找到了 n 为偶数时最大的一节金
链的节数.对于 b 继续如上的过程,就可以找到全部应该断开的金链节数,我算出了
从1到15的所有拆分如下:
1=1
2=1+1
3=1+2
4=1+1+2
5=1+1+3
6=1+2+3
7=1+2+4
8=1+1+2+4
9=1+1+2+5
10=1+1+3+5
11=1+1+3+6
12=1+2+3+6
13=1+2+3+7
14=1+2+4+7
15=1+2+4+8
对于上面的格罗丽亚太太的79节金项链,79+1=80,80/2=40,所以最大的一节就是
40节,79-40=39,39+1=40,40/2=20,所以第二大的一节就是20节,39-20=19,
19+1=20,20/2=10,第三大的一节是10节,19-10=9,9+1=10,10/2=5,又找到了一节是
5,9-5=4,4的表示法如上已经列出来了:4=1+1+2.最后得到79节的金项链的分割法:
1,1,2,5,10,20,40.过去我也碰到过一道类似的题,是23节金项链,也能够很容易地
解决:23+1=24,24/2=12;23-12=11,11=1+1+3+6;所以23的分割法为:1,1,3,6,12.显
然,对于2k-1类型的数,用这里的办法与用二进制记数法得出的结果是一致的.
从上面所列出的拆分法可以看出,如果 2k=<n<2k+1,那么 n 一定要用 k+1个数来
表示,即: n=a0+a1+a2+...+ak.
可以用数学归纳法很容易地证明这是正确的.那么还有没有比这更少的分割法呢?可
以证明没有了.从我们的分析方法中可以看出,这是一个构造性的推理过程,假如还
有比这更少的分割法,那么相当于在表达式 n=a0+a1+a2+...+ak.中进行了某些组合
,比如将a1+a2合并成新的a1,那么原来的有些组合就表示不出来了,例如a0+a2,就没
有办法组合了.当然,一个数的拆分不是唯一的,前面的23节金链还可以分成1,2,3,
6,11.你可以试试,这种分割法照样能满足要求.前面的分析中也可以把 (n-1)/2 留
下来作为最大的节数,但是这样分出来的节数就不一定都是最少的了,例如把15这样
分割,会得到:1,1,2,4,7.虽然能够满足付房费的要求,但是就不是最优解了.最后总
结一下,把前面的算法过程公式化可以得到:
k-1 r-1 k-1
n=(n+c0)/2+ ∑ {[n-∑cs2s+cr2r]/2r+1}+[n-∑cr2r]/2k
r=1 s=0 r=0
其中c0,c1,...ck-1等等是1或是0取决于每一步得出的数的奇偶性.其实最后一项
等于1,这样可以得出:
k-1
n-2k = ∑cr2r
r=0
a0=(n+c0)/2
i-1
ai=[n-∑cs2s+ci2i]/2i+1 1 (i=1,2,3,...k-1)
s=0
ak=1
当然,编成计算机程序还是用递归程序比较简单.这里列出这些公式是为了保留存
照.
------------------------------------------------------------------------
--------
12.巧分乳酪
乔记餐馆虽说吃食不算最好，但却以美味乳酪而远近闻名。块块乳酪状如圆盘，
绕有风趣。一刀下去，就把一块乳酪一切为二。连切两刀，不难将其分成四块，三
刀则切成六块。一天，女招待罗西请乔把乳酪切成八块。乔：“好，罗西。很简单
，我只要这样切四刀就成了。罗西把切好的乳酪往桌子上送时，忽然悟到乔只需要
切三刀便可以把乳酪分成八块。罗西想出了什么妙主意？
罗西豁然开朗，悟到圆柱形乳酪是一个立体图形，可以在中线处横截一刀将其一
切为二。如果允许移动切开的部分，那么连切三刀也行。可以把第一次切开的两块
迭放在一起，切第二刀成四块，再把四块跌放在一起，最后一刀切成八块。罗西的
解法是如此简单，几乎可以说是平凡的。然而它给人以明确的启示：对于有意义的
切分问题，可以用有限差分演算进行研究并用数学归纳法加以证明。有限差分演算
是发现数字序列普通项公式的有力工具。今天，数字序列日益引起人们的兴趣，因
为它具有极其广泛的实际应用范围，还因为计算机能够以极快的速度执行序列的运
算。
罗西第一次切乳酪的方法是在乳酪顶面的若干中线同时切数刀。乳酪具有如同薄
饼那样平坦的顶面。让我们来观察一下，根据在一张薄饼上切数刀的过程，能够生
成一些什么数字序列。假如沿着薄饼若干中线同时切数刀，显然，同时切 n 刀至
多可以切出2n块。
若在其边沿为一条简单闭合曲线的任意平面上同时切下 n 刀，这种方法所切成
的块数，是否最多也是 2n块呢？否。可以随意画出许多既非凸面，并且形状各异
的平面，即使一刀也可切成你所希望的块数。能否画出一种图形，仅切一刀便可以
切出任何有限数目的全等的块？若能办到，这种图形的周长应具有什么特性，才能
确保只需要一刀便可以切成全等的 n 块？若不同时进行切分，薄饼的切分将更为
有趣。你很快会发现：仅当 n〉=3 时，切 n 刀方可切成不止 2n 块。
这里，我们并不考虑所切成的块是否全等或面积相同。当 n=1，2，3，4。。。
时，可以切成的最多块数分别是2，4，7，11。这一大家所熟悉的序列是根据下列
公式求得的：
1+n（n+1）/2
其中，n 是所切的刀数。此序列的前10项（n 自0开始）是1，2，4，7，11，16
，22，29，37，46。。。
请注意，第一行差分是1，2，3，4，5，6，7，8，9。。。第二行差分是1，1，
1，1，1，1，1，1，1，。。。
这强烈地暗示着此序列的普通项是一个二次项。
为什么说“强烈暗示”呢？因为虽然可以用有限差分演算找到一个公式，但是并
不能保证该公式对于无限序列也成立。这一点尚需证明。在薄饼公式这一例子中，
不难通过数学归纳法做出一个简单的证明。
从这点出发，你可以发现大量的引人入胜的研究方向，其中有许多将导致非同寻
常的数字序列，公式以及数学归纳法证明。这里有一些问题可供你作为初步尝试。
采用下列各种方法，最多可以切成几块？
1。在马蹄形的薄饼上切 n 刀。
2。在球形或罗西所切的那种圆柱形乳酪上切 n 刀。
3。用切小圆甜饼的刀在薄饼上切 n 刀。
4。在状如烛环状（即中心有一个圆孔）的薄饼上切 n 刀。
5。在油炸圈（圆环）上切 n 刀。
关于以上这些问题，假设切分是同时进行的，若改成连切方式，并且允许重新安
排切开的部分，其答案如何变化？
------------------------------------------------------------------------
--------
13.隐蔽的尺寸
在城市广场的中央有一片很大的圆形憩息地。市议会拟在该地建造一个菱形浅
水池。多里斯。莱特市长看到这一计划，她找来了建筑师。莱特市长：“我喜欢呈
菱形的水池，用红瓷砖砌成，不知道这水池的每边有多长？”建筑师弗兰克。劳埃
德。朗被问住了。朗先生：“从A至B是5米，从B至C是4米。唔，应求出BD。也许我
需要应用毕达格拉斯定理。朗先生正疑惑不解，市长阁下忽然叫起来。莱特市长：
“啊哈！水池每边长为9米，这是毫无疑问的。”
朗先生：“我的天哪！怪不得你姓莱特（Wright）我姓朗（Wrong）呢。”有了
什么好主意使这个问题迎刃而解？
既是对角线又是半径
莱特夫人忽然悟到水池每边即为矩形的对角线。这个矩形的另一条对角线就是圆
形栖息地的半径。而矩形的两条对角线是相等的，所以水池每边边长就是圆半径的
长度。半径是5+4=9米，因此水池每边也是9米，无需应用毕达格拉斯定理。
你再找一种更简便的方法试试看，这样你就更能体会我们这种解法的优点。如果
你仅应用毕达格拉斯定理和相似三角形，其解法一定很冗长，繁琐。但你如果想到
下列平面几何定理：一个圆的两条内部相交的弦，一条弦的两部分之积等于另一根
弦两部分之积，那么就可以得出稍微简短的解法。根据这一定理，可以求得直角三
角形的高为 √56，在应用毕达格拉斯定理，算出直角三角形的斜边为9。
有一个与此密切相关的问题，那就是诗人亨利。朗非罗在其小说《卡瓦诺》中所
提出的有名的水仙花问题。当水仙花花茎垂直时，花朵伸出水面10厘米。如果把水
仙花拉向一边，使花茎保持直线，花朵沾水的位置离原来的位置是21厘米，问水深
多少厘米？
要解这个问题，可以先画一张草图，此图与水池问题的图相似。我们要确定的就
是x的长度。与水池问题一样，这个问题也不止一种解法。若你还记得两弦相交的
定理，解这个问题是轻而易举的。
还有一个有趣的游泳池难题，灵机一动则迎刃而解。一条海豚位于一个圆形水池
的西边A点，它笔直地游了12米，鼻子触到水边的B点，转过身后，又笔直地游了5
米，到达水池边上的C点，此位置正好与水池边上的A点遥遥相对，试问如果它直接
从A点游向C点，需要游多长距离？
啊哈！要解决这个问题只需知道下列定理：半圆上的圆周角是直角，所以三角形
ABC是直角三角形。已知两直角边长分别为12米和5米，所以斜边为13米。上述问题
都给我们以启示：在许多情况下，如果思路正确，几何问题的求解会变得极其容易
。而要做到这一点，这取决于你是否想到了欧几里德几何的某个基本定理
1.泡泡糖问题
可怜的琼斯夫人路过泡泡糖出售机时,尽量不使她的双胞胎儿子有所察觉.
大儿子:"妈妈,我要泡泡糖."
二儿子:"妈妈,我也要,我要和比利拿一样颜色的."
分币泡泡糖出售机几乎空了,里面只有4粒白色的和6粒红色的泡泡糖.说不准下
一粒是什么颜色.琼斯夫人如果要得到两粒同种颜色的泡泡糖,需要准备花多少钱
?
是不是琼斯夫人需要花6分钱,准可以得到2粒红色的糖----就算所有白色的糖花
去4分钱,还有两分钱可以买到2粒红色的糖.或者她花去8分钱准可得到2粒白色的糖
,所以她需要花8分钱是吗?如果你这样算,那就错了,因为琼斯夫人并不要求必须得
到两粒红色的糖或者两粒白色的糖,她只要求两粒同色的糖,即使先取到两粒不同色
的糖,第三粒必定与前两粒中的一粒同色.所以她最多只需要花3分钱.
如果出售机内有6粒红色的,4粒白色的,5粒蓝色的.琼斯夫人最多要花多少钱?显
然只要花4分钱即可.
如果琼斯夫人的孩子是三胞胎,那该怎样呢?最坏的情况是她拿到了2粒红的,2粒
白的和2粒兰的,第七粒肯定与前六粒中的两粒同色,所以她最多需要花7分钱.
如果只有一粒蓝色的泡泡糖,那么显然只要花6分钱即可买到三粒同色的糖.
假如琼斯夫人是幼儿园的老师,她带着 k 个孩子路过泡泡糖出售机,出售机中有
n 组同色的泡泡糖,且每组糖至少有 k 粒,她需要花多少钱呢?
最坏情况是她每种颜色的泡泡糖都买了 k-1 粒,那么再买一粒即可,所以她最多
需要花 n(k-1)+1 分钱.
如果 n 组糖中有一组或几组同色的糖少于 k 粒,又是什么情况呢?
让我们假设有 m 组同色的泡泡糖少于 k 粒,并且设其中第 i 组糖有 ai 粒,那
么琼斯夫人最倒霉的事情是,她把所有少于 k 粒的同色糖都买了,并且其他种类的
糖每种都买了 k-1 粒,最后再买一粒才能得到 k 粒同色的糖.所以她最多需要花:
m
(n-m)(k-1)+1+∑ai
i=1
分钱.
这种类型的题目很多,又比如从52张纸牌中抽出7张同花的牌,那么最多需要抽多
少张牌呢?显然需要 4(7-1)+1=25 张.
------------------------------------------------------------------------
--------
2.乒乓球赛问题
某中学将举行乒乓球比赛,小明他们班有5人先进行淘汰赛,选出一人参加学校的
决赛,班主任杨老师计算了一下比赛的次数:"嗯,由于5是奇数,所以第一轮有一个队
员轮空,第二轮中还得出现一次轮空,一共需要进行4场比赛.选拔出一个队员后,学
校共有37个班级参加决赛,也采用淘汰赛,你知道需要多少场比赛吗?你还没有算出
来吗?哈哈!还在画表格呀?告诉你吧,每场比赛淘汰一名队员,一共要淘汰36名队员
,所以要进行36场比赛.不过,如果你想轻易地算出轮空的次数却没有这么容易,那么
,怎样计算轮空的次数呢?,请看如下的分析:
不知道你注意了没有,如果比赛人数正好是2的幂,那么轮空次数就是0,也就是说
,如果比赛人数是2,4,8,16,32等等,就不会出现轮空,如果不是这样类型的数,则至
少要有一次轮空.假设有n个队员参赛,如果是奇数,那么第一轮就有一名队员要轮空
,从第二轮开始的轮空数与(n+1)/2个队员参赛的轮空数是一样的,所以这时总的轮
空数是:(用L(n)表示n个队员参赛的轮空数)
L(n)=1+L((n+1)/2)
如果n是偶数,那么,第一轮没有轮空,从第二轮开始的轮空数与n/2个队员参赛的
轮空数是一样的,所以有:
L(n)=L((n)/2)
我们可以统一处理以上两个公式:
L(n)=a0+L((n+a0)/2)
其中a0为1或为0取决于n的奇偶性,下面的a1,a2,a3...也一样,假定2k<n<2k+1,并
且规定n>=2,因为最后总是冠亚军决赛,所以最后一场比赛总是2名队员.继续往下推
,我们有:
L(n)=a0+a1+L(a0/4+a1/2+n/4)
=a0+a1+a2+L(a0/8+a1/4+a2/2+n/8)
=a0+a1+a2+...+ak-1+L(a0/2k+a2/2k-1+...+ak-1/2+n/2k)
k-1 k-1
= ∑as+L(1/2k∑as2s+n/2k)
s=0 s=0
由于最后总有:
k-1
1/2k∑as2s+n/2k=2
s=0
即:
k-1
∑as2s=2k+1-n
s=0
我们看到,L(n)=a0+a1+a2+...+ak-1
所以,只要将2k+1-n化成二进制表示,其系数和就是轮空数,也就是其中1的个数.
对于n=37,我们可以算出2k+1-n=64-37=27=11011,其中有4个1,所以共有四次轮空.
------------------------------------------------------------------------
--------
3.玻璃杯问题
巴尼在汽水柜台工作,他用10只玻璃杯给两名顾客出了个难题.巴尼:"这一排有
10只玻璃杯,左边5只内有汽水,右边5只空着,请你使这排杯子变成满杯与空杯相互
交错,条件是只允许移动4只杯子."两位顾客看了看巴尼,又看了看杯子,摇了摇头,
不知道怎么办.巴尼:"好吧,我来告诉你们,只要分别把第二只杯子和第七只杯子,第
四只杯子和第九只杯子交换一下位置就成了."
这时,奎贝尔教授正好来到柜台前,看到了他们的把戏,并且来了点小花招.奎贝尔
教授:"何需移动四只杯子,我只要移动两只就行了,你行不行?"
巴尼纳闷地瞧着奎贝尔教授,不明就里.奎贝尔教授:"很简单,只要拿起第二只杯子
,把里面的汽水倒进第七只杯子,再拿起第四只杯子,把里面的汽水倒入第九只杯子
就行了."
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
■■■■■□□□□□--->■□■□■□■□■□
虽然奎贝尔教授抓住话语间的模棱两可之处解决了这个问题,但这个问题并不像
乍看上去那么简单.例如,还是这么个问题,但改成100只满杯挨着100只空杯排成一
排,请考虑一下,若要使其变成满杯和空杯交错排列,需将多少对杯子互换位置?显然
,一般地,如果有2n只杯子,n只满杯,n只空杯,需要将[n/2]对杯子互换位置,方法是
2k号杯子与2k+n号杯子互换位置即可(k=1,2,3,...)若n=100,则需互换50次.
有一个与上面分析的问题类似但困难的多的古典难题.咱们这回用两种不同颜色
的杯子作为道具,但是移动方法却大相径庭:每次只能一块儿移动一对相邻的杯子,
使结果成交错排列,以n=3为例,解题过程如下图所示:
1 2 3 4 5 6
■■■□□□
■□□□■■
■□□ ■□■
□■□■□■
普遍的解是什么呢?当n=1时,没有意义,n=2时你会发现,无解,当n>2时,解此问题
至少需要移动n次.n=4时,求解很不容易,你不妨试试,煞是有趣,或许你能够把当
n>=3时的解题过程公式化.不像上两道题比较容易,这个问题我还没有仔细研究过,
先把这道题上载,大家也可以发表意见.
根据这一难题还可以产生许多奇异的变相问题,用来测验你的智力.这里试着举几
例:
(1).仍然是同时移动两只相邻的杯子,但是如果颜色不同,则要在移动过程中
交换位置,这样一对黑白的杯子就变成一对白黑排列了.解8只杯子需要移动5次.对
于10只杯子,5次移动也够了.我还尚不知道他的普遍解,也许你能找出来.
(2).某种颜色的杯子少一个,即某种颜色的杯子有n只,另一种杯子有n+1只,
其余规则不变,已经证明(不好意思,不是我证的,我还没有仔细研究过),对于任意n
只杯子,其解须作n次移动,而且这是最少的移动次数.
(3).使用三种不同颜色的杯子.按照通常的方法移动一对相邻的杯子,使得所
有这三种颜色交相辉映.当n=3(共有9个杯子),其解需要作5次移动.在这些变相问题
中,假设在最终形成的排列中,不允许留有任何空距.如果允许留有空距,则问题的解
法就令人惊奇地变为移动4次了.
看来,尚有许多其他的变化形式,例如,假设一次可以同时移动3只或更多的杯子,
在上述各变相问题中改用这种移动方式,结果会如何呢?假如是第一次移动1只杯子
,第二次移动2只杯子,第三次移动3只杯子,依次下去,那又会怎样?给定某种颜色的
杯子n个,另一种颜色的杯子也为n个,这个问题的解是否总是作n次移动?这种种问题
都有待于人们去解决,我还没有时间来考虑这些问题,这是非常有趣非常值得人们思
考的趣题.
------------------------------------------------------------------------
--------
4.怕斯卡三角形与道路问题
苏珊很为难.她步行去学校,路上老是遇到斯廷基.斯廷基:"嘿嘿,苏珊,我可以陪
你一起走吗?" 苏珊:"不!请走开."
苏珊心想:我有办法了.每天早上我走不同的路线去学校.这样斯廷基就不知道在哪
儿找到我了.这张地图表示苏珊的住所和学校之间的所有街道.苏珊去学校时,走路
的方向总是朝南或朝东.她总共有多少条路线呢?
苏珊:"我真想知道有多少条路线可走.让我想一想.要算出多少条路线看来并不
简单.嗯.啊哈!一点不难,简单的很!"苏珊想到了什么好主意?
她的推理如下:苏珊:"在我家这个角点上写一个1,因为我只能从这一点出发.然后在
遇刺相隔一个街区的两个角点上各写一个1,因为到那里只有一条途径.现在,我在这
个角点上写上2,因为到达那里可以有两条途径.苏珊发现2是1加1之和,她忽然领悟
:若到某一个仅有一条途径,则该角点上的数字为前一个角点上的数字;若有两条途
径,则为前两个角点上的数字之和.
苏珊:"瞧,又有四个角点标上了数字,我马上把其他角点也标上数字."请你替苏
珊把剩下的角点标上数字,并且告诉她步行到学校共有多少条不同的路线.
苏珊的家H
1
1
1
2
1
3
2
5
学校 G
剩下的5个点,自上而下,从左至右分别标以1,4,9,4,13.最后一点上的13表示苏
珊去学校共有十三条最短路径.
苏珊所发现的是一种快速而简单的算法,用来计算从她家到学校的最短路径共有
多少条.要是她把这些路径一条一条地画出来,然后再计数,这样肯定麻烦,还容易出
错.如果街道的数目很多,那么这种方法根本就行不通.你不妨把这十三条路线都画
出来,这样你就更能体会到苏珊的算法是多么地有效了.
你对这种算法是否已经理解,可以再画一些不同的街道网络,然后用这种算法来确
定从任意点A到另一任意点B的最短路线共有多少条.网络可以是矩形网格,三角形网
格,平行四边形网格和蜂窝状的正六边形网格.也可以用其他方法(例如组合公式)求
解,但这种方法十分复杂,需要很高的技巧.
在国际象棋棋盘上,"车"从棋盘的一角到对角线上另一角的最短路径共有多少条
?就像苏珊给街道交点标上数字一样,把棋盘上所有格子也都填上数字,于是问题就
迎刃而解了."车"只能沿着右上方向朝另一个角的目标移动,便可以求出共有多少条
最短路径.如图所示:
1 8 36 120 330 792 1716 3432
1 7 28 84 210 462 924 1716
1 6 21 56 126 252 462 792
1 5 15 35 70 126 210 330
1 4 10 20 35 56 84 120
1 3 6 10 15 21 28 36
1 2 3 4 5 6 7 8
车 1 1 1 1 1 1 1
把整个棋盘正确标号,根据所标的数字,一眼就能看出在棋盘上从一个角出发到任
意一角,有多少条最短路线.右上角的数字是3432,所以"车"从一角到对角线的另一
角的最短路径共有3432条.
让我们把棋盘沿着左上至右下的对角线一截为二,使其成为如下图所示的阵列.此
三角形上的数字与著名的怕斯卡三角形(我国叫做杨辉三角形)的数字是相同的,当
然,计算街道路径条数的算法,恰恰就是构造怕斯卡三角形所依据的过程.这种同构
现象使得怕斯卡三角形成为无数有趣特性的不竭的源泉.
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
...........
利用怕斯卡三角形立即可以求出二项式展开的系数,即求(a+b)的任意次幂,同样
也可以用来解出初等概率论中的许多问题.请注意,上图中自顶部至底部,从边沿一
格来说是1,随着向中间移动,数字逐渐增加.也许你见过根据怕斯卡三角形所制成的
一种装置:在一快倾斜的板上,成百个小球滚过木钉进入各格的底部.全部小球呈现
出一条钟形的二项式分布曲线,因为到达每个底部孔位的最短路径的条数就是二项
式展开的系数.
显然,苏珊的算法同样适用于由矩阵格子组成的三维结构.设有一个边长为3的立
方体,分成27个立方体单元,把它看成棋盘,处于某一个角格上的"车"可以向三个坐
标上的任何位置作直线移动,试问"车"到空间对角线的另一个角格有多少条最短路
径?
------------------------------------------------------------------------
--------
5.错抱的婴儿
在某个医院,四个婴儿的身份标签被搞错了.两个婴儿的标签不错,其他两个婴儿
的标签弄错了.发生这种错误的情况有多少种?
一种简单的计算方法是把所有可能的情况列成一个表格,其结果表明两个婴儿搞错
的情况共有六种.现在假设标签搞乱了后,恰有三个是正确的,只有一个搞错了,问这
个问题有多少种不同情况?你是否用列表的方法求解?还是凭灵机一动想出来的?
A B D C
A D C B
A C B D
D B C A
C B A D
B A C D
这个问题许多人都茫然不解,其原因是他们作了下列错误的假设:在四个婴儿中
,三个婴儿与其标签相符的情况有许多种.但是你如果用"鸽笼原理"思索一下,情况
就一清二楚了.假设有四个鸽笼,一一标出应放物品的名称.若三样物品都放在了正
确的位置中,那么第四样物品只有一处可放,自然该处即为那件物品应放的位置,正
确的可能只有一种,即所有四样物品都放置恰当这一情况,而不可能有其他更多的情
况.一般地,如果 n 件物品,其中已经有 n-1件放对了地方,那么剩下的一件也必定
放置在正确的位置上了.
有一个关于三样东西都标签错误的古典问题.一旦领悟到可以把情况的数目缩
小为1,这个问题也就迎刃而解了.设在桌子上有三个盖着盖子的盒子,其中一个盒子
内有两粒绿豆,第二个盒子内有两粒红豆,另一个盒子内有一粒绿豆和一粒红豆,三
个盒子盖子上分别写着"红豆","红绿豆"和"绿豆",但是所有标签都标错了.你能从
任意一个盒子内取出一粒豆子后,便能判断出所有盒子内都装着什么豆子吗?
同上面的讨论一样,人们一般总是首先考虑有多少种不同的可能性,但是你如果
能够洞悉底蕴,一眼就可以看出只可能有一种情况,从误标为"红绿豆"的盒子中取出
一粒豆子,如果不是一粒绿豆就是一粒红豆,若是一粒绿豆,那么盒子里的另一粒也
必定是一粒绿豆,那么两粒红豆必定在标着"绿豆"的盒子内,反之,若取出的是一粒
红豆,那么另一粒必定也是红豆,两粒绿豆肯定放在标着"红豆"的盒子内,其他一盒
内的情况就一清二楚了.可以看出,三个盒子全都误标的情况只可能有如上两种.从
标着"红绿豆"的盒子内取出一粒便可以排除一种情况,仅剩下唯一正确的情况.
有时,上述问题也会以稍微复杂的形式出现.在三个盒子中,从任意一个盒子内
取出最少的豆子数进行试看,以此来判断三个盒子内各装有什么豆子.唯一的办法是
从标着"红绿豆"的盒子中取出一粒豆子试看.也许你能提出一些更加复杂的问题,诸
如每个盒子内不只两粒豆子,或者盒子不只三个等等.
其他许多发人深省的难题都与上面的婴儿问题有关,同样也涉及到初等概率论
.例如,假设婴儿的标签以随机的方式搞乱,那么四个标签全部正确的概率是多少?全
部弄错的概率是多少?至少有一个正确的概率是多少?恰好有一个正确的概率是多少
?至少有两个正确的概率是多少?恰好有两个正确的概率是多少?最多有两个正确的
概率又是多少?诸如此类,不一而足.
"至少一个"的问题,就一般的形式来说,属于古典趣味数学著作中的问题.这个
问题通常如下所述:在一家旅店,由 n 个人在仔细检查自己的帽子.寄存部的粗心女
郎没能使寄存牌和帽子做到一一对应,她随便地把寄存牌发了出去,问至少一人取回
自己的帽子的概率是多少呢?结果发现,当 n 增大时,其概率迅速地趋近于极限
(1-1/e),或者说比1/2稍微好一点,其中 e 是著名的欧拉常数,等于2.
71828182845904590...,在概率论问题中经常反复地出现.
------------------------------------------------------------------------
--------
6.塑料杯问题
奎贝尔教授出了个难题.奎贝尔教授:"取三个喝咖啡用的泡沫塑料空杯,把11枚
硬币投入杯子中,要求每一只杯子中的硬币数目都是奇数.奎贝尔教授:"这不难做到
,是吗?方法很多,你可以在一只杯子中放入一枚硬币,第二只杯子中放入三枚硬币,
最后一个杯子中放入七枚硬币.这的确很容易.奎贝尔教授:"但是,你能否把十枚硬
币放入同样的杯子中,使得每只杯子中的硬币数都是奇数?这也是能够办到的,不过
你得动点脑筋才行.奎贝尔教授:"但愿你还没有泄气.你只要想到把其中一只杯子放
入另一只装着偶数个硬币的杯子中,就使每只杯子中都是奇数枚硬币了."
啊哈!一旦悟出杯中套杯,同一个集合的硬币可以属于不止一只杯子,这个棘手
的问题也就迎刃而解了.用集合论的术语来说,我们的解是7个元素的集合和3个元素
的集合,后一个集合又包含1个元素的子集.此解可以用图表示如下:
1
2
7
试求所有其余的解亦很有趣.要得到十个解并不困难,上述解法即为其中之一.但
若要发现其余的五个解,或者说十五个全部的解,却还需要花费一番精力.求出十五
个解之后,可以把硬币和杯子的数目,以及对于每只杯中放入硬币数的要求作一些改
变,从而产生一些新的问题.领悟到一个集合的部分或全部可以包含于另一个集合之
中,从而可以作两次计算,这是解决许多著名难题和悖论问题的钥匙.下面是一个趣
味问题.
一个男孩子逃学已经数周,学校考勤人员找到了他.小孩开始向他解释为何没有
时间上学:
"我每天睡觉需要8小时,8X365总共2920小时,一天有24小时,所以2920/24即
122天.
"星期六和星期日不用上学.一年总共约有104天.
"我们还有60天暑假.
"我一天吃饭需要花3小时,一年就要3X365,共有1095 小时,共有1095/24即45天
左右.
"我每天还需要2小时的课外活动.算起来一年也要有2X365,共730小时,或
730/24即30天左右."
小孩把所有这些天数相加如下:
睡觉 122
周末 104
暑假 60
用餐 45
课外活动 30
------
361天
"你瞧,"小孩说"仅剩下4天用作病假,我还没把学校每年应放的节假日算进去呢
!"
考勤人员听了后对小孩的数字研究了半天,看不出有什么破绽.请你的朋友们试
试这个悖论问题,看有多少人能够指出其谬误所在,即把子集不止一次地算进去.这
孩子所说的各项就像奎贝尔教授杯子中套杯子的硬币一样重复地作了相加.
------------------------------------------------------------------------
--------
7.炙肉片的策略
约翰逊先生在户外有个炙肉架,正好能容纳2片炙肉.他的妻子和女儿贝特西都
饥肠辘辘,急不可耐.问怎样才能在最短时间内炙完三片肉.
约翰逊先生:"瞧,炙一片肉的两面需要20分钟,因为每一面需要10分钟.我可以
同时炙两片,所以花20分钟就可以炙完两片.再花20分钟炙第三片,全部炙完需要40
分钟."
贝特西:"你可以更快些,爸爸.我刚算出你可以节省10分钟."
啊哈!贝特西小姐想出了什么妙主意?
为了说明贝特西的解法,设肉片为A,B,C.每片肉的两面记为1,2.第一个10分钟
炙烤A1,和B1.把B肉片先放到一边.再花10分钟炙烤A2和C1.此时肉片A可以炙完.再
花10分钟炙烤B2和C2,仅花30分钟就炙完了三片肉,对吗?
这个简单的组合问题,属于现代数学中称之为运筹学的分枝.这门学科奇妙地向
我们揭示了一个事实:如果有一系列操作,并希望再最短时间内完成,统筹安排这些
操作的最佳方法并非马上就能一眼看出.初看是最佳的方法,实际上大有改进的余地
.在上述问题中,关键在于炙完肉片的第一面后并不一定马上去炙其反面.
提出诸如此类的简单问题,可以采用多种方式.例如,你可以改变炙肉架所能容
纳肉片的数目,或改变待炙肉片的数目,或两者都加以改变.另一种生成问题的方式
是考虑物体不止有两个面,并且需要以某种方式把所有的面都予以"完成".例如,某
人接到一个任务,把 n 个立方体的每一面都涂抹上红色油漆,但每个步骤只能够做
到把 k 个立方体的顶面涂色.
今天,运筹学用于解决事物处理,工业,军事战略等等许多领域的实际问题.即使
是像炙肉片这样简单的问题也是有意义的.为了说明这一点,请考虑下列一些变相问
题:
琼斯先生和夫人有三件家务事要办.
1.用真空吸尘器清洁一层楼.只有一个真空吸尘器,需要时间30分钟.
2.用割草机修整草地.只用一台割草机,需要时间30分钟.
3.喂婴儿入睡,需要时间30分钟.
他们应该怎样安排这些家务,以求在最短时间内全部完成呢?你看出这个问题与
炙肉片问题是同构的吗?假设琼斯先生和夫人同时进行操作,一般人开始往往以为做
完这些家务需要60分钟.但是如果一件家务(譬如说用真空吸尘器做清洁工作)分为
两个阶段,第二阶段延后进行(像炙肉片问题那样),那么三件家务可以在3/4的时间
内即45分钟内完成.
下面有一个关于准备三片热涂奶油的烤面包问题.这个运筹学问题比较困难.烤
面包架是老式的,两边各有一扇翼门,可以同时容纳两片面包,但是只能单面烘烤.如
果要烤双面,需要打开翼门,把面包片翻过身来.
将一片面包放入烤面包架需要时间3秒钟,取出来也需要3秒钟,将面包片在烤面
包架内翻身又需要3秒钟.这些都需要双手操作,即不能同时进行放,取或把两片面包
同时翻身,也不能在放入一片面包,将其翻身或取出的同时把另一片涂抹上奶油.单
面烘烤一片面包需要30秒钟,把一片面包涂抹上奶油需要12秒钟.
每片面包仅限于单面涂抹上奶油.未经烘烤不得事先在任何一面涂抹上奶油.单
面已经烤过的和涂抹上奶油的面包片可以重新放入烤面包加内继续烘烤其另一面.
如果烤面包架一开始就是热的,试问双面烘烤三片面包丙涂抹上奶油最少需要多少
时间?
在两分钟内完成上述工作并不太难.然而,如果你领悟到:一片面包在单面烘烤
尚未结束的情况下,也可以取出,以后再放回烤面包架内继续烘烤这一面,那么全部
烘烤时间就可以缩减至111秒钟.使你想到这一点,统筹安排这些操作使效率达到最
高也远非是一件易事.在这方面,尚有无数比此更为复杂的实际问题,需要借助于与
计算机和现代图论有关的高度复杂的数学手段.
------------------------------------------------------------------------
--------
8.难铺的瓷砖
布朗先生的院子里铺有40块四方瓷砖.这些瓷砖已经破损老化,他想予以更新.
他为修整院子选购新的瓷砖.可惜,目前商店里只供应长方形的瓷砖,每块等于原来
的两块.店主:"布朗先生,您需要几块?".布朗先生:"嗯,我要更换40块方瓷砖,所以
我估计需要20块."
布朗先生试着用刚买的新瓷砖铺院子,结果弄得烦闷不堪.不管他怎样努力,总
是无法铺好.
贝特西:"出了什么问题?爸爸?" 布朗先生:"这些该死的瓷砖,真叫人恼火.最后
总是剩下两个方格没法铺上瓷砖."
布朗先生的女儿画了一张院子的平面图,并且涂上了颜色,看上去好似一张棋盘
.然后她沉思了几分钟.
贝特西:"啊哈!我看出症结的所在了.请设想每块长方形瓷砖必定盖住一个红色
的格子和一个白色的格子,问题就清楚了."
这里面有什么奥妙,你理解贝特西的意思吗?
共有19个白色的格子和21个红色的格子,所以铺了19块瓷砖后,总要剩下2个红
格没有铺,而一块长方形瓷砖是无法盖住2个红格的.唯一的办法是把最后一块长方
形瓷砖断为两块.
A A B B C
K K L L M C D
J T S U M N D
J Q S R R N E
I Q P P O O E
I H H G G F F
布朗先生的女儿利用所谓"奇偶校验"解答了铺瓷砖问题.如果两个数都是奇数
或都是偶数,则称其为具有相同的奇偶性,如果一个数是奇数,另一个数是偶数,则称
其具有相反的奇偶性.在组合几何中,经常会遇到类似的情况.
在这个问题中,同色的两个格子具有相同的奇偶性,异色的两个格子具有相反的奇
偶性.长方形瓷砖显然只能覆盖具有相反奇偶性的一对格子.布朗小姐首先说明,把
19块长方形瓷砖在院子内铺上后,只有在剩下的两个方格具有相反的奇偶性时,才能
把最后一块长方形瓷砖铺上.由于剩下的两个方格具有相同的奇偶性,因此无法铺上
最后一块长方形瓷砖.所以用20块长方形瓷砖来铺满院子是不可能的.
数学中许多著名的不可能性的证明都建立在奇偶校验上.也许你很熟悉欧几里
德的著名证明:2的平方根不可能是一个有理数.证明是这样进行的:首先假设此平方
根可以表示成一个既约的有理分数,则分子和分母不可能都是偶数,否则它就不是一
个既约分数.分子,分母可能都是奇数或者一个是奇数,另一个是偶数.欧几里德证明
接着论证此分数不可能属于上述两种情况,换句话说,分子和分母不可能具有相同的
奇偶性或相反的奇偶性.而任何有理分数是两者必居其一,因而反证了2的平方根不
可能是一个有理数.
在铺砌理论中,有许多必定要用奇偶校验才能论证其不可能性的问题.上述问题只
是个极其简单的例子,因为它仅仅涉及用多米诺骨牌,即简单的,不平凡的波利米诺
来铺砌.(一个波利米诺是一些边沿相连的单位正方形的集合)布朗小姐的不可能性
证明适用于符合下列要求的单位方格矩阵:这种矩阵若按照棋盘那样涂色后,一种颜
色的方格要比另一种颜色的方格至少多一个.
在上述问题中,可以把院子看作缺少两个同色方格的一个6X7矩阵.显然,如果缺少
的两个方格同色,20个多米诺骨牌无法覆盖其余的40个方格.一个有趣的并与此有关
的问题是:如果缺少两个颜色不同的方格,20个多米诺骨牌是否能够覆盖住那缺格的
6X7矩阵?虽然奇偶校验没有证明其不可能性,但着并不意味着一定可以覆盖.通过擦
去一对异色的方格,可以生成所有可能的图形.但若逐一加以研究则不胜其烦,因为
各种可能的情况太多,以至于无法分析.对于所有的情况来说,是否有一种简单的可
能性证明?
有的,此证明既简单又巧妙,为拉尔夫.戈莫里妙手偶得之.他同样也是利用了奇偶
原理.假设此6X7矩阵有一条波及整个内部的闭合回路,宽度为一格.假设把闭合回路
上任何两个异色方格擦去,于是该闭合回路就一断为二,每一部分都是由格数成偶数
的异色方格组成.显然,这两部分的路总是能够用多米诺骨牌覆盖(把骨牌看作可以
停在弯曲车道上的篷车).你也许愿意尝试一下,把这个巧妙的证明应用于尺寸,形状
与此不同的矩阵,也可以考虑擦去不止两个方格的情况.
┌ ─ ─ ─ ─ ─ ┐
│ ┌ ─ ─ ─ ─ ┘
│ └ ─ ─ ─ ─ ┐
│ ┌ ─ ─ ─ ─ ┘
│ └ ─ ─ ─ ─ ┐
└ ─ ─ ─ ─ ─ ┘
铺砌理论作为组合几何中的一个范围广泛的领域,越来越受到人们的注目.要铺砌
的平面可以是任何形状----"有限的或无限的",瓷砖也可以形形色色,而且问题可能
会涉及不同形状的集合,而并非要求单一模式.不可能性证明还经常涉及以某种规定
的方式,用两种或两种以上的颜色为某一平面着色.
与多米诺骨牌相似的三维物体是砖块,其单位尺寸为1X2X4.用这种砖块"堆"成(空
间铺砌)一个4X4X4的箱体并不困难,但是用这种砖块可否堆成一个6X6X6的箱体?这
个问题完全可以应用布朗先生铺砌院子的问题的解法.设想把该立方体分成27个小
立方体,每个为2X2X2.把这些阶为2的立方体交替涂上黑白两种颜色,好似一个三维
的国际象棋棋盘.如果你把每种颜色的单位立方体的个数数一下,就会发现,一种颜
色的立方体比另一种颜色的多八个.
在那大立方体中,无论怎样放置砖块,不多不少总是恰恰"盖住"相同的数目的黑色
和白色的单位立方体,但一种颜色的单位立方体比另一种颜色的多八个,最初的26块
砖无论怎样放置,总会剩下同样颜色的八个单位立方体.因此无法安置第27块砖.如
果不厌其烦地探讨所有可能的堆砌方式,以求证明这一点,这样做显然极其费事.
堆砌理论仅是三维空间堆砌理论的一部分.关于空间堆砌问题,各种资料文献正日
趋增多.它们提出了大量悬而未决,引人入胜的问题,有许多问题的解法可应用于商
品的纸箱包装和堆仓等等.
奇偶性在粒子物理学方面也起着很重要的作用.1957年,两名中国血统的美国物理
学家(指杨振宁,李政道)因为他们在推翻著名的"宇称守恒定律"方面的贡献而获得
诺贝尔奖金.但由于这一题目专业性太强,故此不做详述.但可以举一个有趣的硬币
戏法的例子来说明奇偶性守恒的一种方式.
往桌子上抛一把硬币,数一下正面朝上的有多少,若是偶数,则称正面朝上的硬币
具有偶数性;若是奇数,则称其具有奇数性.现在把一对硬币翻身,再翻第二对,第三
对,任你翻转多少对.你将惊奇地发现,无论翻转多少对,正面朝上的硬币的奇偶性始
终不变.如果原来是奇数性,那么还是保持奇数性;如果原先是偶数性,则始终保持偶
数性.
利用这一点可以耍一个巧妙的魔术.你背过身去,请人随心所欲地把硬币一对一对
地翻转,再请他用手盖住其中任何一枚.然后,你回过身来,瞧一瞧硬币,即可正确地
说出他手掌下的硬币是正面朝上还是反面朝上.秘诀是开始时数一下正面朝上的硬
币有多少,记住是奇数还是偶数.由于一对一对地将硬币翻转并不会影响其原来的奇
偶性,所以你只要在最后再把正面朝上的硬币数一下,就可确定被盖住的那枚硬币是
正面朝上还是反面朝上了.
还有一个变相的问题:请他用手盖住两枚硬币,你再说出盖住的那一对硬币其朝上
一面是否相同.许多心算扑克牌花样的巧妙魔术都是利用奇偶校验来设计的.
------------------------------------------------------------------------
--------
9.多少只动物
这是久违的奎贝尔教授.奎贝尔教授:"我又为你们想出一个问题.在我饲养的动物
中,除了两只以外所有的动物都是狗,除了两只以外,所有的都是猫,除了两只以外所
有的都是鹦鹉,我总共养了多少只动物?你想出来了吗?
奎贝尔教授只养了三只动物:一只狗,一只猫和一只鹦鹉.除了两只以外所有的都
是狗,除了两只以外所有的都是猫,除了两只以外所有的都是鹦鹉.
如果你领悟到"所有"这个词可以指仅仅一只动物的话,头脑中就有了这个问题的
答案.最简单的情况--- 一只狗,一只猫,一只鹦鹉---既是其解.然而,把这个问题用
代数形式来表示也是一次很好的练习.
令x,y,z分别为狗,猫,鹦鹉的只数,n 为动物的总数,我们可以写出下列四个联立
方程:
n=x+2
n=y+2
n=z+2
n=x+y+z
解此联立方程有许多标准方法.显然,根据前三个方程式,可得出x=y=z.由于
3n=x+y+z+6减去第四个方程,得到 n=3,因此x+2=3,所以x=1.全部答案可由x值求得
.
由于动物只数通常是正整数(谁养的猫是用分数来表示只数的?),可以把奎贝尔教
授的动物问题看作所谓刁番图问题的一个平凡例子.这是一个其方程解必须是整数
的代数问题.一个刁番图方程有时无解,有时只有一个解,有时有不止一个或个数有
限的解,有时有无穷多个解.下面是一个难度稍大的刁番图问题,同样也与联立方程
和三种不同的动物有关.
一头母牛价格10元钱,一头猪价格3元钱,一头羊价格0.5元钱.一个农夫买了一百
头牲口,每种至少买了一头,总共花了100元钱,问每种牲口买了多少头?
令x为母牛的头数,y为猪的头数,z为羊的头数,可以写下如下两个方程式:
10x+3y+z/2=100
x+y+z=100
把第一个方程中的各项都乘以2消去分数,再与第二个方程相减以便消去z,这样得
到下列方程式:
19x+5y=100
x和y可能有那些整数值?一种解法是把系数最小的项放到方程的左边:
5y=100-19x,把两边都除以5得到:
y=(100-19x)/5
再把100和19x除以5,将余数(如果有的话)和除数5写成分数的形式,结果为:
y=20-3x-4x/5
显然,表达式4x/5必须是整数,亦即x必须是5的倍数.5的最小倍数既是其自身,由
此得出y的值为1,将x,y的值带入任何一个原方程,可得z等于94.如果x为任何比5更
大的5的倍数,则y变为负数.所以,此题仅有一个解:5头母牛,一头猪和94头羊.你只
要把这个问题中牲口的价钱改变一下,便可以学到许多初等刁番图分析的知识.例如
,设母牛价钱为4元钱,猪的价钱为2元钱,羊的价钱为三分之一元钱,一个农夫准备花
一百元钱买一百头牲口,并且每种牲口至少买一头,试问他每种牲口可以买多少头?
关于这一问题,恰好有三种解.但是如果母牛价钱为5元钱,猪的价钱为2元钱,羊0.5
元钱呢?那就无解.
刁番图分析是数论的一大分支,其实际应用范围极广.有一个著名的刁番图问题,
以费马最后定理而著称:设有方程xn+yn=zn,其中n是大于2的正整数,问此方程是否
有整数解(如果n=2,则称此为毕达格拉斯三元数组,具有自32+42=52起始的无穷多组
解)?这是一个最著名的数论问题,已经由英国数学家安德鲁.威尔斯解决,他用于解
决此问题的方法可以说是大大出乎人们的意料,他应用了一种叫做椭圆函数的理论
,实际上,他证明的并不是方程本身,而是在椭圆函数领域中另一个著名的猜想: 谷
山-志村猜想.由于椭圆函数的模形式与费马最后定理同构,所以,等于是从侧面攻破
了这个300多年的大难题.
------------------------------------------------------------------------
--------
10.药品混乱
一家药店收到运来的某种药品十瓶。每瓶装药丸1000粒。药剂师怀特先生刚把药
瓶送上架子，一封电报接踵而来。怀特先生把电报念给药店经理布莱克小姐听。
怀特先生：“特急！所有药瓶须检查后方能出售。由于失误，其中有一瓶药丸每
粒超重10毫克。请即退回分量有误的那瓶药。怀特先生很气恼。
怀特先生：“倒霉极了，我只好从每瓶中取出一粒来秤一下。真是胡闹。
怀特先生刚要动手，布莱克小姐拦住了他。布莱克小姐：“等一下，没必要秤十
次，只需秤一次就够了。这怎么可能呢？
布莱克小姐的妙主意是从第一瓶中取出1粒，从第二瓶中取出2粒，第三瓶中取出
3粒，以此类推，直至从第十瓶中取出10粒。把这55粒药丸放在秤上，记下总重量
。如果重5510毫克，也就是超过规格10毫克，她当即明白其中只有一粒是超重的，
并且是从第一瓶中取出的。
如果总重量超过规格20毫克，则其中有2粒超重，并且是从第二瓶中取出的，以
此类推进行判断。所以布莱克小姐只要秤一次，不是吗？
六个月后，药店又收到此种药品十瓶。一封加急电报又接踵而至，指出发生了一
个更糟糕的错误。
这一次，对超重药丸的瓶数无可奉告。怀特先生气恼极了。怀特先生：“布莱克
小姐，怎么办？我们上次的方法不中用了。布莱克小姐没有立即回答，她在思索这
个问题。
布莱克小姐：“不错。但如果把那个方法改变一下，我们仍然只需秤一次就能把
分量有误的药品识别出来。这回布莱克小姐又有什么好主意？
在第一个秤药丸问题中，我们知道只有一瓶药丸超重。从每瓶中取出不同数目的
药丸（最简单的方式就是采用计数序列），我们就可使一组数字和一组药瓶成为一
一对应的关系。
为了解决第二个问题，我们必须用一个数字序列把每瓶药单独标上某个数字，且
此序列中的每一个子集必须有一个单独的和。有没有这样的序列？有的，最简单的
就是下列二重序列：1，2，4，8，16，。。。这些数字是2的连续次幂，这一序列
为二进制记数法奠定了基础。
在这个问题中，解法是把药瓶排成一行，从第一瓶中取出1粒，从第二瓶中取出
2粒，从第三瓶中取出4粒，以此类推。取出的药丸放在秤上秤一下。假设总重量超
重270毫克，由于每粒分量有误的药丸超重10毫克，所以我们把270除以10，得到
27，即为超重药丸的粒数。把27化成二进制数：11011。在11011中自右至左，第一
，二，四，五位上的“1”表示其权值分别为1，2，8，16。因此分量有误的药瓶是
第一，二，四，五瓶。
在由2的幂组成的集合中，每个正整数是单一的不同组合中的元素之和。鉴于这
一事实，二进制记数法极为有用。在计算机科学和大量应用数学领域中，二进制记
数法是必不可少的。在趣味数学方面，同样也有难以计数的应用。
这里有一个简单的扑克魔术，可叫你的朋友莫名其妙。这个戏法也许看上去与药
瓶问题毫无关系，但他们的依据是相同的，都是二进制原理。
请别人把一副牌洗过，然后放进你的口袋，再请人说出一个1至15以内的数字。
然后你把手插进你的口袋里，一伸手就取出一组牌，其数值相加正好等于他所说的
数字。
此秘密简单的很。在耍魔术之前，预先取出A，2，4，8各一张放入口袋。这副牌
缺少区区四张，不大可能为人察觉。洗过的牌放入口袋后，暗中将其排置于原先已
经放在口袋中的四张牌的后面。请别人说出一个数字，你用心算将此数表示成2的
幂的和。如果是10，那你就应想到：8+2=10，随即伸手入袋，取出2和8的牌示众。
卜算卡片的依据也是二进制原理，准备六张卡片，分别记为A，B，C，D，E，F。
然后将一些数字填写在卡片上，确定每张卡片上的数字集合的规则是这样的：在一
个数的二进制表示中，若右起第一位是“1”，则此数字就在卡片A上。该卡片上的
数字集合自1起始，全部数字就是1至63范围内所有的奇数；卡片B则包括1至63范围
内的二进制记数法中右起第二位为“1”的全部数字；卡片C包括1至63范围内的二
进制记数法中右起第三位为“1”的全部数字；卡片D，E，F以此类推。注意：63这
个数字的二进制记数法是“111111”，每一位都是“1”，因此每张卡片上都有这
个数字。
这六张卡片可以用来确定1至63范围内的任意一个数字。请一位观众想好此范围
内的一个数字（例如某个人的年龄），然后请他把所有上面有此数字的卡片都交给
你。你随即说出他心中所想的那个数字。秘诀就是把每张卡片上2的幂的第一个数
字相加。例如，如果把卡片C和F交给你，你只要将上面第一个数字4和32相加，便
知道别人心中所想的数字是36。
有时，魔术师为了使得这个戏法显得更加玄妙，故意把每张卡片涂上各种不同的
颜色。他只需记住每种颜色所代表的2的幂。例如，红卡片代表1，橙卡片代表2，
黄卡片代表4，绿卡片代表8，兰卡片代表16，紫卡片代表32（可依据彩虹的诸色顺
序）于是，魔术师站在大房间的一头，请人想好一个数字，并且把上面有此数字的
卡片置于身旁，他即可根据那人身旁的卡片的颜色随口说出别人心中所想的数字。
------------------------------------------------------------------------
--------
11.巧断金链
一位来自阿肯色州的年轻太太格罗丽亚,正在加利福尼亚州旅行.她想在旅馆租用
一个房间,租期一周.办事员此时正心绪不佳.办事员:"房费每天20元,要付现钱.格
罗丽亚:"很抱歉,先生,我没带现钱.但是我有一根金链,共7节,每节都值20元以上.
办事员:"好吧,把金链给我." 格罗丽亚:"现在不能给你.我得请珠宝匠把金链割
断,每天给你一节,等到周末我有了现钱再把金链赎回.办事员终于同意了,但格罗丽
亚必须决定如何断开金链的方法.格罗丽亚:"我该三思而行,因为珠宝匠是按照他所
切割和以后重新连接的节数来索价的.格罗丽亚想了一下,悟到她不必把每一节都割
断,因为她可以把一段段金链换进换出,以这种方式来付房费.当她算出需要请珠宝
匠割断的节数时,她几乎不能自信.你想一想需要割开多少节?
只需要割开一节.这一节应是从一端数起的第三节.把金链断开成1节,2节,4节这
样三段后就能以换进换出的方式每天付给办事员一节作为房费.
啊哈!领悟到下列两点才能解题.第一,至少需要有1节,2节,4节这样三段(即其节
数成二重级数的一些段),这样才能以各种不同的组合方式组成1节,2节,3节,4节,5
节,6节和7节.我们在药品混乱问题中已经知道,这就是作为二进制记数法基础的幂
级数.
第二,只需要割开一节就可以把金链分成符合要求的三段.关于这个问题,若把金
链的长度增加,则可以想出一些新的问题.例如,假设格罗丽亚有一根63节的金链,她
想把金链割开,以上面那种方式来付63天的房费(价格不变).要达到此种目的只需要
割开三节.你想出来了吗?你能否根据金链的不同长度设计一个通用的解题程序,要
求分割开的节数为最少?
有一个有趣的变相问题:若所经手的 n 节首尾相连的闭合回路,例如说格罗丽亚
有一串金项链,由79节相连而成,若每天房费为一节,试问最少需要分割开几节才能
支付79天房费?
所有这些问题都跟二进制记数法有密切的关系.比如格罗丽亚的63节金项链如何
分割?只要将63化成二进制表示:等于"111111"即63=1+2+4+8+16+32只要将从第二节
开始的两节割开,再将从第八节开始的八节割下来,和从第32节开始的32节割下来即
可,这样就有了从1,2,3,4,5,6,直到63的所有节数.一般地,若有 n 节金链, n 是形
如 2k-1类型的数,将 n 化成二进制表示,再将所有"1"的位置所代表的2的幂的数相
间隔地割开即可达到目的.但是对于其他任意类型的数,却不能奏效,比如对于格罗
丽亚的79节金项链,79的二进制记数法表示为"1001111".即79=1+2+4+8+0+0+64,这
样从1到15都能表示,可是从16到63都没法表示,我把这个问题做到这里,也一时糊涂
起来,但这个问题毕竟不是很复杂,咱们也学一学闵科夫斯基在课堂上口出狂言要解
决四色问题的劲头,摸索着来解决一把.咱们可以这样:你不是要求节数最少吗?假设
n=a+b 其中 a 是已经找到的最大的那一节数,b 是比 n 小的已经解决了的金链问
题,由于 b 已经解决,因此 b 的拆分能够表示从1,2,3,...b-1,b 的所有金链节数
,而再大一些的数就不能够表示了,比如 b+1,所以必须要 a 参加进来,如果 n 是奇
数,可令 a=b+1,这样 n=2b+1,所以 b=(n-1)/2,a=(n+1)/2,这样就找到了最大的一
节的节数 a ,然后对 b=(n-1)/2继续应用如上的办法,即可解决问题.如果 n 是偶
数,可令 a=b ,这样虽然 a 本身不能表示出 b+1,但是可以从 b 的拆分中拿出一个
1来(这个1是必须存在的,因为要表示从1,2,3,...b-1,b的所有数)与 a 组成 a+1
也就是 b+1.所以 n=a+b=2a=2b,a=b=n/2.这样也找到了 n 为偶数时最大的一节金
链的节数.对于 b 继续如上的过程,就可以找到全部应该断开的金链节数,我算出了
从1到15的所有拆分如下:
1=1
2=1+1
3=1+2
4=1+1+2
5=1+1+3
6=1+2+3
7=1+2+4
8=1+1+2+4
9=1+1+2+5
10=1+1+3+5
11=1+1+3+6
12=1+2+3+6
13=1+2+3+7
14=1+2+4+7
15=1+2+4+8
对于上面的格罗丽亚太太的79节金项链,79+1=80,80/2=40,所以最大的一节就是
40节,79-40=39,39+1=40,40/2=20,所以第二大的一节就是20节,39-20=19,
19+1=20,20/2=10,第三大的一节是10节,19-10=9,9+1=10,10/2=5,又找到了一节是
5,9-5=4,4的表示法如上已经列出来了:4=1+1+2.最后得到79节的金项链的分割法:
1,1,2,5,10,20,40.过去我也碰到过一道类似的题,是23节金项链,也能够很容易地
解决:23+1=24,24/2=12;23-12=11,11=1+1+3+6;所以23的分割法为:1,1,3,6,12.显
然,对于2k-1类型的数,用这里的办法与用二进制记数法得出的结果是一致的.
从上面所列出的拆分法可以看出,如果 2k=<n<2k+1,那么 n 一定要用 k+1个数来
表示,即: n=a0+a1+a2+...+ak.
可以用数学归纳法很容易地证明这是正确的.那么还有没有比这更少的分割法呢?可
以证明没有了.从我们的分析方法中可以看出,这是一个构造性的推理过程,假如还
有比这更少的分割法,那么相当于在表达式 n=a0+a1+a2+...+ak.中进行了某些组合
,比如将a1+a2合并成新的a1,那么原来的有些组合就表示不出来了,例如a0+a2,就没
有办法组合了.当然,一个数的拆分不是唯一的,前面的23节金链还可以分成1,2,3,
6,11.你可以试试,这种分割法照样能满足要求.前面的分析中也可以把 (n-1)/2 留
下来作为最大的节数,但是这样分出来的节数就不一定都是最少的了,例如把15这样
分割,会得到:1,1,2,4,7.虽然能够满足付房费的要求,但是就不是最优解了.最后总
结一下,把前面的算法过程公式化可以得到:
k-1 r-1 k-1
n=(n+c0)/2+ ∑ {[n-∑cs2s+cr2r]/2r+1}+[n-∑cr2r]/2k
r=1 s=0 r=0
其中c0,c1,...ck-1等等是1或是0取决于每一步得出的数的奇偶性.其实最后一项
等于1,这样可以得出:
k-1
n-2k = ∑cr2r
r=0
a0=(n+c0)/2
i-1
ai=[n-∑cs2s+ci2i]/2i+1 1 (i=1,2,3,...k-1)
s=0
ak=1
当然,编成计算机程序还是用递归程序比较简单.这里列出这些公式是为了保留存
照.
------------------------------------------------------------------------
--------
12.巧分乳酪
乔记餐馆虽说吃食不算最好，但却以美味乳酪而远近闻名。块块乳酪状如圆盘，
绕有风趣。一刀下去，就把一块乳酪一切为二。连切两刀，不难将其分成四块，三
刀则切成六块。一天，女招待罗西请乔把乳酪切成八块。乔：“好，罗西。很简单
，我只要这样切四刀就成了。罗西把切好的乳酪往桌子上送时，忽然悟到乔只需要
切三刀便可以把乳酪分成八块。罗西想出了什么妙主意？
罗西豁然开朗，悟到圆柱形乳酪是一个立体图形，可以在中线处横截一刀将其一
切为二。如果允许移动切开的部分，那么连切三刀也行。可以把第一次切开的两块
迭放在一起，切第二刀成四块，再把四块跌放在一起，最后一刀切成八块。罗西的
解法是如此简单，几乎可以说是平凡的。然而它给人以明确的启示：对于有意义的
切分问题，可以用有限差分演算进行研究并用数学归纳法加以证明。有限差分演算
是发现数字序列普通项公式的有力工具。今天，数字序列日益引起人们的兴趣，因
为它具有极其广泛的实际应用范围，还因为计算机能够以极快的速度执行序列的运
算。
罗西第一次切乳酪的方法是在乳酪顶面的若干中线同时切数刀。乳酪具有如同薄
饼那样平坦的顶面。让我们来观察一下，根据在一张薄饼上切数刀的过程，能够生
成一些什么数字序列。假如沿着薄饼若干中线同时切数刀，显然，同时切 n 刀至
多可以切出2n块。
若在其边沿为一条简单闭合曲线的任意平面上同时切下 n 刀，这种方法所切成
的块数，是否最多也是 2n块呢？否。可以随意画出许多既非凸面，并且形状各异
的平面，即使一刀也可切成你所希望的块数。能否画出一种图形，仅切一刀便可以
切出任何有限数目的全等的块？若能办到，这种图形的周长应具有什么特性，才能
确保只需要一刀便可以切成全等的 n 块？若不同时进行切分，薄饼的切分将更为
有趣。你很快会发现：仅当 n〉=3 时，切 n 刀方可切成不止 2n 块。
这里，我们并不考虑所切成的块是否全等或面积相同。当 n=1，2，3，4。。。
时，可以切成的最多块数分别是2，4，7，11。这一大家所熟悉的序列是根据下列
公式求得的：
1+n（n+1）/2
其中，n 是所切的刀数。此序列的前10项（n 自0开始）是1，2，4，7，11，16
，22，29，37，46。。。
请注意，第一行差分是1，2，3，4，5，6，7，8，9。。。第二行差分是1，1，
1，1，1，1，1，1，1，。。。
这强烈地暗示着此序列的普通项是一个二次项。
为什么说“强烈暗示”呢？因为虽然可以用有限差分演算找到一个公式，但是并
不能保证该公式对于无限序列也成立。这一点尚需证明。在薄饼公式这一例子中，
不难通过数学归纳法做出一个简单的证明。
从这点出发，你可以发现大量的引人入胜的研究方向，其中有许多将导致非同寻
常的数字序列，公式以及数学归纳法证明。这里有一些问题可供你作为初步尝试。
采用下列各种方法，最多可以切成几块？
1。在马蹄形的薄饼上切 n 刀。
2。在球形或罗西所切的那种圆柱形乳酪上切 n 刀。
3。用切小圆甜饼的刀在薄饼上切 n 刀。
4。在状如烛环状（即中心有一个圆孔）的薄饼上切 n 刀。
5。在油炸圈（圆环）上切 n 刀。
关于以上这些问题，假设切分是同时进行的，若改成连切方式，并且允许重新安
排切开的部分，其答案如何变化？
------------------------------------------------------------------------
--------
13.隐蔽的尺寸
在城市广场的中央有一片很大的圆形憩息地。市议会拟在该地建造一个菱形浅
水池。多里斯。莱特市长看到这一计划，她找来了建筑师。莱特市长：“我喜欢呈
菱形的水池，用红瓷砖砌成，不知道这水池的每边有多长？”建筑师弗兰克。劳埃
德。朗被问住了。朗先生：“从A至B是5米，从B至C是4米。唔，应求出BD。也许我
需要应用毕达格拉斯定理。朗先生正疑惑不解，市长阁下忽然叫起来。莱特市长：
“啊哈！水池每边长为9米，这是毫无疑问的。”
朗先生：“我的天哪！怪不得你姓莱特（Wright）我姓朗（Wrong）呢。”有了
什么好主意使这个问题迎刃而解？
既是对角线又是半径
莱特夫人忽然悟到水池每边即为矩形的对角线。这个矩形的另一条对角线就是圆
形栖息地的半径。而矩形的两条对角线是相等的，所以水池每边边长就是圆半径的
长度。半径是5+4=9米，因此水池每边也是9米，无需应用毕达格拉斯定理。
你再找一种更简便的方法试试看，这样你就更能体会我们这种解法的优点。如果
你仅应用毕达格拉斯定理和相似三角形，其解法一定很冗长，繁琐。但你如果想到
下列平面几何定理：一个圆的两条内部相交的弦，一条弦的两部分之积等于另一根
弦两部分之积，那么就可以得出稍微简短的解法。根据这一定理，可以求得直角三
角形的高为 √56，在应用毕达格拉斯定理，算出直角三角形的斜边为9。
有一个与此密切相关的问题，那就是诗人亨利。朗非罗在其小说《卡瓦诺》中所
提出的有名的水仙花问题。当水仙花花茎垂直时，花朵伸出水面10厘米。如果把水
仙花拉向一边，使花茎保持直线，花朵沾水的位置离原来的位置是21厘米，问水深
多少厘米？
要解这个问题，可以先画一张草图，此图与水池问题的图相似。我们要确定的就
是x的长度。与水池问题一样，这个问题也不止一种解法。若你还记得两弦相交的
定理，解这个问题是轻而易举的。
还有一个有趣的游泳池难题，灵机一动则迎刃而解。一条海豚位于一个圆形水池
的西边A点，它笔直地游了12米，鼻子触到水边的B点，转过身后，又笔直地游了5
米，到达水池边上的C点，此位置正好与水池边上的A点遥遥相对，试问如果它直接
从A点游向C点，需要游多长距离？
啊哈！要解决这个问题只需知道下列定理：半圆上的圆周角是直角，所以三角形
ABC是直角三角形。已知两直角边长分别为12米和5米，所以斜边为13米。上述问题
都给我们以启示：在许多情况下，如果思路正确，几何问题的求解会变得极其容易
。而要做到这一点，这取决于你是否想到了欧几里德几何的某个基本定理。
--
※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.13.5]
[回到开始]
[上一篇][下一篇]
荔园在线首页 友情链接：深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店