棋盘上的数学

书书书 !图书在版编目!!"#"数据 !棋盘上的数学!单墫著!"上海#华东师范大学出版社$"#$# !%单墫老师教你学数学& !%&’()*+ * ,-$* +#., ) !!!"棋’!#!"单’!$!"代数课 高中 教学参考资 料!%!"/-0.!-"0 !中国版本图书馆1%2数据核字%"#$#&第$*##$#号 单墫老师教你学数学 棋盘上的数学 著!!者!单!墫 策划组稿!倪!明!孔令志 审读编辑!孔令志 装帧!卢晓红 出版发行!华东师范大学出版社 社!!址!上海市中山北路!""!号!邮编#$$$"# 网!!址!%%%&’()*+,’--&(./&() 电!!话!$#0 "$1#0"""!行政传真$#0 "#23#0$2 客服电话!$#0 "#1"22!3!门市!邮购" 电话$#0 "#1"4113 地!!址!上海市中山北路!""!号华东师范大学校内先锋路口 网!!店!566+#$$’()*+&67.87.&(./$ 印 刷 者!南通印刷总厂有限公司 开!!本!14$90#:$!!#开 印!!张!!&2 字!!数!31千字 版!!次!#$00年!月第一版 印!!次!#$00年!月第一次 书!!号!;<=>431 3 2"03 1$:2 4$?%:3$! 定!!价!0$&$$元 出 版 人!朱杰人 %如发现本版图书有印订质量问$请寄回本社客服中心调换或电话!"# $"%$&&’(联系& $!!!! 总!序 科学昌明!既需要科学家筚路蓝缕"披荆斩棘!也需要普及 工作者耕耘播种"热心培育! 普及工作很重要!如果将科学研究比作金字塔的塔尖!那么 普及工作就是金字塔的底!底宽!塔才高! 科学研究不容易!从事研究!需要才能"努力与机遇!能够从 事研究的人不多!好像阳春白雪!曲高和寡!他们的成果需要普 及工作者通俗化"趣味化!才能广为人知!才能使更多的人关心" 了解"理解!才能引起公众的兴趣!吸引更多的新人一同参加研 究!345678大定理就是一个典型的例子!虽然只有 9:;4<一个 人给出了证明!看懂证明的不过十几个人或几十个人!但对大定 理感兴趣的人成千上万!他们都是普及读物的读者! 普及工作使千万人受益!我就是其中之一! 在学生时代!我读过不少数学普及读物!如刘薰宇的#数学 园地$!孙泽瀛的#数学方法趣引$!许莼舫的#几何定理和证题$! 17<4=的#近世几何学初编$!日本数学家林鹤一的#初等几何作 图不能问题$"上野清的#大代数$!前苏联数学家写的数学 丛书#摆线$"#双曲线函数$等!以及稍后中国数学家华罗庚等写 的数学丛书#从杨辉三角谈起$等!还在#科学画报$上看到谈祥 柏先生写的妙趣横生的文章#奇妙的联系$等!这些数学读物不 仅使我学到许多数学知识"方法和思想!眼界大开!而且使我对 数学产生了浓厚的兴趣!甚至立志要当一名数学家! 但当数学家的梦想却难以实现!因为那时政治运动频仍!读 书!被认为%走白专道路&!会横遭批判!史无前例的文化大革命 %!!!! 更是书与读书人的一场浩劫! %四人帮&倒台后!我才有幸到中国科学技术大学作研究生! 在$)+0年成为首批$+名国产博士之一!但这一年我已年届不 惑!从事数学研究的黄金时期业已过去!我觉得与其花费时间凑 一些垃圾!不如做普及工作对社会更有贡献! 对普及工作!我有浓厚的兴趣!也有一定的基础’ $!由于做过一些研究工作!能够了解较新的材料!能够较 为准确地把握数学及有关史料! "!由于当过多年教师!文字也还通顺!能够注意趣味性与 深入浅出! $)**年恢复高考后!一度出现读书的热潮!这时常庚哲先 生带头写了#抽屉原则及其他$!受到普遍的好评!稍后!上海教 育出版社的王文才"赵斌两位编辑邀我写稿!我就写了#几何不 等式$"#趣味的图论问题$!在$)+#年出版!以后又陆陆续续写 了#覆盖$"#组合数学中的问题和方法$"#趣味数论$"#棋盘上的 数学$"#解析几何中的技巧$"#算两次$"#集合及其子集$"#组合 几何$"#对应$"#国际数学竞赛解题方法$(与葛军合作)"#不定 方程$(与余红兵合作)"#巧解应用题$"#因式分解$"#平面几何 中的小花$"#数学竞赛史话$"#解题思路训练$"#十个有趣的问 题$"#概率与期望$"#数学趣题巧解$"#快乐的数学$"#数列 与数学归纳法$"#解题研究$"#数学竞赛教程$等等! 由于文革后!大家渴望读书!而此前的书大多毁于%文革&劫 火!因此新出的书颇受欢迎!其中也包括了我写的小册子! 冯克勤先生说’%不要小看了这些小册子!它们将数学的美 带给大众!&(冯克勤#评审意见$) 杨世明"杨学枝先生说’%直到$)+#年!大家才盼来单墫的 #几何不等式$一书**不仅普及了基础知识"基本思想方法!而 &!!!! 且激发了研究兴趣!今天初等不等式研究中的许多骨干!都曾从 该书获益!单墫的#几何不等式$一书!无疑是这一阶段的标志性 的著作!&(杨世明!杨学枝#初等不等式在中国$!载#中学数学研 究$"##*年第$期)! 还有一些数学教师见到我客气地说’%我们都是读您的书长 大的!& 这些评论当然是过奖的溢美之词!但也说明普及工作是一 件有意义的"值得去做的事情! 近年来!急功近利的风气在学校蔓延!要根治这种歪风!还 得提倡读书!要使广大青少年%热爱知识!渴求学问&(卡耐基#林 肯传$!人民文学出版社!"##,版第$-页)! 首先!得多出一些好书!供大家阅读! 读书是天下第一件好事!读好书是人生第一件乐事!好读 书!读好书!进步就迅速!有些学生学数学!只做题!从不看书!这 种做法是难以进步的! 感谢华东师范大学出版社出版我的科普著作集!这*种小 册子修订后!重新出版!希望能有较多的读者!特别是青少年读 者!希望它们能给爱好数学的朋友们带来乐趣! $!!!! 前!言 下棋!是一种很好的活动!它与数学有类似之处!都需要思 考"推理和判断!都有利于发展人的思维能力!所以孔老夫子认 为!%饱食终日!无所用心&!不如去下棋! 棋盘本身还可以提供许许多多的数学问题!这些问题不但 饶有趣味!而且蕴含着深刻的数学理论背景!这或许是大部分奕 棋爱好者所始料未及的吧+ 这本小册子!就是向你介绍这些问题!希望能引起你的 兴趣! 作者 $!!!! 目!录 总序 !0 前言 !0 0! !棋盘 !0 #! !覆盖 !1 !! !马 !04 :! !走遍棋盘 !!# 2! !皇后 !:$ "! !皇帝"车"象 !20 3! !博奕 !"0 1! !棋盘上的问题 !34 附录!二进制简介 !41 书书书 !!!!! ! 棋!盘 象棋!围棋和国际象棋的棋盘都是长方形"由一些横线与纵 线组成! 图!!!是象棋的棋盘"它由!"条横线与#条纵线组成"棋 子放在横线与纵线的交叉点上! 图!!! 图!!$是围棋的棋盘"它由!#条横线和!#条纵线组成"棋 子也是放在横线与纵线的交叉点上! "!!!! 图!!$ !!我们还可以考虑更一般的#广义棋盘$"它由" 条横线与# 条纵线组成! 坐标平面上的直线$ %&%& %""’!"’$"&’与直线 ( %)%) %""’!"’$"&’构成一个#无限棋盘$!棋子放在 横线与纵线的交点%)"&’上"这样的点称为整点%因为横坐标) 与纵坐标&都是整数’"也称为格点! 图!!%是国际象棋的棋盘"它由#条横线与#条纵线组成" 纵线之间的距离与横线之间的距离都是相等的"因此截得&* &%’(%个’相等的正方形的小方格!这种棋盘称为&*&的棋 盘!类似地"如果每行有" 个小方格"每列有#个小方格"这种 棋盘称为" *#的%广义’棋盘或" *#的矩形! 国际象棋的棋子是放在方格中的"这与中国象棋!围棋 不同! #!!!! 图!!% 但这种不同只是表面上的!如果在国际象棋盘上"取每个小 方格的中心"将这些中心%’(个’用横线与纵线连结起来"而将 原来的横线!纵线擦去"就得到一个由&条横线与&条纵线组成 的新棋盘"棋子恰好放在新棋盘的横线与纵线的交叉点上! 这样得到的新棋盘称为原棋盘的对偶图或对偶棋盘%图!!(’! 图!!( $!!!! 关于棋盘"流传着一个脍炙人口的古老故事"故事的大意是 这样( 一位印度皇帝学会了国际象棋"从中得到了很多乐趣!皇帝 一高兴"决定给国际象棋发明者以重赏! 于是国际象棋发明者被召进宫! #我要给你奖赏"$皇帝说(#你提出要求吧"我将满足你的愿望!$ #陛下"请赏给我一棋盘麦子吧!$发明者指着棋盘说(#请在 棋盘的第一个方格赏我!粒麦子"第二个方格赏我$粒麦子"第 三个方格赏(粒"第四格赏&粒"第五格赏!’粒&&$ #我懂了"$皇帝打断他的话"#你是要在棋盘上的’(个格子上 都得到麦子"每一个格子上得到两倍于前面一格的麦粒!可是"你不 认为这点要求太微不足道吗! 你应该知道我的财富有多么巨大"$ #是的"我只需要棋盘上的这些麦粒!$发明者笑了笑! #好吧"我一定满足你的要求"下午就让你如数领取!$ 可是"发明者并没有按时领到这笔奖赏!原因是皇帝和他的 财政大臣紧张地算了一下午"还没有算出这#一棋盘$的麦粒数! 其实"这个问题很简单!国际象棋盘上有’(个小方格%见图 !)%’"发明者所要的麦粒数是 + %!,$,$$,$%,& ,$’%! 假设皇帝多赏!粒麦子给发明者"即 +,!%!,!,$,$$,$%,& ,$’%" 将上式右边前两项相加(!,!%$"再加第三项($,$%$$"逐 步加下去"即$$,$$ %$)$$ %$%"$%,$% %$)$% %$("&" 直至最后"得到 +,!%$’%,$’% %$’(" %!!!! 将皇帝#多赏$的!粒拿回去"即发明者所要的麦粒数是 + %$’(-!%!&"((’"*((""*%"*"#"++!"’!+! 这个数后来被称为#国际象棋数$"它是个惊人的大数!有人计算 过(如果造一个粮仓来放这些麦子"粮仓高(公尺"宽!"公尺" 那么粮仓的长度就等于地球到太阳的距离的两倍" 由此看来"皇帝所应允的给国际象棋发明者的奖赏"是世界 上最高的#发明奖$"但也是永远无法兑现的发明奖" 如果皇帝 稍微懂一点数学的话"就不会留下这个千古笑柄" 在这本小册子里"我们将要向读者介绍棋盘中所蕴藏着的 许许多多有趣的问题"以及解决这些问题所用到的一些重要的 数学方法与技巧!下面的三则问题都是涉及棋盘的"虽然问题都 不难"但是"如不会用一点数学"即使是棋界大师对它们也可能 是束手无策哩" 问题!是一个著名问题"曾被用作中国科技大学少年班的 招生试题! 问题 "! ####################! %剪残了的棋盘’剪去国际象棋棋盘的左上角与右下角的两 个小方格%图!!+%!’’!能否用%!个$*!的矩形%图!!+%$’’将 这个剪残了的棋盘盖住! 中国象棋盘上也有许多有趣的问题! 问题 "! ####################" 在图!!’中"甲方一只小卒已经过了河"它可以向前移动一 步"即走到.*也可以横移一步"即走到/!要使这个小卒沿最短 的路线走到对方帅的位置%假定在前进的路上不受任何阻碍’" 问(有多少种不同的走法! &!!!! 图!!+ 图!!’ ’!!!! !!问题 "! ##################### 无论是中国象棋还是国际象棋"马的走法都是一直一斜"所 以棋谚曰#马走日字象%相’飞田$!从图!!*中的/ 点出发"一 只马能否既不重复也不遗漏地跳遍半个棋盘%即棋盘上的每一 点都跳到并且只跳到一次’! 从哪些点出发"可以实现这样的 要求! 图!!* 上述问题将在本书的相关节中一一给予解决!问题$即是 第八节的问题!"问题!和%分别在第二!三节中!建议读者对 上面的问题先考虑一下%我们相信读者在阅读本书时"随身带着 笔和纸的’! (!!!! ! " 覆!盖 首先讨论上节末的问题!%剪残了的棋盘’! 例 "! #####################! 图$!!中的棋盘能否用%!个$*!的矩形恰好覆盖! 图$!! 并非所有问题的答案都必须是肯定的!这个问题的答案就 是不能 !! ! 为了证明这一点"我们将棋盘的方格涂上白色或黑色"使得 每两个相邻的方格%即有公共边的两个方格’颜色不同!通常的 国际象棋棋盘上正是这样涂色"我们称之为#自然涂色$! )!!!! 如果%!个$*!的矩形恰好覆盖这剪残了的棋盘"由于每 个$*!的矩形盖住!个白格与!个黑格"所以棋盘中白格与黑 格的个数应当相等"都是%!个! 但图$!!中的棋盘却有%"个白格"%$个黑格"所以%!个 $*!的矩形不能覆盖这个棋盘! 从这个简单的问题"可以看出涂色这一方法的作用! 同样的道理可以证明从&*&的国际象棋盘上剪去两个同 色的方格"剩下的棋盘一定不能用%!个$*!的矩形覆盖! 如果剪去一个黑格一个白格呢! 例 "! #####################" 在&*&的国际象棋盘上剪去一个黑格与一个白格后"能否 用%!个$*!的矩形将它覆盖! 图$!$ 答案是肯定的"一定能用%!个$*!的矩形将这棋盘覆 盖!事实上"如图$!$"用一些粗线将棋盘隔成宽为!的长条路 线!从任一个方格出发"沿着这条路线前进"可以不重复也不 !*!!! 遗漏地走遍棋盘并回到出发点!现在从剪去的方格/ 出发"沿 这条路线"每经过两个方格就放上一个$*!的矩形!由于剪 去的两个方格/!. 异色"所以/!. 之间%沿着这条路线’有 偶数个方格"恰好能放整数个$*!的矩形!然后继续沿着这 条路线从. 走到/"每经过两个方格放上一个$*!的矩形! 这样就可以用%!个$*!的矩形覆盖整个棋盘%/!. 两方格 已被剪去’! 例 "! ###################### 用!+个,字形及!个田字形%图$!%’"能否覆盖&*&的 棋盘! 图$!% 答案是不能!为了证明这点"我们利用棋盘的自然涂色! 如果!+个,字形与!个田字形能够覆盖这个棋盘"那么 每个,字形覆盖奇数个%!个或%个’白格"从而!+个,字形覆 盖奇数个白格%因为!+个奇数的和是奇数’!!个田字形覆盖$ 个白格!因而"!+个,字形与!个田字形所覆盖的白格数必定 是奇数! 但棋盘中"白格的个数为偶数%%$个’"因此!+个,字形与 !个田字形不能覆盖整个棋盘! 在这个问题中"涂色与奇偶性都发挥了作用! 下面是更巧妙的覆盖问题! !!!!! !!例 "! #####################$ 如图$!("&*&的国际象棋盘剪去左上角的一个方格后" 能否用$!个%*!的矩形覆盖! 剪去哪一个方格才能用$!个 %*!的矩形覆盖! 图$!( 剪去左上角的方格后"棋盘不能用$!个%*!的矩形覆盖! 为了证明这一点"我们将棋盘涂上%种颜色%这一次"采用 自然涂色不能奏效’"涂法如图$!+"其中数字!!$!%分别表示 第一!二!三种颜色! 如果能用$!个%*!的矩形将剪去左上角的棋盘覆盖"那 么每个%*!的矩形盖住第一!二!三种颜色的方格各!个"从而 $!个%*!的矩形盖住第一!二!三种颜色的方格各$!个!然而 棋盘%剪去左上角后’却有第一种颜色的方格$"个"第二种颜色 的方格$$个"第三种颜色的方格$!个!因此"剪去左上角的棋 盘无法用$!个%*!的矩形覆盖! 由此可见"如果剪去一个方格后"棋盘能用$!个%*!的 !"!!! 图$!+ 矩形覆盖"那么剪去的方格一定是图$!+中涂第二种颜色的 方格! 但是"剪去图$!+中涂第二种颜色的一个方格后"仍然不能 保证一定能用$!个%*!的矩形覆盖!比如说"剪去图$!+中第 一行第二个方格后不能用$!个%*!的矩形覆盖!这是由于棋 盘的对称性"剪去这个方格与剪去第一行第七个%涂第一种颜色 的’方格%或剪去第八行第二个涂第三种颜色的方格’"所剩下的 棋盘完全相同! 于是"只有剪去第三行第三个!第三行第六个!第六行第三 个!第六行第六个"这(个方格中的某一个"剩下的棋盘才有可 能用$!个%*!的矩形覆盖! 不难验证这时确实能够覆盖!图$!’表明了剪去第三行第 六个方格后"用$!个%*!的矩形是能够覆盖棋盘的! 于是"当且仅当剪去的!个方格是上述(个方格之一时"棋 盘能用$!个%*!的矩形覆盖! !#!!! 图$!’ 例(彻底解决了!我们从这个%及上面的’问题看到"对于这 类问题"如果答案是不可能的"往往需要机敏的%采用涂色或奇 偶性’反证*如果答案是可能的"通常采用构造法"如例(的 方法! 例 "! #####################% 证明(用!个田字形和!+个(*!的矩形不能覆盖&*&的 棋盘! 这一次"我们按照下面的方式将棋盘涂上黑!白两种颜色! 显然田字形盖住奇数个%!个或%个’白格"而每个(*! 的矩形盖住偶数个白格!然而图$!*中"白格的总数是偶数 %%$个’!这就导致了矛盾!具体的证明细节请读者自己予以 补充! 涂色%也就是分类’是一种常用的方法!但究竟如何涂色"应 根据具体问题具体分析!数学与下棋类似"需要灵活运用各种方 法"#最忌执一$! !$!!! 图$!* !!例 "! #####################& 证明("*#的棋盘能用若干个&*!的矩形恰好覆盖的充 分必要条件是"!#中至少有一个被&整除! 充分性是显然的!因为在&0"%我们用&0"表示&整除"’时" 每一列可以用" & 个&*!的矩形恰好覆盖!&0#的情况与此类似! 现在假定棋盘被若干个&*!的矩形恰好覆盖"要证明"! #中至少有一个被&整除"我们采用反证法证明!如果&$""&$ #%我们用&$"表示&不整除"’"那么由普通的带余除法"可设 " %"!&,1""%1%&" # %#!&,2""%2%&" 其中%不完全’商"!!#!及余数1!2都是自然数"并且不妨设 1&2! 现在将棋盘涂上!"$"&"&这几种颜色%图$!&’!为方便 起见"约定3%3%!"$"&"&’与3,&表示同一种颜色! !%!!! 书书书 图 ! "# !&!!! !!由于每个&*!的矩形恰好盖住颜色为!"$"&"&的方格 各!个"所以棋盘中&种颜色的方格数彼此相等%恰好等于&* !的矩形的个数’! 但另一方面"除去右下角的那个2*1的矩形"其余的"!* #!个&*&的矩形!"!个&*2的矩形!#!个1*&的矩形中" &种颜色的方格都是相等的"在右下角的那个2*1的矩形中"颜 色为!的方格少于2个%不是每一列都有颜色为!的方格"实际 上第二列就没有’!颜色为2的方格恰有2个!因此"在整个"*# 的棋盘中"&种颜色的方格数并不全相等"这就与假设相矛盾" 从而证得&0" 或&0#至少有一个成立! 例!至例’都是讨论有没有某种所说的覆盖存在"这类 问题可以称之为#存在性问题$!如果有某种覆盖存在"那么 还可以进一步探讨有多少种不同的覆盖"这类问题称为#数 量问题$! 例 "! #####################’ 用#个$*!的矩形%这种矩形我们以后称它为骨牌或多米 诺’覆盖$*#的棋盘"有多少种不同的盖法! 设有4# 种不同的盖法!如果#%!"显然只有!种盖法"即 4! %!!当# %$时"有$种盖法%图$!#’"即4$ %$! 图$!# 对于# ’$"我们注意到全体覆盖可以分成两类!第一类是 在最右边竖放!张骨牌*第二类是在最右边横放$张骨牌%图 $!!"’! !’!!! 图$!!" 每个第一类覆盖"实际上是用#-!张骨牌来覆盖$*%#-!’ 的棋盘!所以"第一类覆盖有4#-!种! 每个第二类覆盖"实际上是用#-$张骨牌来覆盖$*%#-$’ 的棋盘!所以"第二类覆盖有4#-$种! 于是"我们得到 4# %4#-!,4#-$! %$!!’ 由4! %!"4$ %$及递推关系%$!!’可逐步推出 4% %4!,4$ %%" 4( %4$,4% %+" 4+ %4%,4( %&" && 从而得到一串数 !"$"%"+"&"!%"$!"%("++"&#"& %$!$’ 这串数通常称为斐波那契%-./01233."!!*++!$+""意大利数学 !(!!! 家’数! 从递推关系式%$!!’及#初始条件$4! %!"4$ %$可以导 出第#个斐波那契数 4# % ! 槡+ 槡+,!% ’$ #,! - !-槡+% ’$ #,, -! ! !)!!! ! # 马 在中国象棋中"马的走法是一直一斜"俗称#马走日字象 %相’飞田$"即从!*$的矩形的一个顶点跳到相对的那个顶点! 马这样走是有道理的"它从棋盘上任一点出发"可以跳到任 何一个指定的点!这个事实"每个下过象棋的读者都是熟悉的! 如果马的#步伐$大一些"改为!*%"即从!*%的矩形的一 个顶点跳到相对的顶点"那么这种马称为!*%的马!它能不能 从棋盘上任一点出发"跳到任何一个指定的点呢! 例 "! #####################! !*%的马不能从棋盘上任一点出发"跳到任何一个指定 的点! 为了证明这个事实"我们将棋盘的左下方的点/ 作为原 点"建立起直角坐标%图%!!’! 如果!*%的马能从整点%(!"$!’一步走到整点%($"$$’" 那么(!与($的差是!或%"$!与$$的差是%或!"即(!与($ 的奇偶性不同"$!与$$的奇偶性也不同!从而(!,$!与($, $$的奇偶性相同!于是在马前进的过程中"走过的整点%("$’ 的坐标和(4$"奇偶性保持不变!从原点/%"""’出发只能走 到坐标和为偶数的点"不能走到%无论走多少步’坐标和为奇数 的点"例如%!""’! yu.qi 文本框 看完整版请登录新华e店 www.xhestore.com