Category: Mathematics

Fun with Hex

According to the folklore, The Hex game was invented by the Danish mathematician Piet Hein, who introduced it in 1942 at the Niels Bohr Institute. It was independently re-invented in 1947 by the mathematician John Nash at Princeton University. The rules are really simple. Each player has an allocated color, Red and Blue being conventional.… Continue reading Fun with Hex

The ultimate prisoner puzzle

People like prisoner puzzles. Here is the hardest one I have ever seen. I heard it from Prof. Boris Bukh on the social hour of Maths Department couple of weeks ago, whom heard it on a maths conference. Since recently I am quite into Cryptography, especially setting up communication protocols, I would like to log… Continue reading The ultimate prisoner puzzle

欺诈猜数游戏（上）

上个月在新加坡的时候，正值国际生物奥林匹克竞赛在新加坡国立大学举行。于是不免想去看看 2012 年 IMO 竞赛的题目和各国比赛的结果。 理论上，国际数学奥林匹克竞赛是从来不进行国家排名的。但是，私底下……你懂的。 这次团体的第一名是韩国队思密达，个人总分第一名是新加坡的一位选手 Jeck Lim。这货四次代表新加坡国家队出战，金银铜满分四种情况都集齐了。中国队总分位列第二，中国队在个人排名最高的是 Yiyang She，位列第四。 言归正传，说说今年的题目。今年难度系数也是最有意思的题目当属第三题——欺诈猜数游戏。 广告插播：《欺诈者游戏》今年的剧场版换女主角了，我再也不相信爱情了。 下面是 2012 年 IMO 第三题： “欺诈猜数游戏”在两个玩家甲和乙之间进行， 游戏依赖于两个甲和乙都知道的正整数和。 游戏开始时甲先选定两个整数和，。甲如实告诉乙的值，但对守口如瓶。乙现在试图通过如下方式的提问来获得关于的信息：每次提问，乙任选一个由若干正整数组成的集合（可以重复使用之前提问中使用过的集合），问甲“是否属于？”。乙可以提任意数量的问题。在乙每次提问之后，甲必须对乙的提问立刻回答“是”或“否”，甲可以说谎话，并且说谎的次数没有限制，唯一的限制是甲在任意连续次回答中至少有一次回答是真话。 在乙问完所有想问的问题之后，乙必须指出一个至多包含n个正整数的集合，若属于，则乙获胜；否则甲获胜。证明： 若，则乙可保证获胜； 对所有充分大的整数，存在整数，使得乙无法保证获胜。 扯点题外话，虽然很多年没有做题了。但是此次再次拿起竞赛题思考的时候，发现心智已经成熟了不少，知道如何去细致地处理问题了。 回想高中的那段时间，无论是看竞赛书，还是出去上课，对于做不出的问题，大都是看了书上或是老师的解答之后，感叹解答之妙，但始终对解题动机这一说没有一个理解。 高中竞赛的训练使得我成为了一个熟练的工人，对于一般的问题，只需要将一般的工具试一遍就好了，而遇到非主流问题就一筹莫展了。所以如何提高对我来说一直是一个问题，现在看来，正是缺乏组合问题的训练，以及对待具体问题具体处理的能力。 但是，一旦脱离了那样的环境，反而能静下心去想问题，也能理解为什么说数学是人类心智的荣耀了。 那下面我要开始分析这个谜题了哦，如果想自己做题目的，就别继续看了哦。隆重推荐这道题目的另外一个原因是，做这个谜题的时候纯粹只需要在脑子里面想就可以了，还可以找个人一起玩这个游戏找找感觉。 第一步，将问题转化为等价的容易思考的形式，也就是说，需要回答这个问题：个回答中至少有一次回答是真话究竟意味着什么？ 每次乙提出一个问题“是否属于？”，如果甲回答“是”，那么我们说是可能属于的集合，反之，我们说的补集是可能属于的集合。为了简化，我们称这个集合为可能集。 那么，经过若干轮问答之后，我们得到一连串的可能集。连续个回答中至少有一次回答是真话就意味着：在这一连串的可能集中，任意连续的个可能集中必然有一个可能集真真切切地含了这个元素。也就是说包含于任意个连续可能集的并集。 第二步，从甲和乙的角度分别考虑取胜的策略。针对第一个小问，我们从乙的角度出发考虑问题。 作为乙的智囊团，我们需要向甲提出一系列为难的问题，使得将可能出现的范围不断缩小。不妨我们把注意力先集中在开始的个问题，我们的目标是使得对应的个可能集的并集最小。 不过多久，就能想到一种二分法的策略。 一开始，的出现范围是到中的所有数。那我们的第一个问题就是取出这个集合中一半数量的数问甲，是不是在这个集合中呢？无论甲如何回答，在第一轮问答过后，得到的可能集，记为，其大小最多就是。此处为了分析方便，我们暂时忽略各种取整的细节。 那如何设计第二轮的问题，才能使得两轮问答过后得到的可能集的并尽量小呢？ 啊哈！只需要将在以外的元素分出来一半作为第二次提问的集合就好了，这样无论甲此次如何选择可能集，记为，这两个集合并集的大小最多是。 这样，如此下去，每次我们都取出前面产生可能集以外元素的一半来质问甲就好了。经过论后，可能集并集的大小最多就是，于是通过之前的分析我们一定可以排除这个并集以外的元素了，也就是个元素了。 如果补回之前忽略的取整细节，你立即会发现，只要，那经过这样轮之后，一定能够排除至少一个数字，从而缩小的出现范围。 我们只要反复应用这个战术，每轮过后，只要的出现范围的大小大于等于，我们就能继续排除。 换句话说，我们总是能将的出现范围的大小缩小到以下。 但第一问的实质是让我们将这个范围的大小缩小到，所以我们的方法需要改进，但毫无疑问我们已经开了一个好头。 观察到在这样的策略下，甲的第一次回答应该尽量选择一个较大的可能集，如果甲选择了只有一个元素的可能集，那可大事不妙了。 那能否迫使甲选择只有一个元素的可能集呢？答案是简单的。 只需要一直问甲，是不是就可以了。如果甲连续轮都回答“不是”，那我们就成功排除了这个数。如果甲某次回答“是”，那接下来的个问题，我们如法炮制之前的二分法就可以成功排除个数。 综上所述，只要大于，那我们就能不断地排除一些数。于是当，乙有必胜策略！ 第二个子问题，请听下回分解。

