广东广播电视台 现代教育频道>>图文新闻>>现代教育快讯
2014高考热门专业：理工类热门专业有哪些？发布时间： 点击:3370　下面对二十个理工类专业做了详细介绍和就业前景已经开设院校推荐。　　1.数学与应用数学　　专业介绍：本专业特点是理工结合，培养具有宽厚的数学基础，熟练的计算机应用和开发技能，较强的外语能力，并掌握一定的应用科学知识，能运用数学的理论和方法解决实际问题的高级科技人才。　　就业去向：毕业生适合到科研、工程、经济、金融、管理等部门和高等院校从事教学、计算机应用、科学计算、软件设计、信息管理、经济动态分析和预测等多方面的研究和管理工作。　　推荐院校：北京大学、南开大学、天津大学、天津理工大学、复旦大学、四川大学、中国科学技术大学武汉大学(招生办)。　　2.信息与计算科学　　专业介绍：本专业培养能在科技、教育和经济部门从事研究、教学、应用软件开发和管理工作等方面的高级专门人才。　　就业去向：主要到科技、教育和经济部门从事研究、教学和应用开发及管理工作。　　推荐院校：北京大学、清华大学(招生办)、浙江大学、南开大学、南京大学(招生办)、吉林大学、西安大学、天津理工大学。　　3.应用物理学　　专业介绍：本专业培养具有坚实的数理基础，熟悉物理学基本理论和发展趋势，熟悉计算机语言，掌握实验物理基本技能和数据处理的方法，获得技术开发以及工程技术方面的基本训练，具有良好的科学素养和创新意识。　　就业去向：毕业生能在应用物理、电子信息技术、材料科学与工程、计算机技术等相关科学领域从事应用研究、技术开发以及教学和管理工作。　　推荐院校：北京大学、清华大学、南京大学、浙江大学、南开大学、天津大学、中国科学技术大学、武汉大学。　　4.应用化学　　专业介绍：本专业以高分子材料、精细化工和计算机在化学化工中的应用技术为专业方向，培养具有可从事相关领域的科学研究，工业开发和管理知识的高级专门人才。　　就业去向：主要到科研机构、高等学校及企事业单位等从事科学研究、教学及管理。　　5.环境科学　　专业介绍：本专业培养能在科研机构、高等院校、行政部门和企事业等单位从事科研、教学、规划与管理、环境评价和环境监测等工作的高级专业人才。　　就业去向：主要到科研机构、高等学校、企业事业单位及行政部门等从事科研、教学、环境保护和环境管理等工作。　　6.环境工程专业　　专业介绍：本专业培养具备城市和城镇水、气、声、固体废物等污染防治和给排水工程，水污染控制规划和水资源保护等方面知识的环境工程学科高级工程技术人才。　　就业去向：主要至政府部门、规划部门、经济管理部门、环保部门、设计单位、工矿企业、科研单位、学校等从事规划、设计、施工、管理、教育和研究开发方面的工作。　　推荐院校：华中科技大学、南开大学、天津大学、天津理工大学　　7.计算机科学与技术　　专业介绍：培养能在科研部门、教育单位、企业、事业、技术和行政管理部门等单位从事计算机教学、科学研究和应用的计算机科学与技术学科的高级专门科学技术人才。　　就业去向：计算机科学与技术类专业的毕业生适合到各系统或行业的相关部门从事软件开发、经营和维护，也可从事教学、科研和技术工作。　　推荐院校：北京大学、北京理工大学、吉林大学、南京大学、南开大学、天津大学、天津理工大学　　8.生物工程(生物科学)　　专业介绍：本专业培养能在生物技术与工程领域从事设计、生产、管理和新技术研究、新产品开发的工程技术人才。　　就业去向：生物科学类专业的毕业生可在教学、科研部门，也可在农、林、渔、牧、副、医、药以及有关的企业与事业单位从事教学、科学研究或其他与生物学有关的技术工作。　　推荐院校：北京大学、华东理工大学、南开大学、天津大学、天津理工大学　　9.生物技术　　专业介绍：本专业能适应生物技术及相关领域的理论及应用性研究，具有创新能力和实践能力的高级专门技术人才。　　就业去向：主要到科研机构或高等学校从事科学研究或教学工作或在工业、医药、食品、农、林、牧、渔、环保、园林等行业的企业、事业和行政管理部门从事与生物技术有关的应用研究、技术开发、生产管理和行政管理等工作。　　推荐院校：南京大学、中国农业大学(招生办)、四川大学、天津大学、华东理工大学　　10.通信工程　　专业介绍：本专业培养掌握光波、无线、多媒体通讯技术、通讯系统和通讯网等方面知识，能在通信领域从事研究、设计、制造、运营及从事通讯技术开发与应用、管理与决策的高级工程技术人才。　　就业去向：适合邮电部所属各邮电管理局及公司从事科研、技术开发、经营及管理工作，也可到军队、铁路、电力等部门从事相应的工作。　　推荐院校：北京邮电大学、天津大学、天津理工大学、华中科技大学、西安电子科技大学(招生办)　　11.机械工程及自动化专业　　专业介绍：本专业培养能在工业生产第一线从事机械工程及自动化领域的设计制造、科技开发、应用研究、运行管理和市场营销等方面工作的宽口径、通识型高级工程技术人才。　　就业前景：可在机械、电子、冶金、石油化工、航空航天、兵工等领域的企事业单位从事生产技术、研究开发、工程建设、行政管理及教育工作等。机械工程及其自动化专业是集机械、电子、信息技术为一体的综合性专业，知识结构先进，适应面宽广，发展潜力大，是一个发展迅速、需求巨大的热门专业。　　推荐院校：西安大学、浙江大学、天津理工大学、天津工业大学　　12.过程装备与控制工程　　专业介绍：本专业培养具备化学工程、机械工程、控制工程和管理工程等方面知识的高级专门人才，以适应现代化工业发展的需要。　　就业前景：主要到化工、石油、能源、轻工、环保、医药、食品、机械及劳动安全等部门从事工程设计、技术开发、生产技术、经营管理以及工程科学研究等方面的工作。本专业毕业生就业几率高，且多能与专业对口。　　13.热能与动力工程　　专业介绍：本专业培养能够从事制冷、空气调节、供热等能源工程的高级工程技术和管理人才。专业内容包括汽车发动机、涡轮机械、锅炉与换热设备、制冷与空调、新能源开发与利用。　　就业前景：在国民经济和部门，从事动力机械(如热力发动机、流体机械、水力机械)的动力工程(如水电动力工程、制冷及低温工程、空调工程)的设计、制造、运行、管理、实验研究和安装、开发、营销等工作。该专业属能源动力类，是国家重点发展领域之一，发展前景广阔。　　推荐院校：北京航空航天大学、天津大学、天津理工大学　　14.电气工程及其自动化　　专业介绍：本专业培养能够从事与电气工程有关的系统运行、自动控制、电力电子技术、信息处理、试验分析、研制开发、经济管理以及计算机应用等领域工作的宽口径“复合型”高级工程技术人才。　　就业前景：毕业后可在电力科研院所、电力规划设计院、自动化高新技术公司、各地电力公司、各发电厂及非电力企业动力部门工作。可在电力系统自动化、计算机应用技术、农业电气化与自动化等主要专业方向深造。　　推荐院校：浙江大学、北京航空航天大学、天津大学、西安交通大学、天津理工大学、天津科技大学　　15.电子信息工程　　专业介绍：本专业培养能够在电子工程领域、信息工程领域、计算机技术与应用领域等从事研究、设计开发、制造、应用和管理与决策的高级工程技术人才。　　就业去向：电子信息工程类专业毕业生适合到电子行业、广播电视等部门从事电子设备制造、电子元件和器件及原材料的开发研制、生产管理等工作，也可到其他部门的相关单位工作。　　推荐院校：北京邮电大学、电子科技大学(招生办)、北京科技大学、浙江大学、天津大学、天津理工大学、天津科技大学　　16.光电子技术科学专业　　专业介绍：培养高级光电子技术科学人才。　　就业前景：到信息产业部门、电信部门、高等院校、企事业单位及有关公司，主要从事光电子技术科学，光电信息工程与技术、光通信工程与技术、光电信号检测处理与控制技术等领域的研究、设计、开发、应用和管理等工作。　　推荐院校：南开大学、天津大学　　17.飞行器设计与工程　　专业介绍：该专业主要培养从事空间飞行器(包括卫星、载人飞船、空间站等)、运载火箭及导弹总体设计和结构设计、飞行动力学与控制系统设计及其他民用产品机电一体化与控制设备的设计、开发与研究等工作的高级专业技术人才。　　就业前景：毕业生基本进入科研设计单位和国有企业、部队以及高等学校　　推荐院校：北京航空航天大学、西北工业大学(招生办)、南京航空航天大学　　18.飞行器动力工程　　专业介绍：本专业培养适应民航现代化与国际化需要的，既具备较扎实的理论基础、较宽的知识面，又具备工程师基本技能训练，有较强动手能力和适应能力的民航机务高级技术人才。　　就业前景：主要从事飞行器(包括航天器与运载器)总体设计、结构设计与研究、结构强度分析与试验，并从事通用机械设计及制造的工作。由于我国航空航天领域近年来的飞速发展，开发发动机的飞行器动力工程专业的毕业生每年都供不应求。飞行器动力工程专业大部分学生都在航空、航天、民航等领域对口从事研究工作。但是还有很多学生去了能源、、管道输送等部门施展才华。而这些国家重点项目和重大工程都依赖航空航天发动机改装成的核心部件。　　推荐院校：北京航空航天大学、中国民用航空学院、南京航空航天大学、西北工业大学　　19.边防管理学　　专业介绍：本专业培养适应新时期公安边防工作需要，德、智、体、美全面发展，基础理论扎实，业务素质高，实践能力强，富有创新精神，能在公安边防部队从事国(边)境管理、出入境边防检查和部队管理等方面工作的高级专门人才。　　就业前景：主要到公安边防部队和出入境管理部门从事国(边)境管理和出入境边防检查等方面的工作。毕业生一次性就业率为100%。我国疆域辽阔，随着改革的深入发展，对外开放的领域将越来越广，进出口口岸也必将随之增加，加之当今国际局势并不稳定，为防止国际上某些居心叵测的势力和个别不法分子入境，边防管理将会更加重要。　　推荐院校：中国人民武装警察部队学院　　20.服装设计与工程　　专业介绍：本专业培养掌握服装学科的基本理论和基础知识，能在服装生产、科研、教学、贸易等部门从事服装产品设计与开发、服装生产技术、服装企业管理、针织产品工艺设计与生产、服装贸易以及服装科学研究与教学工作的高级专门人才。　　就业前景：爱美之心人皆有之，服装产业的蓬勃发展急需大量专业人才，该专业毕业生不仅在服装生产和销售企业、服装研究单位、服装行业管理部门从事服装产品开发、市场营销、经营管理、服装理论研究工作，还可到新闻出版机构从事宣传评论等方面工作。　　推荐院校：天津工业大学、江南大学(招生办)三角形方形圆形正五边形的画法能联想到什么数字，没有条件限制，但是是组密码 - 叫阿莫西中心 - 中国网络使得骄傲马戏中心！
三角形方形圆形正五边形的画法能联想到什么数字，没有条件限制，但是是组密码
小站会根据您的关注，为您发现更多，
看到喜欢的小站就马上关注吧！
下一站，你会遇见谁的梦想？
数学是个永恒的话题。&&在数学的天地里，重要的不是我们知道什么，而是我们怎么知道什么.&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&——毕达哥拉斯&&&
趣题：寻找四个共圆的点
5 张矩形的纸片和 6 张圆形的纸片散落在桌面上，如下图所示（其中一张矩形纸片被撕掉了一个角）。考虑所有露在外面的矩形顶点以及纸张边缘处的交点，你能否从中找出四个保证共圆的点？很简单，右下角那个绿色矩形的四个顶点就满足要求，因为矩形的四个顶点显然是共圆的。其实，在这个图里，还有另外三组满足要求的点，你能找到吗？
&&&&&&&&&首先， A 、 B 、 C 、 D 这四个点显然是另一组满足要求的点。另一组不太容易找到的点则是 E 、 F 、 G 、 H 这四个点：由于 &EFG = &EHG = 90& ，因而 E 、 F 、 G 、 H 四点共圆。原题的答案本来到这里就结束了，但有趣的是，题目的原作者自己都没想到，满足要求的点还有一组：由于 &EMN = &EHN = 90& ，因而 E 、 M 、 H 、 N 四点也是共圆的。
这道题的修改版（用一个额外的圆形纸片盖住了 M 点）收录在了 Stephen Barr 的 Second Miscellany of Puzzles 一书中。我则是在 Martin Gardner 的 The Colossal Book of Short Puzzles and Problems 一书中看到的这道题。
趣题：圆内接八边形的面积
一个圆内接八边形，各边长度依次为 2, 2, 2, 2, 3, 3, 3, 3 。求这个八边形的面积。
&&&&&&&&&&&&假设圆的半径为 R 。整个八边形是由 4 个三边分别为 3, R, R 的三角形和 4 个三边分别为 2, R, R 的三角形组成。如果我们重新摆放这 8 个三角形，让这两种三角形交替出现的话，整个图形的面积是不会变的。然而，新的八边形相当于是一个边长为 3 + 2&2 的正方形去掉了 4 个直角边为 &2 的等腰直角三角形以后所得的图形。它的面积是 (3 + 2&2)2 & 4 = 13 + 12&2 。
这是 1978 年 Putnam 数学竞赛的 B1 题。我是在 Proofs Without Words II & More Exercises in Visual Thinking 一书里看到的题目及其解法。
立方和公式的一个组合数学证明
&&观察下面几个式子：&&&&&&13 = 1； (1)2 = 1 &&&&&&13 + 23 = 9； (1 + 2)2 = 9 &&&&&&13 + 23 + 33 = 36； (1 + 2 + 3)2 = 36 &&&&&&13 + 23 + 33 + 43 = 100； (1 + 2 + 3 + 4)2 = 100 &&&&&&&& &&&&&&大家应该可以猜到，事实上，对于任意正整数 n ，下述等式永远成立：&&&&&&13 + 23 + & + n3 = (1 + 2 + & + n)2&&&&这个恒等式的证明方法有很多很多，今天我看到了一种有趣的组合证明方法，来源于《Proofs that Really Count》的第 8 章。
&&&&首先，让我们考虑所有这样的数列：它由 0 到 n 之间的整数组成，长度为 4 ，并且最后一个数严格大于前面所有的数。我们把所有满足要求的数列所组成的集合叫做集合 A 。也就是说：&&&&&&A = {(a, b, c, d) | 0 & a, b, c & d & n}&&&&集合 A 里面有多少元素呢？我们可以这样来计算：最后一个数 d 的值可以从 1 到 n 当中选择，只要 d 选定了，前面的数都可以从 0 到 d - 1 之间任意选择，这一共会产生 d3 种选法。于是，集合 A 的元素个数就是 13 + 23 + & + n3。&&&&接下来，让我们考虑所有这样的数列：它由 0 到 n 之间的整数组成，长度为 4 ，并且第 2 个数严格大于第 1 个数，第 4 个数严格大于第 3 个数。我们把所有满足要求的数列所组成的集合叫做集合 B 。也就是说：&&&&&&B = {(x, y, z, w) | 0 & x & y & n 并且 0 & z & w & n}&&&&集合 B 里面有多少元素呢？我们可以按照下面这种方式来计算。如果 x 选的是 n - 1，那么 y 有 1 种选法；如果 x 选的是 n - 2，那么 y 有 2 种选法&&如果 x 选的是 0，那么 y 有 n 种选法。总之，选择合适的 x 和 y 就有 1 + 2 + & + n 种选法。类似地，选择合适的 z 和 w 也有 1 + 2 + & + n 种选法，因而满足要求的数列一共有 (1 + 2 + & + n)2 个。&&&&接下来，我们在 A 、 B 两个集合之间建立一种一一对应的关系，从而证明 13 + 23 + & + n3 = (1 + 2 + & + n)2 。对于 A 当中的任意一个元素 (a, b, c, d) ：如果 a & b ，那么数列保持原形不变，仍然是 (a, b, c, d) ；如果 a & b ，那么把数列变为 (c, d, b, a) ；如果 a = b ，那么把数列变为 (b, d, c, d) 。容易看出，集合 A 当中的每一个元素都会唯一地对应于集合 B 当中的某个合法的元素。举三个例子：&&&&&&(1, 2, 3, 4) & (1, 2, 3, 4) &&&&&&(2, 1, 3, 4) & (3, 4, 1, 2) &&&&&&(1, 1, 2, 4) & (1, 4, 2, 4)&&&&反过来，对于 B 当中的任意一个元素 (x, y, z, w) ：如果 y & w ，那么数列保持原形不变，仍然是 (x, y, z, w) ；如果 y & w ，那么把数列变为 (w, z, x, y) ；如果 y = w ，那么把数列变为 (x, x, z, w) 。容易看出，集合 B 当中的每一个元素都能变回为集合 A 当中的元素。因此，集合 A 和集合 B 里的元素确实是一样多的。
Penney 的游戏：正所谓后发制人，先发制于人
让我们来玩一个游戏。连续抛掷硬币，直到最近三次硬币抛掷结果是&正反反&或者&反反正&。如果是前者，那么我获胜，你需要给我 1 元钱；如果是后者，那么你获胜，我会给你 1 元钱。你愿意跟我玩这样的游戏吗？换句话说，这个游戏是公平的吗？乍看上去，你似乎没有什么不同意这种玩法的理由，毕竟&正反反&和&反反正&的概率是均等的。连续抛掷三次硬币可以产生 8 种不同的结果，上述两种各占其中的 1/8 。况且，序列&正反反&和&反反正&看上去又是如此对称，获胜概率怎么看怎么一样。实际情况究竟如何呢？实际情况是，这个游戏并不是公平的&&我的获胜概率是你的 3 倍！虽然&正反反&和&反反正&在一串随机硬币正反序列中出现的频率理论上是相同的，但别忘了这两个序列之间有一个竞争的关系，它们要比赛看谁先出现。一旦抛掷硬币产生出了其中一种序列，游戏即宣告结束。这样一来，你就会处于一个非常窘迫的位置：不管什么时候，只要掷出了一个正面，如果你还没赢的话，你就赢不了了&&在出现&反反正&之前，我的&正反反&必然会先出现。事实上，整个游戏的前两次硬币抛掷结果就已经决定了两人最终的命运。只要前两次抛掷结果是&正正&、&正反&、&反正&中的一个，我都必胜无疑，你完全没有翻身的机会；只有前两次掷出的是&反反&的结果，你才会赢得游戏的胜利。因此，我们两人的获胜概率是 3:1 ，我的优势绝不止是一点。你或许想问，如果已知我的硬币序列是&正反反&，那么你应该选择一个怎样的硬币序列，就能保证获胜概率超过我呢？研究表明，你可以选择&正正反&，这样一来，我们两人的获胜概率将会变为 1:2 ，换句话说你将会有 2/3 的概率获胜。
趣题站 2014 年 5 月的趣题对此进行了更深一步的探究。A 、 B 两人打算玩这么一个游戏。首先， A 选择一个长度为 n 的正反序列，然后 B 再选择另一个长度为 n 的正反序列。之后，不断抛掷硬币，哪名玩家所选的正反序列最先出现，哪名玩家就获胜。我们的问题是，假如两名玩家都采取最优策略的话，对于哪些 n ，游戏对玩家 A 更有利一些（换句话说，玩家 A 拥有超过 50% 的胜率），对于哪些 n ，游戏对玩家 B 更有利一些（换句话说，玩家 B 拥有超过 50% 的胜率）。今后，为了方便起见，我们用数字 1 代表&正面&，用数字 0 代表&反面&。&&当 n = 1 时，两名玩家的获胜概率显然相同。当 n = 2 时，可以验证，除了 00 打 10 以及 11 打 01 的胜率之比是 1:3 以外，其他所有情况（包括 00 打 11 、 00 打 01 、 01 打 10 、 11 打 10 等四种）的胜率之比都是 1:1 。因而，如果两名玩家都采用最优策略的话， A 一定会选择 01 和 10 之一，从而避免 B 获得 3 倍于自己的胜率。最终结果便是，两人的胜率之比维持在 1:1 的位置，获胜概率仍然相同。令人意想不到的是，当 n & 2 时，游戏总是对玩家 B 更有利的。换句话说，我们要证明，当 n & 2 时，不管 A 选择的 01 串是什么，玩家 B 总能有针对性地选择一个恰当的 01 串，使得他获胜的概率大于 50% 。事实上，我们会证明这样一个结论：玩家 B 总可以截取 A 所选的 01 串的前 n & 1 位，再在前面加上一个数字 0 或者数字 1 作为自己的 01 串，从而使得自己获胜的概率至少有 (2 & (1/2)n-1)/3 。不妨把 A 选择的 01 串记作 Py （其中 P 是一个长度为 n & 1 的 01 串， y 则表示数字 0 或者数字 1 ），我们先来看看，如果 B 选择的 01 串是 0P ，结果将会怎样。不断抛掷硬币，直到最近 n & 1 次硬币抛掷结果正好是序列 P 。这有三种情况：情况一，最近 n 次硬币抛掷结果是 0P ；情况二，最近 n 次硬币抛掷结果是 1P ；情况三，目前硬币抛掷次数还不足 n 次。情况三是最为特殊的，它意味着整个游戏的前 n & 1 次硬币抛掷结果正好就是序列 P ，其概率为 (1/2)n-1 。让我们假设情况一出现的概率是 p1 ，则情况二出现的概率就是 1 & (1/2)n-1 & p1 。如果出现了情况一，那么玩家 B 就直接获胜了，游戏结束；如果出现了情况二或者情况三，那么游戏仍需继续进行下去。不妨把此时的游戏局面叫做节点 X 。现在，玩家 A 离胜利已经非常接近了。如果下一次抛掷硬币的结果正好是 y ，那么玩家 A 就获胜了，游戏结束；如果下一次抛掷硬币的结果是 y （这里 y 表示与 y 相反的数字），那么游戏将会到达另外一个关键的中间状态：最近 n 次硬币抛掷结果为 Py 。对于两名玩家来说，这是全新的起跑线。如果下一次出现 P 的时候，它前面的那个数字是 0 ，那么玩家 B 就直接获胜了，游戏结束；如果下一次出现 P 的时候，它前面的那个数字是 1 ，那么游戏状态又会回到节点 X ，玩家 A 将会再次得到一个制胜的绝佳机会。不妨假设以 Py 打头的随机 01 序列中，下一个 P 的前面正好是数字 0 的概率为 p2 ，那么下一个 P 的前面正好是数字 1 的概率就是 1 & p2 。于是，整个游戏的状态转移图如下图所示。
玩家 B 获胜的概率就可以用 p1 和 p2 表示出来了。首次出现 P 的时候玩家 B 就获胜的概率为 p1 ，有另外 1 & p1 的概率进入节点 X 。进入节点 X 以后， A 将会有 1/2 的概率获胜， B 将会有 (1/2) & p2 的概率获胜，其余情况下游戏局面将会回到节点 X ，刚才的各种事件会以相同比例的概率再次发生，并且有可能一遍一遍地重复下去。因此，总的来说，进入节点 X 以后，两名玩家的获胜概率之比是 (1/2) : ((1/2) & p2) ；进而得出，进入节点 X 以后，玩家 B 获胜的概率就是 ((1/2) & p2) / (1/2 + (1/2) & p2) = p2 / (1 + p2) 。综上所述，玩家 B 的获胜概率应为：W0 = p1 + (1 & p1) & p2 / (1 + p2)别忘了，上述概率值仅仅是 A 在选择了 01 串 Py 之后， B 以 0P 应对时获胜的概率。如果 B 选择以 1P 应对呢？整个游戏的状态转移图将会变成下面这样。
前面我们说过，硬币序列里第一次出现 P 的时候，最近 n 次硬币抛掷结果是 0P ，最近 n 次硬币抛掷结果是 1P ，目前硬币抛掷次数还不足 n 次，这三种情况的发生概率分别为 p1 、 1 & (1/2)n-1 & p1 和 (1/2)n-1 。然而，这次玩家 B 选择的 01 串变成了 1P ，因而游戏开始时进入两条支线的概率就成为了图中所示的那样。另外，从 Py 出发随机产生 01 串，下次出现 P 时它的前面正好是数字 1 的概率为 1 & p2 ，因而我们需要把第一幅状态转移图当中的所有 p2 都替换成 1 & p2 。可以计算出，进入节点 X 以后，两人的胜率之比为 (1/2) : ((1/2) & (1 & p2)) ，其中 B 的获胜概率为((1/2) & (1 & p2)) / (1/2 + (1/2) & (1 & p2)) = (1 & p2) / (2 & p2)玩家 B 的总获胜概率就是：W1 = 1 & (1/2)n-1 & p1 + ((1/2)n-1 + p1) & (1 & p2) / (2 & p2)我们要证明的即是， W0 和 W1 总有一个大于等于 (2 & (1/2)n-1)/3 。注意到，如果固定 p2 不变，把 W0 和 W1 都看作是关于 p1 的函数，那么 W0 将会是一个线性递增函数， W1 则是一个线性递减函数，因此最坏的情况将会发生在 W0 = W1 的时候，此时 W0 和 W1 中的较大值达到最小。解得p1 = (1/3) & (2 & (1/2)n-1 & p2 & (1/2)n-1 & p2)把上式代回 W0 或者 W1 当中的任意一个，得到的是一个与 p2 无关的数，它正是 (2 & (1/2)n-1)/3 。下图是 n = 3 时 W0 和 W1 的图像，可以看到两个图像相交在一起，形成了一条高度大约为 0.58 的交线。至此，我们便成功地证明了，当 n & 2 时，不管 A 选的 01 串是什么， B 总能有针对性地选择另一个 01 串，使得获胜概率可以高达 50% 以上。
&事实上，如果把玩家 A 的选择记作 Py ，那么玩家 B 的最优策略一定就是 0P 和 1P 之一。这个结论是由 Leonidas Guibas 和 Andy Odlyzko 在 1978 年合写的一篇论文里证明的。当 n = 3 时，玩家 B 的最优策略可以归纳如下：
如果 A 选的是那么 B 应该选两人的胜率之比
掌握了上面这个表格的话，你就拥有了一个骗小女生的绝好工具。 YouTube 的
系列视频上就介绍了这个 bar trick ：把游戏规则告诉小女生，让她先选一个长度为 3 的硬币序列，然后你再按照上表选择一个对应的硬币序列，你便能保证获得至少 2 倍于她的胜率。重复多次游戏，你将会以很惊人的大比分获胜。你甚至不需要刻意去背表格，只需要记住：如果对方的选择是 wxy ，那么你选择 xwx 就行了。当然，玩家 B 的最优选择也并不总是把 Py 的第 2 位取反后加在 P 的前面。当 n = 5 时，如果 A 选择了 10110 ，那么 B 选择 11011 会得到 7/12 & 58% 的胜率，而选择 01011 则会得到 17/24 & 71% 的胜率，后者才是他的最优选择。 Leonidas Guibas 和 Andy Odlyzko 认为，玩家 B 究竟是选 0P 更好还是选 1P 更好，这并没有一个明显的规律。有人或许想问，这些概率值都是怎么计算出来的呀？ John Conway 在 Winning Ways for Your Mathematical Plays 的第 4 卷中提到了一种方法。假如 a 和 b 是两个 n 位 01 串。如果 a 和 b 完全相等，那么记一个数字 1 ，如果不相等，那么记一个数字 0 。接下来，比较 a 的后面 n & 1 位以及 b 的前面 n & 1 位，如果相等，那么接着记一个数字 1 ，如果不相等，那么接着记一个数字 0 。接下来，比较 a 的后 n & 2 位以及 b 的前 n & 2 位，并根据比较结果记下数字 0 或者数字 1 。不断这样做下去，直到最后比较 a 的最后面 1 位和 b 的最前面 1 位，并产生新的数字。在整个过程中，你会依次记下 n 个数字，最终会得到一个 n 位的 01 串。把它当作一个二进制数，并转换成十进制。我们把最终的结果记为 L(a, b) 。举几个例子：
L(1) = (10010)2 = 18
L(1) = (00001)2 = 1
L(0) = (10000)2 = 16
L(0) = (01001)2 = 9那么， 01 串 a 和 b 的胜率之比就是(L(b, b) & L(b, a)) : (L(a, a) & L(a, b))因此， 10110 和 01011 的胜率之比就是 (16 & 9) : (18 & 1) ，也就是 7:17 。刚才玩家 B 的获胜概率 17/24 & 71% 就是用这种方法算出来的。不过， John Conway 本人似乎从未发表过这个神奇公式的正确性证明。&其实，之前在证明这个游戏对 B 更有利的时候，证明过程当中有一个小漏洞，我们有意没说：如果 Py = 000&00 的话，那么 0P 将会等于 Py ；类似地，如果 Py = 111&11 的话，那么 1P 将会等于 Py 。这违反了游戏的规则（两人不能选取相同的 01 串），而且也没法套在刚才的状态转移图里。好在，这两种情况单独分析起来非常容易。事实上，我们很容易证明， A 永远不应该选择 000&00 或者 111&11 ，因为这是最笨的策略。如果 A 选择的是 000&00 ，那么 B 只需要选择 100&00 即可。容易看出，只有开局后的前 n 位硬币序列恰好是 000&00 的情况下， A 才能获胜，如果第 n 次抛掷硬币以后 A 还没获胜的话，那么 B 就锁定胜局了&&在出现 000&00 之前， 100&00 必然会先出现。因此， A 的胜率仅为 (1/2)n ，而 B 的胜率则为 1 & (1/2)n 。为什么说这是 A 最笨的策略呢？这是因为，不管 A 选择了什么 01 串，他获胜的概率至少也有 (1/2)n （即开局后的前 n 位硬币序列恰好如 A 所选的情况），因而刚才那种策略的获胜概率已经达到下限，糟糕得不能再糟糕了。类似地，如果 A 选择 111&111 ，那么 B 可以选择 011&11 ，这同样能让 A 的获胜概率降到最低。讨论到这里，大家肯定想要问：那么， A 的最优策略又是什么呢？1992 年， J&nos Csirik 在一篇论文中指出，当 n & 3 时， A 的最优策略之一是
（中间有 n & 3 个数字 0 ），此时 B 应该选择
来应对，两人的胜率之比将会变成 (2n-2 + 1) : (2n-1 + 1) 。当 n = 3 时，查阅上面给出的表格可知， A 的最优策略可以是 010, 011, 100, 101 当中的任意一个。当然， A 的最优策略并不能让 A 的获胜概率大于 50% ，只能让 A 的损失尽可能地小罢了。&对了，这个有趣的游戏叫做 Penney&s game ，它是由 Walter Penney 在 1969 年提出来的。
将立方体绕其体对角线旋转一周后会得到什么图形？
最近看到一道小学数学题，非常考验人的空间想象能力：将一个立方体绕着它的对角线 AC1 旋转一周，会得到下面的哪一种立体图形？
&&&&&&&&&答案是 D 。下面是我自己做的一个演示动画。
你猜对了吗？
在 2048 里能够得到的最大的数是多少？
Michael Brand 在 Using your Head is Permitted 趣题站 2014 年 4 月的中提出了一个这样的问题：在最近非常流行的小游戏
中，你能得到的最大的数是多少？在这里，我们简单描述一下游戏的规则。游戏在一个 4 & 4 的棋盘上进行，棋盘里填有一个个的&数块&，每个数块上都写有某个形如 2n 的正整数。每一步，你需要从上、下、左、右四个方向中选取一个方向，按下对应的方向键之后，所有的数块都会&落&到这个方向；若有两个同种的数块在此过程中发生碰撞，则它们的值会相加起来，并合成一个新的数块。然后，系统会在棋盘中随机选择一个空白位置，并在此生出一个新的数块，上面写有数字 2 或者数字 4 （两种情况之比为 9 : 1）。游戏开始时，棋盘上会自动生成两个随机的数块，你的目标就是通过有限步的操作，得出一个写有 2048 的数块。当然，即使得到了 2048 这个数块，游戏也不会自动结束，你还可以向更大的数发起挑战。于是就有了我们刚才的问题：理论上，这个游戏当中能够得到的最大的数是多少？&可以证明，我们永远不可能在 2048 当中玩出 218 这个数。让我们把棋盘上的所有数全部加起来，并在累加过程中不断关注当前总和的二进制表达。如果棋盘里的数分别是 2, 4, 16, 64, 16, 2 的话，累加结果的二进制表达依次为 10 & 110 & 10110 & 1010110 & 1100110 & 1101000 。你会发现，由于棋盘上的每个数都是形如 2n 的正整数，因而把它加进总和之后，这个总和的二进制表达里最多只会多出一个数字 1 （如果发生了进位，数字 1 的个数可能会不变甚至减少）。这意味着，如果最终棋盘上的所有数之和的二进制表达当中一共有 k 个数字 1 ，那就说明刚才至少有 k 个数在相加，换句话说棋盘里至少有 k 个数块。容易看出，每走一步之后，棋盘上的所有数之和都会增加 2 或者 4 。如果最终棋盘上出现了一个 218 ，就说明棋盘上的所有数之和至少是 218 ，那么在此之前棋盘上的所有数之和一定经历过 218 & 2 或者 218 & 4 。前者的二进制表达为 11 11 1110 ，这里面有 17 个数字 1 ，超过了棋盘里总的格子数，因而显然是不可能的。后者的二进制表达是 11 11 1100 ，这里面有 16 个数字 1 ，正好是棋盘里总的格子数。这说明，此时棋盘刚好被填满， 22, 23, 24, &, 217 这 16 种不同的数块各有一个。这意味着棋盘里不但没有空白的格子，也没有相同种类的数块可以合并，此时玩家直接就死掉了！因而，我们是没有办法得到 218 的。因此， 217 = 131072 成为了 2048 这个游戏中数块大小的一个理论上限。但是，我们真的能弄出 131072 吗？看上去，我们好像只需要构造出下图所示的局面就行了，但这个局面本身能否实现，还有待进一步讨论。 Michael Brand 猜测，理论上 131072 也是无法得到的，但他不能证明这一点。我虽然在网上看见过很多网友宣称自己打出过 131072 ，甚至有的网友发出了最后几步的视频（比如），但由于我从来没有看到过完整的演示过程，因而也持怀疑态度。期待万能的网友们能够提供一种简洁有效的构造解，来说明当运气足够好的情况下，我们有办法打出 131072 ；或者找到一个更好的证明方法，足以说明 131072 也是理论上不可能实现的。
最后补充一句： 2048 的游戏概念来源于另一款叫做
的游戏。如果你喜欢 2048 的话，建议你去购买 Threes! ，它无疑比 2048 更加精致，更加有趣。我的 iPad 上只装了一个游戏，就是 Threes! 。
杨辉三角中的自然底数 e
杨辉三角中的自然底数 e&
你相信吗，杨辉三角里竟然也有自然底数 e 的身影。 2012 年， Harlan Brothers 发现了杨辉三角中的一个有趣的事实。不妨把杨辉三角第 n 行的所有数之积记作 sn ，那么随着 n 的增加， sn & sn+2 / sn+12 会越来越接近 e & 2.718 。事实上，我们有：
这是为什么呢？ John Baez 在上给出了一个漂亮的解释。
首先，让杨辉三角 (A) 里面的每个数都除以它左下角的那个数，于是得到了图 (B) 所示的三角形数阵。你会发现，这个数阵里有一个很明显的模式，即第 n 行的所有数分母都是 n ，分子则分别是 n, n-1, &, 2, 1 。这并不是巧合。这是因为：
接下来，让图 (B) 里的所有数都除以它右下角的那个数，于是得到了图 (C) 所示的三角形数阵。容易看出，这个数阵第 n 行的所有 n 个数应该都是 (n + 1) / n = 1 + 1/n ，它们乘起来等于 (1 + 1/n)n 。随着 n 的增加，这个数会越来越接近 e 。最后，让我们追溯一下图 (C) 中每个数的来源。图 (C) 中第 n 行的每个数都等于图 (B) 中第 n 行的某个数除以第 n + 1 行的某个数，进而等于图 (A) 中第 n 行的某个数除以第 n + 1 行的某个数的结果，除以第 n + 1 行的某个数除以第 n + 2 行的某个数的结果。因此，图 (C) 中第 n 行的所有数乘起来，结果正是 sn & sn+2 / sn+12
趣题：2014 年 INMO 中的一个问题
这是 2014 年印度全国奥林匹克数学竞赛（INMO）的第 2 题：求证，对于任意正整数 n ，[n/1] + [n/2] + [n/3] + & + [n/n] + [&n]总是偶数。这里， [x] 表示不超过 x 的最大整数。&&&&&&&&&&官方给出的解答采用的是数学归纳法。不妨令f(n) = [n/1] + [n/2] + [n/3] + & + [n/n] + [&n]容易算出 f(1) = 2 ，这是一个偶数。接下来我们只需要证明，对于所有的正整数 k ， f(k+1) & f(k) 的结果都是一个偶数。注意，如果 i 正好是 k+1 的一个约数，那么 [(k+1)/i] & [k/i] 将会等于 1 ，否则 [(k+1)/i] & [k/i] 都会等于 0 。于是我们有f(k+1) & f(k) = σ(k+1) + [&k+1] & [&k]其中 σ(k+1) 表示 k+1 的约数个数。由于一个数的约数总是成对地出现，因而 σ(k+1) 几乎总是一个偶数，除非 k+1 恰好是一个完全平方数；另外， [&k+1] & [&k] 的值几乎总是为 0 ，只有当 k+1 恰好是一个完全平方数时才等于 1 。也就是说，当 k+1 不是完全平方数时， σ(k+1) 是一个偶数，并且 [&k+1] & [&k] = 0 ；当 k+1 正好是完全平方数时， σ(k+1) 是一个奇数，并且 [&k+1] & [&k] = 1 。不管怎样， f(k+1) & f(k) = σ(k+1) + [&k+1] & [&k] 的结果都是一个偶数。至此，结论也就证到了。有趣的是，当网友在
上提出了这个问题后， David Angell 给出了一个更具启发性的证明。容易看出， [n/1] + [n/2] + [n/3] + & + [n/n] 的值，其实就是第一象限里位于函数 y = n/x 及其下方的整数格点的个数。我们把这些点分成两类：位于一三象限角平分线以外的，以及恰好位于一三象限角平分线上的。前一类的点总是成对地出现，因而一定有偶数个。但是，后一类点并不是成对出现的。那么，这些点一共有多少个呢？注意到，这些点也就是所有形如 (i, i) 的点，其中 i2 不能超过 n 。因而，这样的点一共有 [&n] 个。
因此， [n/1] + [n/2] + [n/3] + & + [n/n] + [&n] 的值，其实就等于这两类点的总个数，其中后一类点被重复计算了两次。这个值显然应该是偶数。题目来源：
多边形外角和等于 360° 的一种直观解释
多边形外角和等于 360& 的一种直观解释&
趣题：用 k × 1 的矩形覆盖 n × n 的正方形棋盘
用 k & 1 的小矩形覆盖一个 n & n 的正方形棋盘，往往不能实现完全覆盖（比如，有时候 n & n 甚至根本就不是 k 的整倍数）。不过，在众多覆盖方案中，总有一种覆盖方案会让没有覆盖到的方格个数达到最少，我们就用 m(n, k) 来表示这个数目。求证：不管 n 和 k 是多少， m(n, k) 一定是一个完全平方数。&&&&&&如果 n & k ，那么很明显，棋盘里一个小矩形也放不下，因而 m(n, k) = n2 ，这是一个完全平方数。下面我们就只考虑 n & k 了。
我们先来证明这样一个事实：如果某个覆盖方案当中，仅剩下一个 s & s 的小正方形区域没有覆盖到，其中 s & k / 2 ，那么这样的方案一定是最优的。首先，在棋盘中的每个格子里都填上一个数，使得从最左下角出发，各个对角线上的数依次为 0, 1, 2, &, k & 1, 0, 1, 2, &, k & 1, & （上图所示的是 k = 6 的情况）。那么，把一个 k & 1 的小矩形放在棋盘中的任意位置，它总会覆盖每种数字各一个。假设某个覆盖方案当中，仅剩下一个 s & s 的小正方形区域没有覆盖到。注意到，任意一个 s & s 的小正方形区域里最多只会出现 2s & 1 种不同的数，因此如果 s & k / 2 ，那么这个 s & s 的小正方形区域里一定会缺失至少一种数，比方说 x （在上图中，右上角的那个 3 & 3 的空白区域里就缺数字 5 ，因而我们可以取 x = 5 ）。由此可以推出，此时小矩形的数目已经达到了最大值，任何其他覆盖方案都不可能包含更多的小矩形，因为每个小矩形都必然会覆盖到一个 x ，然而在刚才的覆盖方案中，所有的 x 都已经被覆盖到了。&
有趣的是，当 n & k 时，让整个棋盘仅剩一个边长不超过 k / 2 的小正方形区域没有覆盖到，这是一定能做到的。不妨把 n 除以 k 的余数记作 r 。如果 r & k / 2 ，那么我们可以直接用横着的小矩形从左向右填充棋盘，再用竖着的小矩形填充余下的部分，最终会剩下 r & r 的小正方形区域。上图所示的就是 n = 22 并且 k = 5 的情况，注意到 22 除以 5 的余数为 2 ，确实小于等于除数 5 的一半。可见，对于这类情况，我们都有 m(n, k) = r2 ，这是一个完全平方数。&
如果 r & k / 2 呢？我们可以用和刚才类似的方法填充棋盘，使得棋盘右上角仅剩一个 (r + k) & (r + k) 的正方形区域。然后再用 4r 个小矩形像风车一样填充这个 (r + k) & (r + k) 的区域，使得正中间只剩下一个边长为 k & r 的小正方形区域。由于 k & r & k / 2 ，因而此时的覆盖方案再次达到最优。上图所示的就是 n = 22 并且 k = 6 的情况，注意到 22 除以 6 的余数为 4 ，确实大于除数 6 的一半。可见，对于这类情况，我们有 m(n, k) = (k & r)2 ，这仍然是一个完全平方数。题目来源：
趣题：圆中的两个相切的半圆
下面这个结论是 Andrew Jobbings 在 2011 年指出的：
AB 是圆 O 的一条直径， CD 、 EF 是两条垂直于 AB 的弦，并且以 CD 为直径的半圆和以 EF 为直径的半圆正好切于点 T 。那么，两个半圆的面积之和一定等于圆 O 的面积的一半。你能证明这个结论吗？
&&&&&&&&&&
网站上给出的一种证明方法。如果把两个半圆的半径分别记作 r1 和 r2 ，把整个大圆的半径记作 R ，那么我们只需要证明π r12 / 2 + π r22 / 2 = π R2 / 2即r12 + r22 = R2由于 △MCO 是直角三角形，由勾股定理可知MO2 + MC2 = OC2其中 MC 就是其中左边那个半圆的半径， OC 就是整个圆 O 的半径，因而我们只需要证明 MO 就是右边那个半圆的半径即可。现在，连接 CT 、 FT ，你会发现 △MCT 和 △NFT 都是等腰直角三角形，并且 C 、 T 、 F 在一条直线上。由于圆心角的度数是圆周角的两倍，因此 &COE = 2 &CFE = 90& ，由此可知 &1 + &2 = 90& 。而 &2 + &3 = 90& ，于是 &1 = &3 。根据同样的道理，我们还可以得到 &2 = &4 。再加上整个大圆的半径 OC = OE ，就足以判定 △MCO 和 △NOE 全等了。这说明 MO = NE ，而后者正是右边那个半圆的半径。
利用重心推导平方和公式
假设平面上有 1 + 2 + 3 + & + n 个小球，每个小球的质量都是 1kg 。它们排成了一个三角形阵，具体地说，它们排成了一个倒置的、以 (0, 1) 为顶点的等边三角形。这个三角形阵作为一整个物体，它的重心的 y 坐标是多少？我们有两种不同的求解方法。
第一种方法是暴力方法。这个物体的重心的 y 坐标，一定等于所有小球的 y 坐标的平均值，即(1 & 1 + 2 & 2 + 3 & 3 + & + n & n) / (1 + 2 + 3 + & + n)或者写作(12 + 22 + 32 + & + n2) / (n & (n + 1) / 2)另一种方法则是利用图形的对称性。由对称性，整个三角形阵的重心显然应该位于这个三角形各边中线的交点上，一些经典的几何结论可以告诉我们，这个交点正好把每条中线都分成了 1 : 2 两段。因而，这个点的 y 坐标就是1 + 2 & (n & 1) / 3 = (2 n + 1) / 3这两种方法求出来的答案应该相等。于是，我们得到了等式(12 + 22 + 32 + & + n2) / (n & (n + 1) / 2) = (2 n + 1) / 3即12 + 22 + 32 + & + n2 = n & (n + 1) & (2 n + 1) / 6这个方法是我在 Proofs Without Words II & More Exercises in Visual Thinking 一书里看到的。&
2014 年 9 月 1 日 / 几何, 数列, 物理, 证明&
有点意思 貌似不太好推广啊，比如立方和。 唔，我试试正四面体之类的会给出什么东西&&
对了，昨天晚上我试了下，一开始用的四棱锥&&因为直接就是立方和了。但是对称性不好。 最后结果有点出入，只在n&&才一致，大概是因为虽然点阵的分布是均匀的，但跟四棱锥真正的均匀分布还是不一样的。 然后试了下正四面体，有点麻烦，要消去一坨东西，不过最后还是得出来了立方和的。不知有没有更简单的几何方法。
竟然不是lochost8080回复&已阅&！
少打了几个字母。。。localhost8080
可以用杨辉三角的性质和高次相减的方法
二维表述的证明： 设点阵(x1，y1 ), (x2，y2 ), &, (xn，yn )为多边形各顶点;则其质心坐标为O(&x n/n, &y n/n);以O为圆心的圆为(x-&x n/n)2+(y-&y n/n)2=C （C为常数，任意半径的平方。）;对于其上一点P，有(xp-&x n/n)2+(yp-&y n/n)2=C ;展开其，两边乘以n，nxp2-2xp&x n +n (&x n/n)2 +nyp2-2yp&y n +n (&y n/n)2 =nC ;调整常数，&(xp2-2xpx n+x n2+ yp2-2ypy n+y n2)=nC-[n (&x n/n)2 +n (&y n/n)2-x 12-y12-x22-y22-&-x n2-y n2]=C& （易知C&亦为常数）;从而，&[(xp- x n) 2+(yp- yn) 2]= C& .命题得证。 推广至多维形式： 由定理二维形式的证明可以看出，升维后所多出的变量（例如z）及各展开项系数是决定升维后定理成立的关键。 由于对于任意维度D，设该维度下的各广义球方程都可表述为：&d[x(d)-a(d)]2=r2其中，x(d)为d维空间的各轴或曰参数，a(d)为球心在各轴上投影坐标，r为半径； 设其圆心为O[&x(1) n/n, &x(2) n/n,...,&x(d) n/n]， 即点集x(1) n, x(2) n,&,x(d) n的广义质心，则对其上一点P，有&d[x(d)p-&nx(d) n/n]2=r2两边乘以n，则其展开式中，x(d)p&x(d) n其系数恒为-2，说明总可以将其写为：&d{&n[x(d)p- x n ]2}= C(常数)的形式。
趣题：竞技场里的狮子能否保证抓住最高速度相同的小明？
小明和狮子同被关在一个半径为 10 米的竞技场里，狮子位于竞技场的圆心处，小明则在距离圆心 1 米的地方。两者的最大运动速度都是每秒 1 米。狮子有没有什么必胜策略，使得不管小明怎么跑，它总能在有限的时间里抓住小明？根据
相关词条的描述，这个问题是由 R. Rado 在 1925 年时提出的。一个经典的&答案&是，狮子只需要始终保持自己与小明在圆盘的同一半径上即可。直觉上看，由于狮子总是处在&内圈&上，因而不管小明跑到了哪里，狮子总能轻松地与小明继续保持在同一半径上；并且，狮子总有足够的余力向小明靠近，严格减小它与小明之间的距离，除非小明是沿着半径方向径直向外跑。由于竞技场的大小是有限的，小明不可能无限地向外跑，因而狮子最终总会追上小明。但是，后来人们发现，这个解法其实是错误的，原因很简单：能不断靠近小明，不一定就能在有限的时间里抓住小明，正如 1/2 + 1/4 + 1/8 + 1/16 + & 永远不会超过 1 一样。最终， A. S. Besicovitch 为小明构造出了一个极其巧妙的策略，使得狮子无论如何都抓不到小明，从而完美地解决了这个问题。不过， MathWorld 的词条里并没有提到这个解法。你能想到这个解法吗？&&&&&&&A. S. Besicovitch 为小明设计的策略如下。游戏开始后，小明首先把接下来的时间分成一小段一小段的，这些时间段的长度依次为 t1, t2, t3, t4, & 。不妨把竞技场的圆心记作 O ，把小明当前的位置记作 M 。每个时间段开始的时候，小明都会看看此时此刻线段 OM 的位置，并且沿着垂直于 OM 的方向，以最高速度往没有狮子的那一侧跑去（如果狮子的位置恰好位于 OM 所在直线上，则向任意一侧跑去）。容易看出，不管在哪个时间段里，狮子都不可能追到小明。如果把第 i 个时段结束后小明与圆心的距离 OM 记作 ri ，那么由勾股定理可知：ri2 = ri-12 + (ti & 1)2 = ri-12 + ti2其中 r0 = 1 。
因此，当 t1 + t2 + t3 + & + tn 这么多的时间过去以后，小明与圆心的距离 OM 满足OM2 = rn2 = 12 + t12 + t22 + t32 + & + tn2最巧妙的地方来了。令 ti = 1/i ，那么 t1 + t2 + t3 + & 是发散的，但 t12 + t22 + t32 + & 却是收敛的。具体地说：
&&&t1 + t2 + t3 + t4 + t5 + &= 1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + 1/9 + && 1 + 1/2 + 1/4 + 1/4 + 1/8 + 1/8 + 1/8 + 1/8 + 1/16 + &= 1 + 1/2 + (1/4) & 2 + (1/8) & 4 + (1/16) & 8 + &= 1 + 1/2 + 1/2 + 1/2 + 1/2 + &它显然可以达到任意大。而
&&&t12 + t22 + t32 + t42 + t52 + &= 1 + 1/22 + 1/32 + 1/42 + 1/52 + && 1 + 1/(1&2) + 1/(2&3) + 1/(3&4) + 1/(4&5) + &= 1 + (1 & 1/2) + (1/2 & 1/3) + (1/3 & 1/4) + (1/4 & 1/5) + &= 1 + 1 & 1/2 + 1/2 & 1/3 + 1/3 & 1/4 + 1/4 & 1/5 + && 2因而 OM2 始终不超过 1 + 2 = 3 ， OM 的长度也就始终不超过 &3 & 1.732，这远远小于竞技场的半径（事实上， OM2 的极限是 1 + π2 / 6 ，可以算出 OM 的极限约为 1.63 ）。这说明，不管时间过去了多久，小明始终在坚持运动，并且运动路线始终在可活动范围以内。既然每一个时间段里狮子都无法抓到小明，狮子自然也就永远抓不到小明了。题目和解答最早应该出自 John Littlewood 的 A Mathematician&s Miscellany 一书当中。图片中的小狮子图标来自，小明图标则来自。题目里的&策略&一词缺乏形式化的描述，这使得本文的内容非常不严谨，同时还会引发很多其他有趣的讨论，感兴趣的读者可以见。&
2014 年 8 月 30 日 / 几何, 极限, 算法, 趣题
寻找相邻两项之比不趋于 1.618 的广义 Fibonacci 数列
大家或许知道 Fibonacci 数列 1, 1, 2, 3, 5, 8, & 有一个非常漂亮的性质：数列中的相邻两项之比将会越来越接近黄金比例 (1 + &5) / 2 & 1.618 。事实上，如果我们用 F(n) 来表示第 n 个 Fibonacci 数的话，那么当 n & & 时，我们有 F(n + 1) / F(n) & (1 + &5) / 2 。不过，可能有人并不知道，如果把 Fibonacci 数列的前两项换成两个其他的正整数（但保持 Fibonacci 数列的递推关系不变），由此所得的广义 Fibonacci 数列当中，相邻两项之比仍然会趋近于 (1 + &5) / 2 。比方说，如果数列的前两项为 7, 2 ，那么整个数列的前 15 项以及相邻两项之比的情况如下：
7, 2, 9, 11, 20, 31, 51, 82, 133, 215, 348, 563, 911, , &&2 / 7 = 0.&9 / 2 = 4.5 11 / 9 = 1. / 11 = 1. / 20 = 1.55 51 / 31 = 1. / 51 = 1. / 82 = 1. / 133 = 1. / 215 = 1. / 348 = 1. / 563 = 1.4 / 911 = 1.5 / 1474 = 1.6180461&更神奇的是，即使最前面这两个数当中有一个负数或者都是负数，相邻两项之比的趋势依旧不变！举个例子，若数列的开头两项是 20 和 -13 ，则有：
20, -13, 7, -6, 1, -5, -4, -9, -13, -22, -35, -57, -92, -149, -241, && (-13) / 20 = -0.65 7 / (-13) = -0. (-6) / 7 = -0. 1 / (-6) = -0. (-5) / 1 = -5 (-4) / (-5) = 0.8 (-9) / (-4) = 2.25 (-13) / (-9) = 1.4444444 (-22) / (-13) = 1.6923077 (-35) / (-22) = 1.5909091 (-57) / (-35) = 1.6285714 (-92) / (-57) = 1.6140351 (-149) / (-92) = 1.6195652 (-241) / (-149) = 1.6174497事实上，不管数列的开头两项是多么奇怪的两个实数（比如 -7/2, &2, & 或者 π/10, -&e, & 等等），按照 Fibonacci 式的递推关系算出后面各项，相邻两项之比几乎总会趋于 (1 + &5) / 2 ！注意，刚才我们使用了&几乎&一词，因为这个结论其实并不总是成立。今天的题目就是：请你找出至少一个反例。也就是说，你需要找出至少一个由递推关系 a(i) = a(i & 1) + a(i & 2) 生成的数列，使得当 n 趋于无穷大时 a(n + 1) / a(n) 并不趋于 (1 + &5) / 2 。对了， 0, 0, 0, 0, 0, & 这种情况自然不算。&&为了方便起见，接下来我们把 (1 + &5) / 2 记作 φ ，它约等于 1.618 ；再把 (1 & &5) / 2 记作 φ& ，它约等于 -0.618 。容易看出， φ 和 φ& 是方程 1 + x = x2 的两根。如果数列的开头两项是 1 和 φ& 的话，这个数列会是什么样呢？由于 1 + φ& = φ&2 ，因此数列的下一项是 φ&2 ；由于 φ& + φ&2 = φ& & (1 + φ&) = φ& & φ&2 = φ&3 ，因此数列的下一项是 φ&3；由于 φ&2 + φ&3 = φ&2 & (1 + φ&) = φ&2 & φ&2 = φ&4 ，因此数列的下一项是 φ&4 &&不断这样推下去，大家很快便会发现，整个数列其实就是这样：1, φ&, φ&2, φ&3, φ&4, φ&5, φ&6, &毫无疑问，这个数列的相邻两项之比永远是 φ& = (1 & &5) / 2 ，并不会慢慢趋近于 φ = (1 + &5) / 2 。这就是一个满足要求的反例。万事开头难，有了第一个反例，再找更多的反例就不是难事了。比方说，所有以 c, c & φ&, & 开头的数列全都一并成为了反例，其中 c 可以是任意一个非 0 实数。有趣的是，除此之外，再也没有其他的反例了。换句话说，如果你把相差一个系数的广义 Fibonacci 数列看作本质上相同的数列，那么刚才我们给出的反例是唯一的。下面我们就来证明这一点。&首先注意到，让广义 Fibonacci 数列里的每一项都乘上非 0 实数 c ，得到的仍然是一个广义 Fibonacci 数列。也就是说，如果数列a(1), a(2), a(3), a(4), a(5), &是一个由 a(1) 和 a(2) 生成的广义 Fibonacci 数列，那么c & a(1), c & a(2), c & a(3), c & a(4), c & a(5), &就是一个由 c & a(1) 和 c & a(2) 生成的广义 Fibonacci 数列。另外，两个广义 Fibonacci 数列之和必然也是一个广义 Fibonacci 数列。也就是说，如果数列a(1), a(2), a(3), a(4), a(5), &是一个由 a(1) 和 a(2) 生成的广义 Fibonacci 数列，并且数列b(1), b(2), b(3), b(4), b(5), &是一个由 b(1) 和 b(2) 生成的广义 Fibonacci 数列，那么数列a(1) + b(1), a(2) + b(2), a(3) + b(3), a(4) + b(4), a(5) + b(5), &就是一个由 a(1) + b(1) 和 a(2) + b(2) 生成的广义 Fibonacci 数列。最后别忘了，刚才我们说过， φ 和 φ& 是方程 1 + x = x2 的两根，因而数列1, φ, φ2, φ3, φ4, φ5, φ6, &和1, φ&, φ&2, φ&3, φ&4, φ&5, φ&6, &就成了两个非常特别的广义 Fibonacci 数列。&把上面三点结合起来，我们将会得出结论：一切广义 Fibonacci 数列都可以表示成k + l, k & φ + l & φ&, k & φ2 + l & φ&2, k & φ3 + l & φ&3, k & φ4 + l & φ&4, k & φ5 + l & φ&5, &的形式，其中 k 和 l 是两个适当的常数。例如，为了把经典的 Fibonacci 数列1, 1, 2, 3, 5, 8, &表示成刚才那种形式，我们只需要找出合适的 k 和 l ，使得它们同时满足k + l = 1, k & φ + l & φ& = 1这两个方程。解得 k = φ / &5, l = & φ& / &5 ，因而 Fibonacci 数列实际上就是(φ / &5) & (φ& / &5), (φ / &5) & φ & (φ& / &5) & φ&, (φ / &5) & φ2 & (φ& / &5) & φ&2, (φ / &5) & φ3 & (φ& / &5) & φ&3, &或者干脆写作(φ & φ&) / &5, (φ2 & φ&2) / &5, (φ3 & φ&3) / &5, (φ4 & φ&4) / &5, &这正是 Fibonacci 数列的通项公式。类似地，为了求出广义 Fibonacci 数列20, -13, 7, -6, 1, -5, -4, -9, -13, -22, &的通项公式，我们只需要求解关于 k 和 l 的二元一次方程组k + l = 20, k & φ + l & φ& = -13解得 k = 10 & 23 / &5, l = 10 + 23 / &5 ，因而该数列其实就是(10 & 23 / &5) + (10 + 23 / &5), (10 & 23 / &5) & φ + (10 + 23 / &5) & φ&, (10 & 23 / &5) & φ2 + (10 + 23 / &5) & φ&2, (10 & 23 / &5) & φ3 + (10 + 23 / &5) & φ&3, &&注意， φ 是一个绝对值大于 1 的数， φ& 是一个绝对值小于 1 的数，因而随着 n 的增加， φn 很快便会变得非常非常大，同时 φ&n 也会很快变得非常非常接近于 0 。因此，就算 k 的绝对值再小，就算 l 的绝对值再大， k & φn + l & φ&n 的值也会很快变得和 k & φn 几乎相同，相邻两项之比基本上就相当于是 k & φn+1 和 k & φn 之比，自然也就等于 φ 了。除非&&除非 k 等于 0 ！因此，广义 Fibonacci 数列的相邻两项之比不趋于 φ 的情况仅此一种，此时整个数列实际上为：l, l & φ&, l & φ&2, l & φ&3, l & φ&4, l & φ&5, &&最近在 reddit 上看到了，网友 Gro-Tsen 的让人有醍醐灌顶之感，故写此文记之。
45 道 Bongard 问题：寻找图形分类的依据
如果让你设计一种用于人工智能测试的谜题，你会怎么设计？俄国计算机科学家 Mikhail Moiseevich Bongard 在 1967 年出版的 Проблема Узнавания 一书中提出了一种&图形分类依据&型的谜题。谜题的规则很简单：现已按照某种依据把 12 张图片分成了左右两组（每组各 6 张），问依据是什么。在 Проблема Узнавания 的附录中， Bongard 自己出了 100 道题，并把它们依次编号为 1, 2, 3, &, 100 。很多题目对于人类来说非常简单，分类依据几乎是一目了然；但是，要想设计某种算法让计算机自动解出，则是一件看上去几乎不可能完成的任务。下面这张图是书上第 283 页的三个谜题。第 7 号谜题的答案是，左边的图形都是竖着的，右边的图形都是横着的；第 8 号谜题的答案是，左边的图形都在右边，右边的图形都在左边；第 9 号谜题的答案是，左边的图形都是平滑的线条，右边的图形都是波浪形线条。
这 100 道题里还有很多难题，可能是人类也要看半天才能看出来的。下面这张图是书上第 298 页的三个谜题。第 52 号谜题的答案是，左边的图形箭头方向相反，右边的图形箭头方向相同；第 53 号谜题的答案是，左边的图形中外面那个多边形拥有更多的边，右边的图形中里面那个多边形拥有更多的边；第 54 号谜题的答案是，左边的图形顺时针依次是＋○△，右边的图形逆时针依次是＋○△。
1970 年，这本书的英译版 Pattern Recognition 登陆美国。认知科学专家 Douglas Hofstadter 对附录中的这些谜题产生了极大的兴趣。他把这些问题叫做 Bongard 问题，并且还自编了 56 道新的问题。在他的神作 G&del, Escher, Bach: An Eternal Golden Braid 一书中， Bongard 问题也没少出镜。
Harry Foundalis 对 Bongard 问题也非常感兴趣。他在已有题库的基础上又增加了 44 道题目，从而把问题的编号扩展到了 200 。你可以在 Foundalis 的上看到这些谜题。最近，我也迷上了 Bongard 问题。我从这 200 道题目中选择了 45 道题，并把它们分成了简单、中等、困难三个难度，每个难度各 15 道题。很多简单题都会让我产生一种超越机器的自豪感，同时也会让我由衷地敬佩题目作者变着法子虐人工智能的能力。个别难题则真的非常非常难，足够荒废大家一下午的时间了。希望大家能够喜欢。
EASY 15. 答案：
直边 | 曲边
歪斜 | 对称
封闭 | 有缺口
顺时针 | 逆时针
渐强 | 减弱
一条线 | 两条线
方向统一 | 方向杂乱
两侧数量相等 | 两侧数量不等
实心圆在内部 | 实心圆在端点
竖纹 | 横纹
三角形 | 圆形
MEDIUM 01.
MEDIUM 02.
MEDIUM 03.
MEDIUM 04.
MEDIUM 05.
MEDIUM 06.
MEDIUM 07.
MEDIUM 08.
MEDIUM 09.
MEDIUM 10.
MEDIUM 11.
MEDIUM 12.
MEDIUM 13.
MEDIUM 14.
MEDIUM 15. 答案：
凸图形 | 凹图形
水平通道 | 竖直通道
末梢逐渐变小 | 末梢逐渐变大
三角形在圆形上 | 三角形在圆形下
三角形比圆大 | 三角形比圆小
空心图形覆盖实心图形 | 实心图形覆盖空心图形
两点连线成 \ 形 | 两点连线成 / 形
四个交点 | 两个交点
圆圈在不同分支上 | 圆圈在同一分支上
实心物体更多 | 空心物体更多
框内的三个圆圈距离很近 | 框外的三个圆圈距离很近
加号到两个圆点距离相等 | 加号到两个圆点距离不等
图形嵌套可达两层 | 图形嵌套最多一层
三线延长后交于一点 | 三线延长后不交于一点
左分支的顶端比右分支低 | 左分支的顶端比右分支高
HARD 15. 答案：
线条两端距离很远 | 线条两端距离很近
线条首段和尾段平行 | 线条首段和尾段垂直
有三条简单型的边 | 有三条修饰型的边
实心部分正往宽处漫延 | 实心部分正往窄处漫延
连接后成等腰三角形 | 连接后成斜三角形
三角形指向圆心 | 三角形不指向圆心
多边形以某条边为底 | 多边形以某个顶点为底
实心圆离空心圆更近 | 实心圆离三角形更近
两个小物体之间的连线不被阻挡 | 两个小物体之间的连线会被阻挡
三个点的横坐标等距 | 三个点的纵坐标等距
四个点构成平行四边形 | 四个点不构成平行四边形
边数和点数相等 | 边数和点数不等
圆圈在加号构成的凸包内 | 圆圈在加号构成的凸包外
去掉共线三点后剩下两点呈 : 状 | 去掉共线三点后剩下两点呈 & & 状
依据性质进行分类 | 依据数量进行分类
立方和公式的一个组合数学证明
&观察下面几个式子：&&&&&&13&= 1； (1)2&= 1&&&&&&13&+ 23&= 9； (1 + 2)2&= 9&&&&&&13&+ 23&+ 33&= 36； (1 + 2 + 3)2&= 36&&&&&&13&+ 23&+ 33&+ 43&= 100； (1 + 2 + 3 + 4)2&= 100&&&&&&&& &&&&&&大家应该可以猜到，事实上，对于任意正整数 n ，下述等式永远成立：&&&&&&13&+ 23&+ & + n3&= (1 + 2 + & + n)2&&&&这个恒等式的证明方法有很多很多，今天我看到了一种有趣的组合证明方法，来源于《Proofs that Really Count》的第 8 章。
&&&&首先，让我们考虑所有这样的数列：它由 0 到 n 之间的整数组成，长度为 4 ，并且最后一个数严格大于前面所有的数。我们把所有满足要求的数列所组成的集合叫做集合 A 。也就是说：&&&&&&A = {(a, b, c, d) | 0 & a, b, c & d & n}&&&&集合 A 里面有多少元素呢？我们可以这样来计算：最后一个数 d 的值可以从 1 到 n 当中选择，只要 d 选定了，前面的数都可以从 0 到 d - 1 之间任意选择，这一共会产生 d3&种选法。于是，集合 A 的元素个数就是 13&+ 23&+ & + n3。&&&&接下来，让我们考虑所有这样的数列：它由 0 到 n 之间的整数组成，长度为 4 ，并且第 2 个数严格大于第 1 个数，第 4 个数严格大于第 3 个数。我们把所有满足要求的数列所组成的集合叫做集合 B 。也就是说：&&&&&&B = {(x, y, z, w) | 0 & x & y & n 并且 0 & z & w & n}&&&&集合 B 里面有多少元素呢？我们可以按照下面这种方式来计算。如果 x 选的是 n - 1，那么 y 有 1 种选法；如果 x 选的是 n - 2，那么 y 有 2 种选法&&如果 x 选的是 0，那么 y 有 n 种选法。总之，选择合适的 x 和 y 就有 1 + 2 + & + n 种选法。类似地，选择合适的 z 和 w 也有 1 + 2 + & + n 种选法，因而满足要求的数列一共有 (1 + 2 + & + n)2&个。&&&&接下来，我们在 A 、 B 两个集合之间建立一种一一对应的关系，从而证明 13&+ 23&+ & + n3&= (1 + 2 + & + n)2&。对于 A 当中的任意一个元素 (a, b, c, d) ：如果 a & b ，那么数列保持原形不变，仍然是 (a, b, c, d) ；如果 a & b ，那么把数列变为 (c, d, b, a) ；如果 a = b ，那么把数列变为 (b, d, c, d) 。容易看出，集合 A 当中的每一个元素都会唯一地对应于集合 B 当中的某个合法的元素。举三个例子：&&&&&&(1, 2, 3, 4) & (1, 2, 3, 4)&&&&&&(2, 1, 3, 4) & (3, 4, 1, 2)&&&&&&(1, 1, 2, 4) & (1, 4, 2, 4)&&&&反过来，对于 B 当中的任意一个元素 (x, y, z, w) ：如果 y & w ，那么数列保持原形不变，仍然是 (x, y, z, w) ；如果 y & w ，那么把数列变为 (w, z, x, y) ；如果 y = w ，那么把数列变为 (x, x, z, w) 。容易看出，集合 B 当中的每一个元素都能变回为集合 A 当中的元素。因此，集合 A 和集合 B 里的元素确实是一样多的。
连分数的一个性质以及它的一个组合解释
你知道吗？连分数&&&&&&&&&&而连分数&&&&&&&&&&这两个连分数的分子竟然是相同的！这是为什么呢？《Proofs that Really Count》里面给出了一个有意思的组合学解释。
&&&&为了叙述方便，接下来我们统一用下图所示的符号来表示连分数：&&&&&&&&&&我们用 p(a1, a2, a3, &, an) 来表示 [a1, a2, a3, &, an] 的最简分数形式的分子，用 q(a1, a2, a3, &, an) 来表示 [a1, a2, a3, &, an] 的最简分数形式的分母。于是，我们有&&&&&&&&&&注意到，最后的那个分数已经是最简的了。如果不是的话，这就意味着 p(a2, a3, &, an) 和 a1&& p(a2, a3, &, an) + q(a2, a3, &, an) 之间有公共的因数，这进一步表明 p(a2, a3, &, an) 和 q(a2, a3, &, an) 之间必须要有公共的因数；然而 p(a2, a3, &, an) 和 q(a2, a3, &, an) 是 [a2, a3, &, an] 的最简分数形式的分子和分母，它们已经没有公共的因数了。&&&&因此，连分数的分母就应该满足&&&&&&q(a1, a2, a3, &, an) = p(a2, a3, &, an)&&&&而连分数的分子则应该满足&&&&&&&&&p(a1, a2, a3, &, an)&&&&&&= a1&& p(a2, a3, &, an) + q(a2, a3, &, an)&&&&&&= a1&& p(a2, a3, &, an) + p(a3, &, an)&&&&再结合初始条件 p(an) = an&以及 p(an-1, an) = an-1&& an&+ 1 ，我们就得到了连分数分子的一个完整的递推公式。接下来，我们要为这个递推公式赋予一个组合数学上的意义。考虑一个 n & 1 的棋盘，你可以在这个棋盘上放置一些 1 & 1 的砖块或者 2 & 1 的砖块。 1 & 1 的砖块可以叠放起来，但第 i 个位置上的砖块数目不能超过 ai； 2 & 1 的砖块则只能单独放置，它的上面和下面都不能有任何别的砖块。我们规定，棋盘的每个位置上都必须放有砖块，不允许出现任何空的位置。假如 n = 6 ，并且 a1&到 a6&的值依次是 3, 1, 4, 1, 5, 9 ，那么我们的棋盘就如左图所示，右图则是一个合法的砖块放置方案。&&&&&&&&&&&给定 n 的值以及序列 a1, a2, &, an&后，如何计算满足要求的砖块放置方案数呢？我们可以尝试着采用递推的办法。我们可以把所有的方案分为两大类。其中一个大类就是，第一个位置放有 1 到 a1&个 1 & 1 的砖块，这类方案的总数等于 a1&乘以在后面 n - 1 个位置放置砖块的方案数；另一个大类则是，第一个位置被一个 2 & 1 的砖块所覆盖，这类方案的总数就直接等于在后面 n - 2 个位置放置砖块的方案数。你会发现，这个组合问题的递推公式与刚才的 p(a1, a2, &, an) 完全一致，而且容易验证，只在第 n 个位置放砖块有 an&种方式，只在第 n - 1 和第 n 个位置放砖块则有 an-1&& an&+ 1 种方式，这也与 p(an) 和 p(an-1, an) 的值是相符的。因而， p(a1, a2, &, an) 的值正好就是在高度限制分别为 a1, a2, &, an&的棋盘上放置砖块的方案总数！&&&&回到本文最初的问题：为什么连分数 [a1, a2, a3, &, an] 和 [an, &, a3, a2, a1] 的分子是相同的呢？现在看来几乎是显然的：因为这两个连分数的分子表示的是两个左右镜像的棋盘的砖块放置方案数，而两个左右镜像的棋盘本质上是相同的，它们的砖块放置方案数显然应该相等。
趣题：免分割线的多米诺骨牌覆盖方案
& 问题：能否用多米诺骨牌既无重复又无遗漏地覆盖一个 6 & 6 的棋盘，使得棋盘上的每一条水平线和每一条竖直线都会穿过至少一个多米诺骨牌？举个例子，下图所示的棋盘覆盖方案就是不满足要求的，因为棋盘的第二条水平线不会切断任何一个多米诺骨牌。??&&&&&&
&&&&&&&&&&&&&满足要求的棋盘覆盖是不存在的。我们有一个非常漂亮的证明。注意到，任意一条水平线都会把整个棋盘分成上下两部分，这两部分所包含的小正方形的个数都是偶数。那些完全在这条线上面的多米诺骨牌会占据其中偶数个格子，那些完全在这条线下面的多米诺骨牌也会占据其中偶数个格子，因而棋盘的上下两部分各剩下了偶数个格子，这些格子就留给了那些穿过了这条水平线的多米诺骨牌来占据。每一个穿过了这条线的多米诺骨牌都会在上下两部分棋盘各占据一个格子，因此为了完全覆盖棋盘，这样的多米诺骨牌必须得有偶数个才行。结论就是：在一个满足要求的棋盘覆盖方案中，每条水平线都会穿过至少两个多米诺骨牌。同理，每条竖直线也都会穿过至少两个多米诺骨牌。然而，在 6 & 6 的棋盘中，水平线和竖直线一共有 10 条，每条线上都有两个多米诺骨牌，这显然是不现实的，因为整个棋盘里一共也只能放下 18 个多米诺骨牌。&&&&有趣的是，棋盘再稍微大一些，这种推理就失效了。在一个 8 & 8 的棋盘中，水平线和竖直线一共有 14 条，它们对应于 28 个多米诺骨牌，这却并不会导致矛盾，因为棋盘里一共能放下 32 个多米诺骨牌。那么， 8 & 8 的棋盘是否存在满足要求的覆盖方案呢？更一般地，对于哪些正整数 M 和 N ，在一个 M & N 的棋盘里存在满足要求的覆盖方案呢？注意， M 和 N 这两个数当中至少得有一个数是偶数，否则整个棋盘将会有奇数个小方格，这根本不可能被多米诺骨牌既无重复又无遗漏地覆盖住。&&&&不妨假设 M & N 。 M = 1 和 M = 2 的情况基本上可以直接被排除了（不过，这里面有一个特例，即 (M, N) = (1, 2) 可以算作是一个平凡解）。 M = 3 的情况基本上也可以直接被排除，但这可能不大容易看出来。假如一个棋盘只有 3 行，最左边那一列肯定不能全用横向的多米诺骨牌覆盖，否则将会立即产生一条通畅的竖直线，如左图所示。那么，最左边那一列肯定有一个纵向的多米诺骨牌，比如右图中的 1 号多米诺骨牌。于是，覆盖方案会被迫地向右图所示的方向发展，最终会不可避免地出现一条通畅的水平线。&&&&&&&&&&&&&&&&M = 4 的情况也能被排除。最左边的那一列不能全被横着的多米诺骨牌占据，也不能全被竖直的多米诺骨牌占据，剩下的本质不同的可能性就只有下面两种了，这最终都会被迫失败。&&&&&&&&&&&&&&&&接下来该研究的就是 M = 5 的情况。由于 M 、 N 都等于 5 的情况已经被我们排除了（ M 、 N 不能都是奇数），因此我们应该开始考虑 M = 5 并且 N = 6 的情况。这是第一次出现有解的情况：在 5 & 6 的棋盘上，满足要求的覆盖方案是存在的！下图就是其中一种方案，你可以考虑先自己想一会儿再查看答案：&&&&&&&&&&&令人意想不到的是，对于其他所有的情况，满足要求的覆盖方案都是存在的！也就是说，如果我们能用多米诺骨牌既无重复又无遗漏地覆盖 M & N 的棋盘，使得棋盘中的每一条水平线和竖直线都会穿过至少一个多米诺骨牌，则 M 和 N 必须而且只须同时满足下面这些条件：&&&&&&(1) M 和 N 至少有一个是偶数；&&&&&&(2) M 和 N 都大于 4 ；&&&&&&(3) M 和 N 不同时等于 6 。&&&&刚才，我们已经给出了 M 、 N 分别等于 5 和 6 时的方案。我们便能很快得出，只要 M 、 N 这两个数一个是奇数一个是偶数，满足要求的覆盖方案都是存在的。这是因为，对于任意一个合法的覆盖方案，我们都能按照下面的模式，把它扩展成一个新棋盘下的覆盖方案，使得棋盘的其中一条边的长度不变，另一条边的长度比原来增加 2 个单位。&&&&&&&&&&我们详细解说一下这种扩展模式吧。首先注意到，原覆盖方案的最后一列不可能都是用横向的多米诺骨牌覆盖的，也不可能都是用纵向的多米诺骨牌覆盖的（否则会立即产生一条通畅的竖直线）。因此，最后一列的多米诺骨牌一定是有横有竖的。把这些多米诺骨牌向右移动两个单位，然后用横向的多米诺骨牌填充由此所得的空白，就得到了一个新的方案。新方案的每条线为什么都穿过了至少一个多米诺骨牌呢？为了说明这一点，我们只需要考察新的棋盘中最后那几条竖直线即可。这很容易看出来&&刚才的那个&有横有竖&的结论可以保证这些竖直线都不会是畅通的。&&&&现在，估计大家已经看出来了，为了填上之前埋下的所有坑，我们只差最后一环了：在一个 6 & 8 的棋盘上设计一种满足要求的覆盖方案。这样一来，我们便能从 5 & 6 和 6 & 8 这两个基础布局出发，不断套用刚才的扩展模式，从而为所有应该有解的棋盘提供一个满足要求的解。给出一个 6 & 8 的布局并不容易，但也不算太难，你也可以考虑先想一想，再查看下图所示的答案：&&&&&&&&&&原问题是一道非常经典的问题了，经典的组合数学教材《Introductory Combinatorics》开篇就提过这个例子。后面的探讨则出自 Solomon Wolf Golomb 的《Polyominoes》一书。
趣题：Kontsevich的单人跳棋游戏
&&&&&&有一个无限大的棋盘，棋盘左下角有一个大小为 n 的阶梯形区域，其中最左下角的那个格子里有一枚棋子，如左图所示。你每次可以把一枚棋子&分裂&成两枚棋子，分别放在原位置的上边一格和右边一格。你的目的是通过有限次的操作，让整个阶梯里不再有任何棋子。下图所示的是 n = 2 时的一种解法。我们的问题是：对于那些 n ，这个游戏是有解的？&&&&&&
&&&&&&&&&&&&&&&&&当 n = 1 时，第一步直接就解了。刚才我们已经展示了 n = 2 时的解法。不可思议的是，对于其他所有的 n ，这个游戏都是无解的！下面我们就来证明这一点。&&&&&&&&&&像上图那样给棋盘中的格子赋值，这样的话，每一步操作都会把棋子从赋值为 x 的格子裂变到两个赋值为 x/2 的格子里，这不会改变所有棋子所在格子的数字之和。因此，所有棋子所在格子的数字之和就是一个不变量，这个值初始时是 1 ，今后则永远都是 1 。接下来，我们能立即得出，所有 n & 4 的情况都是无解的。容易看出第一行所有格子的数字之和是 2 ，第二行所有格子的数字之和是 1 ，接下来几行的数字之和则依次为 1/2, 1/4, 1/8, &，因而整个棋盘上的所有数字之和是 2 + 1 + 1/2 + 1/4 + 1/8 + & = 4 。然而，当 n = 4 时，阶梯区域里的所有数之和为 1 + (1/2) & 2 + (1/4) & 3 + (1/8) & 4 = 13/4 ，空白区域里的所有数之和仅为 4 - 13/4 = 3/4 。因此，我们不可能把所有棋子都移到空白区域里。当然，当 n & 4 时，空白区域里的数字之和会更小，把所有棋子都移到空白区域里就更不可能了。&&&&&&&&&&但是，上面的推理并不能直接适用于 n = 3 时的情况：所有空白区域的数字之和为 4 - 1 - (1/2) & 2 - (1/4) & 3 = 5/4 & 1 ，这么看上去，把所有棋子都移到空白区域似乎是有可能的。然而注意到，不管怎么操作，第一行都只有一枚棋子，第一列也只能有一枚棋子。考虑到这一点，空白区域里的数字之和似乎就又不够了。为了让棋局所对应的数值尽可能地大，最理想的情况便是，第一行的那个棋子正好位于标有 1/8 的格子里，第一列的那个棋子也位于标有 1/8 的格子里，此时第一行和第一列的其他格子都不能再有棋子了，因而我们还得从 5/4 当中减去两个 (1/16 + 1/32 + & ) ，结果等于 5/4 - (1/8) & 2 = 1 。另外，有限次操作不可能让棋子占满中间那片无限大的空白区域，因而棋局可以达到的数字之和严格地小于 1 。如果第一行的那个棋子更靠右，或者第一列的那个棋子更靠上，棋局可以达到的数字之和还会更小。因此，当 n = 3 时，游戏是保证无解的。&&&&上述游戏是由 Maxim Kontsevich 在 1981 年提出的。有一个类似的跳棋游戏叫做&，解决方法也是赋值法，并且更神奇的是，在赋值的过程当中竟然出现了黄金分割 φ 的身影！
热爱文学的你们。
大家好。很幸运 素履 审核通过了。支持我的人、怀有同样的情怀的人，可以通过微信订阅号&素履&或者&sulv_&关注。二维码也在下面。我已经推送了它的创刊号，对我来说就像一个初生的婴儿。第一份的排版可能不是很好，我会努力改进。希望大家多多支持，为了我们之间共同的理想。感谢大家。
16100人关注
16100人关注
站长在关注
说的太好了，我顶！
Copyright & 2014
Corporation, All Rights Reserved
Processed in 0.4651 second(s), 3 db_queries,
0 rpc_queries