称硬币问题、小白鼠找毒药问题与编码理论

本文要讨论的问题比较常见,但是好像很少有人从纠错码的角度给出解释。从纠错码的角度看问题的好处是可以很容易理解为什么要这样设计策略,而且能举一反三处理其它类似的问题。事实上我觉得这种趣味问题正是帮助初学者理解纠错码基本概念的绝好例子。

不过本文并不假定读者事先学过编码论,但是需要懂一点有限域的知识。

称硬币问题

问题:有 12 枚外表一模一样的硬币,其中一枚是假币,其余都是真币。假币的重量与真币不同,但是更重还是更轻不知道。给你一个没有砝码和刻度的天平,最少称几次才能确保找出假币?

相亲问题与倒向归纳法

问题:假设你是一位大龄男士,准备参加 100 场相亲 (别介意具体数字)。你打算依次与每个女士 \(i\) 约会,然后根据印象给她打一个分数 \(X_i\)\(X_i\) 的值介于 \([0,1]\) 之间。如果你对女士 \(i\) 很满意,那么就和她结婚,否则就放弃她,参加下一场相亲,当然拒绝了人家可就没有回头的机会了。如果你拒绝了前 99 位女士,那么不论第 100 次相亲结果如何你都只能和最后这位女士结婚。在相亲之前,你对这些女士的情况一无所知,所以姑且假定她们的分数 \(X_i\) 都是 \([0,1]\) 上均匀分布的独立的随机变量。问题是:应该采取怎样的相亲策略,才能娶到你最中意的女士?

三质点弹簧系统的简正模式

今天的问题是群表示论在物理中的一个小应用:

问题:平面上有三个质量均为 \(m\) 的质点 \(A,B,C\),它们位于一个正三角形的三个顶点处。质点之间两两由一根弹簧相连,三个弹簧都是一样的,但是弹簧质量忽略不计。

初始时所有质点都处于静止状态,弹簧之间没有张力。假设给这三个质点分别施加一个初始速度,使这三个质点在平面内作刚体运动,不考虑任何摩擦力和空气阻力。那么这个系统的简正模式 (normal mode) 是什么?

这里 简正模式 的含义是所有质点按照一个共同的频率和固定的相位关系相对于各自的平衡位置作简谐振动。

模式的等待时间与反直觉概率

著名概率学家 Feller 在他的名著 "An introduction to probability and its applications" 中提到了这样一个实验:

重复抛掷一枚均匀的硬币,用 H 代表正面向上,T 代表背面向上,一直到连续出现 6 次 H 为止。这里连续 6 个 组成的模式记作 HHHHHH,所需要抛掷硬币的次数叫做等待时间。等待时间是一个随机变量,最小值是 6,最大值可以是无限。Feller 问:等待时间的均值是多少?

这个问题可以用 Markov 链来解,但是非常繁琐。香港中文大学李硕彦教授在他的论文

A Martingale Approach to the Study of Occurrence of Sequence Patterns in Repeated Experiments.

中用离散鞅的知识给出了一个简洁而巧妙的解法,本文就来介绍他的方法。

洛奇绵羊问题

我们的问题源自中世纪威尔士人的故事集《Mabinogion》中的一段:

一个男孩来到了一个美丽的山谷,有一条小河在谷中流淌。他看到河一边的草地上有一群黑绵羊,另一边的草地上有一群白绵羊。羊群被施以一种魔法:每个时刻都恰有一只绵羊发出咩咩的叫声。如果发出叫声的是白绵羊,就会有一只黑绵羊趟过小河跑过来并且变成白绵羊;如果发出叫声的是黑绵羊,则会有一只白绵羊趟过小河跑过去并且变成黑绵羊。每个时刻发出叫声的绵羊是完全随机的,整个过程没有绵羊出生或者死亡,一直持续到所有绵羊都变成同一种颜色为止。

问题是这样的:

问题:如果男孩可以选择在初始时刻 \(0\),或者是每个魔法时刻 \(1,2,\ldots\) 结束后将任意数量的白绵羊赶出山谷,那么为了最终得到尽可能多的黑绵羊,他应该采取怎样的策略?

飞船空间跳跃问题

本文的问题出自 Williams 的教材 Probability with Martingales,虽然不算很难但是综合使用了许多知识,展示了抽象的鞅理论其实有着丰富多彩的应用。