Excerpt from Kunen

People living in cannot construct a which is -generic over . They may believe on faith that there exists a being to whom their universe, , is countable. Such a being will have a generic and an . The people in do not know what and are but they have names for them, and .… Continue reading Excerpt from Kunen

Mathematical Abbreviations

Here is a short list of mathematical abbreviations which troubled me the first time I graded students’ papers. You should be familiar with these words if you have used English as your first language in mathematics for years. But for students who has no experience of writing maths in English, this list might help. Abbreviation… Continue reading Mathematical Abbreviations

Published
Categorized as Mathematics

John 椭球

对于一个三角形，一定可以找到一个椭圆，满足，。对于一个平行四边形，一定可以找到一个椭圆，满足，。由于在仿射变换下三角形，平行四边形，椭圆，线段比例都保持，所以只需要对正三角形和正方形进行证明就可以了。 实际上，John 定理断言，每一个维凸体都有一个相应的椭球E满足，。对每一个中心对称凸体，都有一个相应的椭球满足，。 为了证明 John 定理，我们需要引入 John 椭球的概念，为此需要证明 John-Loewner 椭球定理：对于任意一个维空间中的含有内点的紧子集，存在唯一的椭球包含K，使得椭球体积达到最小，此时，称该椭球为 John 椭球。 证明（概要）：利用椭球与阶正定对称阵的联系，考虑所有包含 K 的椭球的中心和其对应的正定对称阵构成空间，证明函数在上取到最大值，存在性得证。如果在中有两个极大值点，可以通过这两个极大值点构造中的元素，使得在该元素上的取值更大（这里需要利用在上的凹性），由此导出矛盾，唯一性得证。 作为应用，我们考虑所有的的紧子群，令，其中是单位球，此时含有内点。于是是在任意中元素作用下稳定，如果是的 John 椭球，那么在任意中作用下也稳定（这是因为的紧致性保证了其任意元素的行列式为，于是明显包含，且体积与相等，由 John 椭球的唯一性知的稳定性），由此可知存在，使得对任意，有，，故，也就是说在相差一个共轭的程度上，正交群是极大的紧子群。

井田问题

