不求甚解学经济-不动点定理（一）斯拜纳引理 Sperner's Lemma

这一部分是Sperner引理。沿“Sperner引理→KKM引理→Brouwer定理→Kakutani定理”的推进思路目前是诸多证明拓扑不动点定理的思路中最易懂的一种。

一些概念

1.仿射无关：如果$X_{0},...,X_{m}​$为线性无关，则$X_{1}-X_{0},...,X_{m}-X_{0}​$便是仿射无关的。（亦可仿照线性无关来定义仿射无关，即若任何一组标量$a_{0},...,a_{n}​$，在满足不全为0但​$\sum_{i=0}^{n}a_{i}=0​$的条件下，都无法使得​$\sum_{i=0}^{n}a_{i}X_{i}=0​$，则称这组向量​$X_{0},...,X_{n}​$为仿射无关的。）

2.单纯形：n维单纯形就是n+1个仿射无关点的凸包，记为$S=co\lbrace X_{0},...,X_{n} \rbrace$，意即Simplex。单纯形可以定义为开集，然后于其上定义闭单纯形，而闭单纯形是最简单的非空紧凸集。或者可以直接将其定义为$n+1$个仿射无关点的闭凸包，$S=cl(co\lbrace X_{0},...,X_{n} \rbrace)$。我们将采用第二种定义方式。

3.单位单纯形，记为$\Delta$，单位单纯形凸组合的各系数在0与1之间，加总和为1。比如2维单纯形，就是3个点的凸组合，表现为一个三角形，这3个点就是三角形的3个顶点。（而单纯形因其性质，可以作为在博弈论中混合策略的理解方式，各坐标之和为1也就是各种情况下的概率之和为1。）

4.标号：将$n$维单纯形的$n+1$个顶点赋以标号，如$0,1,…,n$或$1,2,…,n+1$，各顶点的标号互不相同。

5.简单剖分：将$n$维单纯形划分为一大堆小$n$维单纯形。简单剖分有两种，分别为重心剖分与等距剖分。剖分里面的小单纯形之间要么共点，要么碰不上，要么共面。剖多细致无所谓。对于Sperner引理所要求的来说，这两种都是可以的。我们约定，原先的单纯形称为母单纯形，而剖分之后得出的小单纯形称为子单纯形。

6.好标号：母单纯形各边上的子单纯形节点不能使用对面顶点上的数字，但使用两端中的哪个无所谓。比如三角形三顶点标为$0,1,2$，那么$0,1$那条边上可以有$0$或者$1$，但不能用该变正对面那点上的$2$。而母单纯形内部的子单纯形怎么标无所谓，比如三角形内部随意选择$0,1,2$。

7.好子形：如果原先单纯形内部有个剖出来的小单纯形，其各顶点恰好使用了所有标号，不重不漏。那这个小单纯形就是好子形。

Sperner引理

Sperner引理：不管怎么剖分，内部一定存在奇数个好子形。

证明

可用递推法。$n=1$时的结论是证明$n=2$时的条件，以此类推。

$n=1$时，1维单纯形，就是两个点的凸组合，即一条线段。标号为一端点为$0$，另一端点为$1$。
剖分就是把线段为成几小节，小节的标号可以从两端点的标号任意选。比如算上端点可以依次为$0,0,1,0,1,0,1,0,0,1$，而且前面说过剖多细致无所谓，所以$0,1,0,0,0,0,1,1,1,0,0,1,1,0,1$什么的也行。不过必须遵守两端点标号是不同的，即一边为$0$，另一边为$1$。
记$F(0,0)$为两端都是$0$的小节的个数，$F(0,1)$为一边为$0$而另一边为$1$的小节的个数，具体哪边是$0$哪边是$1$无所谓。（这时候要算只能算剖分之后的，不能把长的和内部细分之后的都算在一起。举个不恰当的例子（因为这个例子有数值），一个两厘米的线段，如果剖成两节，一厘米一节，那么就只能按两条小线段算。不能把剖之前的和剖之后的加在一起成了三条线段。）$F(0,0)$和$F(0,1)$都是小节的个数，下面再看标号的个数。每个满足$F(0,0)$的小节都贡献了两个$0$，每个满足$F(0,1)$的小节都贡献了一个0，但是有一个问题，在算$F(0,0)$和$F(0,1)$时，我们把除了最原始端点之外的0都算了两次，为了把全部的点都算两次，还得加1。因此$2\times F(0,0)+F(0,1)+1$等于线段上所有$0$的个数的二倍。而$2\times F(0,0)$当然为偶数，所有0个数的二倍为偶数，1为奇数，因此$F(0,1)$必为奇数。所以得证。

$n=2$时，三角形。母单纯形三个顶点标号为$0,1,2$。把小单纯形中三个顶点为$(0,1,1)$或者$(0,0,1)$的个数设为A，把好子形个数设为$G$，$n=1$时我们算的是$0$的个数（当然其实算1也一样），这里$n=2$我们算边为$(0,1)$的个数（当然算$(1,2)$或者$(0,2)$也一样）。每个A贡献了两个$(0,1)$的边，每个$G$贡献了一个这样的边。$A$和$G$都是子单纯形。我们再来算边，上述方法里，每条内部端点为$(0,1)$的小边算了两次，内部$(0,1)$边设为$B$，每条边界端点为$(0,1)$的小边算了一次，边界$(0,1)$边设为$C$。因此2A+G=2B+C。而我们在$n=1$时已经知道了$C$是奇数，所以$G$也是奇数，得证。

同理，往下递推。可有$n$维情形。$\square$