Category: Mathematics

I am teaching MAT 412/512 Introduction to Combinatorics this semester. Earlier in the semester, I introduced the Stirling numbers of the second kind, and I did not find a good opportunity to introduce the Stirling numbers of the first kind until I started introducing permutation groups and group actions to build up to the Pólya… Continue reading On the Stirling numbers of the first kind

This article documents my presentation of Gromov’s theorem on groups of polynomial growth at the MIT combinatorics reading group. The presentation is based on Gromov’s 1981 paper, Groups of polynomial growth and expanding maps, Kleiner’s 2007 paper, A new proof of Gromov’s theorem on groups of polynomial growth, and Tao’s 2009 blog post, A finitary… Continue reading On Gromov’s theorem on groups of polynomial growth

One of the students in my class, Undergraduate Seminar on Discrete Mathematics, asks if the exchange property of a matroid can be strengthened to the following, of which I was completely unaware. Strong basis exchange property. For every pair of bases and , there exists such that both and are still bases. As it turns… Continue reading On the basis exchange property

Here is a problem from Week of Code 29 hosted by Hackerrank. Problem. Given two integers and (), find and print a common fraction such that and is minimal. If there are several fractions having minimal distance to , choose the one with the smallest denominator. Note that checking all possible denominators does not work… Continue reading Minimal Distance to Pi

Although using blackboard and chalk is the best option for a math talk for various reasons, sometimes due to limit on the time, one has to make slides to save time on writing. The most common tools to create slides nowadays are LaTeX and Beamer. When I was preparing for my talk at Vancouver for… Continue reading Alternative to Beamer for Math Presentation

Hausdorff moment problem asks for necessary and sufficient conditions that a given sequence with be the sequence of moments of a random variable supported on , i.e., for all . In 1921, Hausdorff showed that is such a moment sequence if and only if the sequence is completely monotonic, i.e., its difference sequences satisfy the… Continue reading A Short Proof for Hausdorff Moment Problem

接上次的日志，先重复一下谜题： 欺诈猜数游戏在甲和乙之间进行，甲和乙都知道正整数 和 。游戏开始时，甲先选定两个整数 和 ，其中 。甲告诉乙 的值，但对 守口如瓶。乙试图通过提问来获得与 相关的信息：每次提问，乙任选一个由若干正整数组成的集合（可以重复使用之前提问中使用过的集合），问甲“是否属于？”。乙可以提任意数量的问题。每次提问之后，甲立刻回答是或否，甲可以说谎话，但在任意连续 次回答中至少有一次回答是真话。 在乙问完所有想问的问题之后，乙必须指出一个至多包含 个正整数的集合 ，若 属于 ，则乙获胜；否则甲获胜。证明：对所有充分大的整数 ，存在整数 ，使得乙无法保证获胜。 为了解决第二个问题，需要从甲的角度考虑问题，每一次回答问题后，使得乙无法缩小 范围。 为此我们考虑贪心策略：甲每次在乙提出的集合和其补集中选择元素较多的那个集合。很明显这个策略有一个弱点：如果乙每次提问都问“ 是不是 呢？”那甲如果每次只顾眼前利益，应当回答“不是。”但经过 轮之后，甲就能轻松排除 ，从而缩小 的范围。 于是甲的策略必须是一种折中的策略，既要顾及眼前的利益，又不能放弃长期的利益。我们设定 。 于是甲在觉得到底要选择乙提出的集合或是其补集前，对 到 中每个数都进行打分。甲对 的打分是 ，其中 而 满足 在最近连续 次选择的集合中都不出现。根据每个元素的打分，甲在 和 中选择会使得之后整个集合总分较低的那个集合。 为了让证明成立，设定 。下面，我们通过归纳法证明每一次所有元素的总分不超过 。根据打分规则，最开始总分是 ，命题显然那成立。假设目前的总分是 ，乙给出集合 ，如果甲选 ，则总和变为 ，如果甲选 ，则总和变为 。由于甲会选择使得总和变得更小的那个策略，于是他回答后总和至多为 。由于 ，总和小于 。命题成立！ 如果 连续 次没有被甲选中，则其得分已经为… Continue reading 欺诈猜数游戏（下）