向 Matrix67 致敬，我也来写点科普文章。 假期给初一、初二小孩讲几何课的时候，都提到了下面的命题：四边形中，依次是边上的两个三等分点，依次是边上两个三等分点，求证。 这道题目立即让我联想起了张景中院士的一本科普书，上课的时候我记不得这本书的名字了，后来回去搜索了一下，叫《新概念几何》。我的爸妈一般不给我买书（可能是因为买过两套四大名著我都不看的关系吧），记忆中他们还给我买过的书只有《十万个为什么（小学版）》和《新概念几何》了。 在《新概念几何》中提到过一个问题，叫做井田问题：传说从前的农民要分地的话，没有很精准的丈量工具，也不懂几何或是微积分，所以都采取一些近似的方法。有一天，村里的九户人家发现了一块四边形的田地，他们打算平分这块田。于是他们通过脚步丈量四条边后，将四边都三等分后，如下图将田分为了九块。 很明显，这块田地没有被九等分。但会不会像之前的“三分田地”问题一样，有类似的结论呢？很自然的一个猜测是最中间的土地面积是总面积的九分之一。其数学表述如下：四边形中，依次是边上的两个三等分点，依次是边上两个三等分点，依次是边上的两个三等分点，依次是边上两个三等分点，求证。 由于整个问题犹如在一块田中写一个井字，井田问题由此得来。 记得当时上课的时候，由于是即兴想到这个问题，双核同时运转，只顾着把故事编得生动一些，没腾出脑子去想解答，所以留下这个问题让小朋友自己回家思考了…… 实际上，建立在之前的三分田地的结论上，这个问题是很容易解决的： 由之前的结论，红色四边形的面积是整个面积的三分之一。假设我们能再证明和分别是的三等分点，那再次利用三分田地的结论，我们就能证明红黑相交的部分的面积是红色四边形的三分之一，也就是原四边形的九分之一了。 最后我们证明和确实分别是的三等分点，为此我们只证明是的三等分点。 为了能看得更清楚，我们考虑与需要证明的结论有关的部分。 由定比分点公式，我们有关于面积的等式： 于是，就证明了需要的结论。 通过类似的论证，读者还能将井田问题中的三等分替换为五等分、七等分甚至任意等分。进行类似的面积划分后，最中间那块的面积便是分之一了。

Published
Categorized as Mathematics

数学之路——对话恽之玮学长