问题:一艘太空船正在宇宙中做星际航行时,飞船的控制系统出了故障,飞船不能正常地进行空间跳跃,而是只能预先设定一个距离,然后以此距离进行一次方向完全随机的跳跃。现在飞船想要返回太阳系。假设太阳系的半径是 \(r\),发生故障时飞船与太阳的距离为 \(R>r\)。好消息是在每个时刻,飞船能够知道自身与太阳系的距离。

求证:不论采用怎样的跳跃策略,飞船返回太阳系的概率都小于 \(r/R\);但是对任何 \(\epsilon>0\),可以采取适当的策略,使得飞船返回太阳系的概率大于 \((r-\epsilon)/R\),即 \(r/R\) 是最优概率。这个最优策略是什么?

Schur 多项式,Littlewood-Richardson rule 与 Hook 长度公式

在数学中有那么一些问题,它们的表述简单而初等,但是解决起来却非常困难,往往需要相当的奇思妙想和深刻的工具,而且围绕这个问题许多不同领域的数学交织在一起,演绎出许多奇妙的故事来。

Young 表就是其中一个精彩的例子,组合数学,表示论,概率论在这里发生了奇妙的交汇。

我们先从一个有趣的问题开始:

问题\(n\) 位选民要在一次选举中给 \(m\) 个候选人投票,每个选民只能投一票。已知第 \(i\) 位候选人最终的得票数为 \(\lambda_i\),这里 \(\sum_{i=1}^m\lambda_i=n\)\(\lambda_1\geq\cdots\geq\lambda_m\)。问题是:有多少种不同的得票序列,使得在投票过程中的任一时刻,对任何的 \(i<j\),第 \(i\) 位候选人所得的票数总不少于第 \(j\) 位候选人所得的票数?

举个例子,假设有 \(n=10\) 位选民和 \(m=4\) 个候选人,则得票序列 \[1, 2, 1, 3, 2, 1, 2, 4, 3, 1\] 表示第一个选民投票给 1 号,第二个选民投票给 2 号,第三个选民投票给 1 号,第四个选民投票给 3 号,依次类推。符合问题要求的序列必须满足对任何 \(1\leq k\leq n\)\(1\leq i<j\leq m\),序列的前 \(k\) 项中数字 \(i\) 出现的次数都大于等于数字 \(j\) 出现的次数。

虽然问题的表述很简单,但其实答案相当复杂,绝非一般的初等方法所能解决。对付它的最好方法是 Schur 多项式的理论,我接下来就来介绍它。

线性代数杂题若干

二次型的惯性指数问题

我在研究生期间给学弟学妹们当高等代数课助教时,除了改改作业,讲讲习题,还经常需要出一些有点巧妙但又不太复杂的题目,帮助他们理解所学的内容。某一次我出了这样一道题:

问题:我们知道如果 \(A\) 是一个对称矩阵,\(T\) 是一个可逆矩阵,则 \(B=T'AT\) 也是对称矩阵且 \(A,B\) 合同 (congruent),所以它们有相同的正负惯性指数。如果 \(T\) 是不可逆矩阵呢?这时 \(A\)\(B\) 的正负惯性指数有怎样的关系?

当时班上无人能立刻给出答案。

其实这个题目不过是我把他们作业中的一道题改了改说法而已:

Artinian 环与 Wedderburn-Artin 定理

讲述 Wedderburn-Artin 定理的教材已经非常多了,在介绍群表示论或者非交换环的书里通常都可以找到,证明途径也大同小异。据我个人的体会,讲群表示论的书往往只介绍有限维群代数的情形,显得不太够用;而讲非交换环的书则喜欢从 Jacobson 根,密度定理讲起,念起来很让人劝退。我觉得 Artinian 环情形的 Wedderburn-Artin 定理还是非常有用的。我打算采用当年 Wedderburn 的思路展开叙述,即通过极大幂零理想来定义半单性。这种方式的好处是每一步的动机都比较自然,至少比上来就丢出一个 Jacobson 根的定义让人舒服一些。

关于中心单代数的三个基本结论

本文来自我在讨论班上的一个两小时左右的报告,目的是介绍中心单代数的三个最基本的结论:中心单代数对张量积运算是封闭的,Noether-Skolem 定理,双重中心化子定理。这部分内容比较古老,在很多教材上都有,但是采用的途径却很不一样,找一个完全符合自己口味的讲述不是件容易的事情。Jacobson 的书我念的就很抓狂。后来查阅了不少教材后经过提炼整理得到了本文,希望我的表述做到了清楚易懂。

 | 

当前网速较慢或者你使用的浏览器不支持博客特定功能,请尝试刷新或换用Chrome、Firefox等现代浏览器