接上次的日志，先重复一下谜题： 欺诈猜数游戏在甲和乙之间进行，甲和乙都知道正整数 和 。游戏开始时，甲先选定两个整数 和 ，其中 。甲告诉乙 的值，但对 守口如瓶。乙试图通过提问来获得与 相关的信息：每次提问，乙任选一个由若干正整数组成的集合（可以重复使用之前提问中使用过的集合），问甲“是否属于？”。乙可以提任意数量的问题。每次提问之后，甲立刻回答是或否，甲可以说谎话，但在任意连续 次回答中至少有一次回答是真话。 在乙问完所有想问的问题之后，乙必须指出一个至多包含 个正整数的集合 ，若 属于 ，则乙获胜；否则甲获胜。证明：对所有充分大的整数 ，存在整数 ，使得乙无法保证获胜。 为了解决第二个问题，需要从甲的角度考虑问题，每一次回答问题后，使得乙无法缩小 范围。 为此我们考虑贪心策略：甲每次在乙提出的集合和其补集中选择元素较多的那个集合。很明显这个策略有一个弱点：如果乙每次提问都问“ 是不是 呢？”那甲如果每次只顾眼前利益，应当回答“不是。”但经过 轮之后，甲就能轻松排除 ，从而缩小 的范围。 于是甲的策略必须是一种折中的策略，既要顾及眼前的利益，又不能放弃长期的利益。我们设定 。 于是甲在觉得到底要选择乙提出的集合或是其补集前，对 到 中每个数都进行打分。甲对 的打分是 ，其中 而 满足 在最近连续 次选择的集合中都不出现。根据每个元素的打分，甲在 和 中选择会使得之后整个集合总分较低的那个集合。 为了让证明成立，设定 。下面，我们通过归纳法证明每一次所有元素的总分不超过 。根据打分规则，最开始总分是 ，命题显然那成立。假设目前的总分是 ，乙给出集合 ，如果甲选 ，则总和变为 ，如果甲选 ，则总和变为 。由于甲会选择使得总和变得更小的那个策略，于是他回答后总和至多为 。由于 ，总和小于 。命题成立！ 如果 连续 次没有被甲选中，则其得分已经为… Continue reading 欺诈猜数游戏（下）
An Upper Bound on Stirling Number of the Second Kind
We shall show an upper bound on the Stirling number of the second kind, a byproduct of a homework exercise of Probabilistic Combinatorics offered by Prof. Tom Bohman. Definition. A Stirling number of the second kind (or Stirling partition number) is the number of ways to partition a set of objects into non-empty subsets and… Continue reading An Upper Bound on Stirling Number of the Second Kind
A Probabilistic Proof of Isoperimetric Inequality
This note is based on Nicolas Garcia Trillos’ talk, Some Problems and Techniques in Geometric Probability, at Carnegie Mellon University on January 29, 2015. In particular, we demonstrate a probabilistic proof of the isoperimetric inequality. The proof can also be found in Integral Geometry and Geometric Probability by Luis A. Santaló. Theorem. For a convex set… Continue reading A Probabilistic Proof of Isoperimetric Inequality
On Extension of Rationals
This note is based on my talk An Expedition to the World of -adic Numbers at Carnegie Mellon University on January 15, 2014. Construction from Cauchy Sequences A standard approach to construct the real numbers from the rational numbers is a procedure called completion, which forces all Cauchy sequences in a metric space by adding… Continue reading On Extension of Rationals
Poisson Summation Formula and Basel Problem
This note is based on Professor Noam Elkies’ talk at Carnegie Mellon University on December 2, 2014. A classical mathematical analysis problem, also known as the Basel problem, first posed by Pietro Mengoli in 1644 and solved by Leonhard Euler in 1735, asks the precise sum in closed form of the infinite series Here we… Continue reading Poisson Summation Formula and Basel Problem
A Note on Thue's Method
This note is based on my talk Introduction to Diophantine Approximation at Carnegie Mellon University on November 4, 2014. Due to limit of time, details of Thue’s method were not fully presented in the talk. The note is supposed to serve as a complement to that talk. Diophantine Approximation Diophantine approximation deals with the approximation… Continue reading A Note on Thue's Method
美国数学奥林匹克观察（下）
接上篇。因为实在有太多东西可以写，所以犹豫了很久是不是要分中篇和下篇。想想还是挑重点一气说完。 除了在 MOP 第三周举行的为时两天的 TSTST 以外，在前两周还有四次 MOP 测试和两次 IMO 模拟考试。这六次考试都是不关联来年的集训队选拔的。但这六次考试很有趣的是，阅卷员（大多数是过去参加过 IMO 的学生）会对解答主观地作出风格分的评判。比如，如果你的解答是一通暴算，那很抱歉，你的风格分可能会很低。为了鼓励第一次的参加的学员，特别是在红组和绿组的学员，他们的四次 MOP 测试会在原有的三个题目上附加两个简单的题目。 为了增进学生互相之间的合作，在前两周还有三个学生一组组队赛。红组和绿组用一套稍简单的题，蓝组和黑组用稍难的一套题。评分的方式是在阅卷员面前解释自己的解答。换句话说，在这个过程中，学生不但要解决问题，还要教会组里不会的伙伴。这正好也呼应了 Jane Street 讲座里所说的工作中的团队合作。 除了之前说的几个考试测验外，整个项目里还有一个广受同学欢迎的叫做 ELMO 的竞赛。ELMO 具体是什么意思不得而知，但每年这个名字都会有新的诠释。比如今年 ELMO 代表 Ego Loss (surely) Must Occur，意思就是损伤自尊心必然发生。这个竞赛由老生（Veteran，也就是至少是第二次参加 MOP 的学员）运作，模拟 IMO 的模式：老生提供试题，构成备选试题列表（ELMO Shortlist），新生（Rookie，第一次参加 MOP 的学员）组队，老生被分配到每队成为领队，新生参加比赛后由老生阅卷并互相之间协调分数。 虽然这个活动仅仅是一个由学生运行的比赛，但是每年他们都会像模像样地把试题和备选试题发到上篇提到的 Art of Problem Solving 的网站，不知道内情的人，乍一看肯定会觉得这是一个由某机构运作的官方的比赛。学生们拍照的时候不会说Cheese（茄子），而会喊 ELMO Meeting!（ELMO 会议），可见这个比赛的受欢迎程度。 除了这个 ELMO 竞赛外，另外有一件事情彻底颠覆了我之前对美国高中数学教育的刻板印象。有一天，教练和阅卷员开完会，回到寝室楼大厅，看到了这番情景。 为了说清楚这个比赛，简单讲一下美国的一个为初中生设计的竞赛 MathCounts。这个比赛类似于中国的华罗庚数学金杯赛，最后一轮是抢答赛（Countdown Round），也是该项比赛唯一的口试部分，用于决定每年的冠军。而照片里所看到的是高中生版本的 MathCounts，大家管它叫平板支撑抢答赛（Plank Countdown），因为比赛选手需要在抢答的过程中一直平板支撑。出乎我意料的是，孩子们的心算速度非常快。决赛轮，两个选手大多数时候都能在题目刚念完未念完的时候给出答案。 孩子们在不断创新的同时，整个教练组也尽力会去优化整个项目的体验。比如 Po-Shen… Continue reading 美国数学奥林匹克观察（下）
美国数学奥林匹克观察（上）
上个学期，不时会在午后太阳将下山前，在卡内基梅隆大学附近的山坡上小跑。有一次小跑归来，进入 Doherty 楼的时候，遇到了 Po-Shen Loh。我之前就听说 Po-Shen 是美国国际数学奥林匹克（下简称 IMO）队的副领队。Po-Shen 当时推着自行车，突然问我，你想不想今年暑假辅导美国 IMO 集训队。我回答说我非常乐意，但因为没有碰竞赛好多年，水平肯定不行了，但！是！平面几何肯定是可以保证质量的。于是，我就这么来到了内布拉斯加的首府林肯。 说到内布拉斯加，大多数美国人的反应是不毛之地（in the middle of no where），喜欢看生活大爆炸的同学肯定会说是 Penny 的老家。但林肯毕竟是首府，集训队住宿和上课的地方在内布拉斯加大学林肯分校。美国大学在校园建筑方面向来奢华，集训队所住的地方更是学校里历史最悠久的宿舍楼，条件可以说是非常舒适。 这个暑期项目的官方名字是 Maths Olympiad Summer Program，缩写就是 MOSP，但是大家喜欢管它叫 MOP，直译过来就是拖把，参加这个活动的学生也就自然被称之为了 Mopper，直译过来就是拖地的人。根据 Mopper 们在之前一年中各个竞赛的综合表现被分为黑组（十人）、蓝组（十五人）、绿组（十五人）和红组（十一人）。黑组的十个成员中包括了即将参加今年在非洲开普敦举行的 IMO 正式队员。 MOP 正式开始是从六月九日，在这之前还有给黑组成员的小灶 Pre-MOP。为了备课，我的母亲从上海帮我翻拍了很多以前的笔记和数学日志，精选了一百来个题目，花了不少时间把每一个题目都做了一遍，并翻译成英文写了解答。 即便如此备战，第一天试水还是被黑组的学生震撼到了。具体过程是这样的，由于种种原因，我没办法复印讲义，于是只能把题目抄到黑板上。我抄了五六个题到黑板上，心想，少年们，受苦吧！但离下课还有一会的时候，学生当中有一个叫 James Tao 问我有没有更多的问题，于是我又得往黑板上抄了两三个题目才稳住了局面。 第一次上课我还给他们讲了一些射影几何的定理。后来我发现这完全是多余的，可以假设黑组的学生什么都知道，只要挑选好的问题给他们即可。第二次上课采用这个策略就明显从容很多了。 Pre-MOP 很快就过去了。六月九日大批的蓝绿红组的学生到来，看面孔大多数都是华裔，不知道这算是人种优势，还是华人家长比较在数学教育。于是我问 James Tao 他是如何走上奥林匹克数学道路的。他说，一方面，是他父亲的辅导，小时候拿着一本中文的几何书翻译着将给他听。另一方面，他发现了 Art of Problem Solving 这个网站和一本叫 Problems from the Book 的书。我个人的看法是，华人家长会更有意识培养和挖掘孩子数学能力。 六月十日的晚上有一个简短的会，面向所有的… Continue reading 美国数学奥林匹克观察（上）
How I wrote my first independent paper
This is what happened behind the scene. In the first draft, I was very pedantic. The resulted draft is notation-heavy and has no introductory section. It was then totally discarded. However, the structure of the proof was reused in the later drafts. My advisor suggested a useful dictionary by Trzeciak for mathematicians like me who… Continue reading How I wrote my first independent paper
Fun with Hex (Cont.)
In the previous post Fun with Hex, I asserted without proof that the Hex Game will never result a draw. In Jiri Matousek’s An Invitation to Discrete Mathematics, I found an elegant proof for the assertion, which requires only a little bit of elementary graph theory. The idea of the proof can also prove Sperner’s… Continue reading Fun with Hex (Cont.)