恽之玮学长是北京大学数学科学学院 00 级的学生，后去 Princeton 读研，2009 年至 2010 年期间在高等研究所（Institute of Advanced Study）工作，目前在 MIT 就职，主要工作方向为几何表示论（Geometric Representation Theory）。 王志宇：学长是什么时候开始下决心做纯数学？ 恽之玮：是在高中和大学之间，参加完竞赛之后。我有一段时间不想做纯数学，也可能是题做多了有点厌烦，想念计算机或者其他的。后来碰到南大的一个老师，她跟我说纯数学还是很有意思的，越念下去越有意思。我进大学后就一直觉得纯数学很有趣，后来就没有动摇过。 王志宇：你们那届做纯数学的有多少人？ 恽之玮：现在还在做的大概有十个人或者更多。从之前和之后的比较来说这都是一个 local 的最大值，整体的不能说。 姜子麟：现在是否诱惑比较多，容易半途转行？ 恽之玮：你说是应用方面，嗯，这个一直有很多人，数学学院毕业的做这些的是大多数人。做金融，统计啊等等。我个人对这些不太感兴趣。 姜子麟：学长当年如果转向了计算机，现在的轨迹会是什么样的？ 恽之玮：我高中时候喜欢的那种计算机其实就是编程序，像现在的环境，清华有姚班，我也有可能去上。你们也知道那些竞赛题，有些组合跟计算机题挺像的，当时做的有点腻了，如果以我当时的状态，可能就不会选择进一步研究类似组合的问题。我觉得数学的好处在于，可能解问题时，最后还是要用一些组合的办法，但问题的方面更加广，像几何的数论的。同样的想法，可以有不同的包装。表面完全不同的问题，最后的想法又是相通的。 盛开：学长刚接触到大学课程的时候，对那些课程的感受是怎么样的？ 恽之玮：上大学之前，我买了一本拓扑的教材。当时看不懂，但我觉得他讲得很清楚。大一寒假里，我再翻一翻，越看越有意思，拓扑是吸引我的一个方面。还有一个就是 Galois 理论，当时老师也没有时间教，主要是自己看的。像 Galois 理论，它证明五次方程没有根式解，中学里就听过，但一直不知道是怎么证的。我一直对它挺感兴趣。我对群的概念比较感兴趣，这两个都涉及到群的概念。对我比较影响比较大的几门课，高峡老师当时给我们讲了“模形式”，这门课非常适合本科生，是一门很综合的学科。现在不用着急，今后肯定要学一学。它把拓扑，复变还有群论这些东西都综合在一起，学了之后你会发现，前面的东西你可能都没学懂，真正用的时候不会操作。 王志宇：学长在低年级的时候就学这些高级课程？ 恽之玮：我是在大三时候学的模形式。我听说你们现在越学越早，有些同学二年级就开始学代数几何。我前面两年对拓扑和微分几何感兴趣，后面才转向代数几何。我当时还参加讨论班，郑志明老师讲动力系统。高峡老师的讨论班不限定题目，可以读一个东西或者自己想点问题。当时陈维桓开了个研究生课程，是黎曼几何，我也去听了这个课。那个讲的更一般一些，相比本科的微分几何来说。其实研究生课程也不见得比本科的难多少，如果你把数学分析和代数学的比较好的话。 恽之玮：抽象代数其实应该早点学。依照我们的传统，比我更早学数学的人当中，学几何还有分析的比较多，学代数、数论、表示论这些都相对比较少一些。这可能就是因为我们代数学的时间比较靠后，而且讲的东西也不是很多。你们现在有抽代二，抽代二其实是研究生的课。如果把抽象代数一、二这两门都上下来，肯定比我们当时学得多。至少Galois理论，作为一个本科生，作为一个数学系的本科生，你一定得知道是怎么回事。相当于是数学在前一个世纪，也就是十九世纪最大的突破吧。学数学肯定得知道这个。 姜子麟：有时候会觉得学习代数有点枯燥，这方面学长怎么看？ 恽之玮：你们学抽象代数是吧。我当时学群的时候也觉得很抽象，证明的那些关于群的定理，都是很抽象也很一般的，那些论述对所有群都是成立的。其实学群不应该这么学，应该学个别的具体的群。而且不要光学群，要学习群在空间中的作用。群作用的概念现在是有的，但是你对于每一个群都要想一想它作用在什么上面。如果你凭空造出来一个群，不作用在任何东西上面，它是没有意义的。比如说学习 Galois 理论你就知道了，这个群作用在这个域上。如果群不作用在任何东西上，就没有存在的意义。 王志宇：学长能举一些更具体的例子吗？ 恽之玮：以前那个杨磊老师——现在不知道还开不开课，我们受他影响挺大的——他当时叫我们念 Klein 的《二十面体与五次方程》。那本书是二十世纪初翻译的，语言跟现在的有些不一样。但是它的内容都是很具体的、可以动手算的，我们当时做了个二十面体模型来看这里的对称群。它还可以被用来解某些五次方程；或者换句话说，五次方程不能用根式解，但是可以用椭圆函数解。相当于当时的数学基本上都能归纳到这本书里了。当时数学其实已经很丰富了，当时的比如模型式的理论，虽然不算很系统，但是模型式里的特殊函数、矩阵、线性变换群，还有 Riemann 曲面、常微分方程——你可以将里面的东西翻译成 Riemann 曲面的语言。这样书如果认真看的话可以学到很多东西。一般书讲的很抽象，上来看两页就不想看。但这本书不用当任务看，你可以当消遣看。能当消遣看的数学书不多。 恽之玮：我在 Princeton 的导师叫 MacPherson，是个拓扑学家，也做代数几何和表示论，但他拿手的是拓扑。当然他现在在考虑一些应用数学问题，也很有意思。我没有跟他学过这些东西，但是完全是纯数学里的想法，相当于开创了拓扑的一个新的方向。他告诉我，一定要注重例子。比如说找几个曲线、曲面作为例子来算；定理成立与否的条件，这个条件是否必要也，可以举个例子。这一方面帮助你理解一般性的定理：有些时候通过分析一个例子你可以就知道一般性的问题该怎么做了；另一方面在今后做研究的时候，很多研究中的问题都来源于例子，而不是抽象的理论。最终的研究成品可能是一个推广了的、发展了的理论，是一套抽象的东西，但其实研究者的出发点肯定不是这样的。有一个具体的问题或具体的例子，原来的工具不够用了，从而迫使他来发现、来改进别人的结果，于是新发展了一套工具，而不是为了发展这个而发展。一定要以例子为中心。也有个别不看例子的，像 Grothendieck，他是代数几何的一代宗师。这种人毕竟是少数，他的逻辑思维的能力太强了，很少能有人能达到这个程度。其他的数学家，虽然写的有些东西很抽象，但他的想法，如果你跟他交谈或者是了解他私下里怎么思考，其实都是例子。 姜子麟：那怎么能挑选一个比较好的问题作为自己的入手？ 恽之玮：其实我这方面也不算成功，我刚开始做本科生科研，跟着姜伯驹老师和王诗宬老师，最后什么都没有写出来，我也是不好意思的。其实本科生科研里有很多很具体的东西，上手并不难，是可以操作操作的。但是我自己没有找到什么比较好的问题。 王志宇：您当时是跟那两位老师做什么方面的？ 恽之玮：姜伯驹老师让我读一些关于辫群的东西。那是很有意思的东西，我现在还很感兴趣，和纽结理论有一些关系，里面又有一些代数的操作，你可以具体地去算。但是我最后也没做出什么东西来。王诗宬老师当时开了一门课叫几何群论，几何群论的主要观点就是把每一个群都看成空间的基本群，换句话说就是把群作用在一个拓扑空间上。把每一个用几何的观点来看，然后推导出一些纯粹关于群的一些性质，也就是代数的性质。但是用几何的观点去看，你就看得自然一些。这个也是很有意思的一个学问，但是我的主要的经历还是放在学上面了。其实本科生搞科研可能还是早了点，当时我也没有找到什么合适的问题。… Continue reading 数学之路——对话恽之玮学长