Domain 靈質空間

虽然也许只是心理暗示，但我总觉得自己和喜欢的棋手之间冥冥之中有着联系。这不是没有证据的。2023 年的四月底，丁立人¹成为了世界冠军，我则收到了清华的录取。我想我们二人都很难否认，我们没有足够强，却在恰当的时机被幸运眷顾。一位高中同学当时这样评价我：

天赋很高，但没有那么高；学习很刻苦，但没有那么刻苦。

Nepo 伸出手认输的那一刻，丁的脸上并没有笑容，他似乎很困惑，他把脸埋在手里，躲闪着摄像机。所有人都在庆祝；正如所有人也在祝贺我。然而我想，我们二人都心知肚明，这并不是所向披靡的冠军领取早已属于他的荣誉的故事，这甚至算不上「成功」。初中时一位英语老师说，vocabulary.com 上 success 一词的释义非常值得看，那里如今写着：

For some students, success in school means getting As and Bs. For others, it means getting straight As, starring in the school play, and winning the class election. Success means achieving a goal, and everyone’s goals are different.

然而我们二人的生活真切地改变了；这种改变其实很好概括，一言以蔽之，我们都厌倦战斗了。丁立人一年都没有怎么比赛，在一年后的世界冠军赛上，输掉了一个荒唐的王兵残局——一位比笔者的年龄还小的棋手就此成为世界冠军。我则成为了一个人群中过于普通的学生，我埋头学着复分析，随即又忘掉；学着身边人的样子，说着那些意义不明的 Yau² 笑话：「不求上进，自甘中下」。不当一流棋手算自甘中下吗，我不知道；不在本科中稿几篇顶会论文呢？

从优绩中逃脱，又掉进反优绩的陷阱。人们说，实习像滚雪球，大一大二进小厂，大三大四进中厂，毕业了便可以进大厂。人们说，特定的年纪干特定的事情，以至于由于我忘掉了复分析，我便错过了做纯数学的唯一机会，我只好在那些十八岁读博的同学面前自惭形秽，不再拥有花好几个下午看代数的权利，而是必须得攒论文。事实上，什么都像滚雪球，什么差距都越拉越大。不过我很庆幸，这种焦虑已经是过去的事情了，我想我终于找到了一点平衡；就像如今我早已不怕输棋了。

上大学以来，我就几乎没有错过任何一场国际象棋赛事的直播。十几分钟才走一步棋的节奏，特别适合作为赶 DDL 的背景音。在昨天的候选人赛中，中村光把一个该赢的车兵残局走和了，三和一负；Sindarov 则三胜一和，创下了候选人赛前四轮史无前例的战绩。亲爱的村主播在复盘视频里的懊恼显而易见：

他引用了棒球选手 Yogi Berra 的一句话：

It’s getting late early.

正如我快要二十岁了。我常开玩笑和朋友说，「男人过了二十就是六十」。我当然不至于很认真地这么认为，然而我对于二十岁这个数字的焦虑也是真实的。跑三千米的时候，我很爱做的一件事情是不停计算已经跑完的路程所占据的比例：一圈是十五分之二，两圈半是三分之一；跑至半程的时候，就安慰自己说，把刚刚已做的再做一遍就好了。令我很恐惧的是，我甚至无从得知，二十岁究竟是四分之一、三分之一或二分之一。

世界的规则在我的周身扭曲又重塑。我想到一个很好的比喻，却缺乏精巧的语言，只好费劲描述给读者：我们身处物理世界，正如棋手坐在棋盘边——规则写在那里，下一步的全部变化，无非原子运动的推演，或穷尽棋步的搜索——而我们仍然举棋不定，只因我们的无知。最好的招法存在，我们无法比它做得更好；我们毕生所求，只是尽力不要显得太蠢。

Chess is the struggle against the error.

真的落下了太多吗？我可以二十岁开始学数学、二十岁下棋输给九岁小孩、二十岁仍旧对社会一无所知吗？我可以为重新推导出别人在十八世纪写下的结果欢欣鼓舞吗，当成自己的成功吗？一定要前不见古人、后不见来者，才能不让自己显得可悲吗？

前几天受系里委托，从同辈中间征集给 2026 级新生的、来自学长的寄语。问到一个我很佩服的同学，他发给我长长一段话，意思是要拒绝，理由大概是自己并不够强；他问，「xxx（另一个同学）有发表在 xxx 上的论文，是否由他来撰写更合适呢？」

这位同学旋即撤回了那一段长长的话，简单地回复道：「没问题，很高兴被邀请。」

We tend to think of success as a triumph or victory, but if you look at its linguistic roots in Latin, success literally just means “result.” At some point several centuries ago people probably began using success as shorthand for “good success,” and eventually they dropped the good altogether. That would explain why in formal settings you still occasionally hear the phrase “good success,” even though we now think of all successes as good.

也许人的寿命不是按时间划定的，而是按照生病的次数划定的；也许永远不生病，人也就永生了。可是有谁是那样的呢？我们并不生活在无菌舱里，我们要奔跑的时候跌断骨头，要熬夜熬出肝伤；要吃那么辣的火锅，并且蘸蒜泥和香油，然后吃出胃肠炎，从剩余生病的机会里折去一次。某一次之后，我们死去。

倘若真能得以放纵也好了。遗憾的是，我这次似乎什么也没有做错：我吃着食堂的出品，看不出一丝不干净的地方；我开春了还穿着羽绒服，戴着口罩和护目镜；我甚至久违地在午夜之前睡了觉。然而我还是得了胃肠炎，我发烧又腹泻，我还冷。

小的时候，我有一套古诗古文和现代散文的光碟，我那典型的江浙沪母亲让我在上学的路上反复地听。我竟然很不反感这件事。那光碟配有一本文字，就成为我主要的背诵材料，我小学有段时间沉迷背诵《桃花源记》《长恨歌》，凭此骗取了语文老师的厚爱。散文的部分，则成为我的作文素材；冰心的《往事》里有这样一段：

我倚枕百般回肠凝想，忽然一念回转，黯然神伤……今夜的青山只宜于这些女孩子，这些病中倚枕看月的女孩子！ …… 往者如观流水——月下的乡魂旅思：或在罗马故宫，颓垣废柱之旁；或在万里长城，缺堞断阶之上；或在约旦河边，或在麦加城里；或超渡莱因河，或飞越落玑山；有多少魂销目断 ，是耶非耶？只她知道！来者如仰高山——久久的徘徊在困弱道途之上，也许明日，也许今年，就揭卸病的细网，轻轻的试叩死的铁门！天国泥犁，任她幻拟：是泛入七宝莲池？是参谒白玉帝座？是欢悦？是惊怯？有天上的重逢，有人间的留恋，有未成而可成的事功，有将实而仍虚的愿望；岂但为我？牵及众生，大哉生命！

如今重读，我无颜承认这就是我当年竭力模仿的文字；不过读者大概容易明白，为什么这样的文字会吸引一个四五年级而自以为是的小孩。不过，我虽不是女孩子，我的病枕也见不到月亮，我想，我确有些将实而仍虚的愿望。

好不容易生病了，当然可以名正言顺地不干正事；掏出来好久不碰的西班牙语，学不进去；只好掏出小红书。是的，生病了，我甚至敢于放肆地「用互联网烂梗麻痹精神」。我以前是看 B 站的，觉得太浪费时间卸载了；于是改看小红书，成功戒掉了 B 站。看了一下午 Steven He¹，心想他长得好像搞优化理论的老师。刚刚睡不着，发烧到 38.6，只好下床接着看小红书。刷到有人问「如何低调地晒顶奢酒店」，于是女人们晒酒店，男人们晒有着女人痕迹的酒店。「这很糟糕」，我当即想道。然而我很喜欢酒店高级的早餐（虽然我也没住过多高级的），光松饼就有五六种，第一次让我知道了牛奶还有全脂和脱脂的区别，也让我明白奶酪并不像猫和老鼠里那样香甜。不要提吃不完的培根、烤香肠、小蛋糕和巧克力喷泉。「妈的，」我心想，「看来我也很想住顶奢酒店。」我很想住顶奢酒店吗？我不知道，但我承认你把那些图片摆在我眼前的时候，我被诱惑到了——尤其是在病中。

尤其是在病中，我才终于重新提笔——为此我不胜惭愧。搞艺术的可以接着酒劲或药劲创作，我终究搞不来，但是借着烧糊涂了总是可以的。

刚刚似乎还有什么要写的，这会儿已全忘记了，那么随便写一点杂谈。今天一个人去校医院的时候，那护士抽血时忽然叫我再说一遍自己的名字，我问，「这是为了让我不要紧张吗」，她没忍住噗嗤笑了，我对此很得意。又想起来一桩往事，初中的时候也是肠胃炎，那次要严重得多，第二天则是升学考试的口试，两人一组，和我组队的女同学急的要死；最后考试去考了，倒是离开了那所学校。想一想这竟然已是五年前的事情了。

我发觉，我如今写作时总忍不住将自己荒唐的一面暴露出来。不知道究竟是思维长进了、不矫揉造作了，还是灵魂里没有什么东西、只剩下糟粕了。我不是冰心，相比之下，我的往事单纯得多了。我的前十八年就像 Steven He，也许不是父亲给我施加的压力，也有自我的苛求，这种惯性如此根深蒂固，以至于我快要二十岁了，我依然后悔六岁时没有好好学钢琴。同学有人刚刚开发了一款 dating 软件，「好荒唐」，我想；然而活了二十年，我似乎也没有在这个世上留下什么痕迹，连一款 dating app 都没有。我上着很好的学校，期待着那未成而可成的事功，仅此而已。我隐约相信，我能自己挣到钱去吃大酒店的早餐。

发烧会让我明白更多事情吗？我怀念真正的清醒。

万能的上帝，我诚何福？我又何辜？

为了纪念 mer 第一次做出三题，Ziri 决定为此次 Codeforces Round 写题解，顺便回忆青春。

A. Passing The Ball

题面. 给定一个由 L 和 R 组成的字符串，开头和结尾分别一定是 L 和 R。从第一个人开始传球，当前持球人如果是 L 就往左传，否则往右传。求有多少人可以拿到球。

题解. 签到题。观察到答案是第一个 L 的序号，因为球不可能传给 L 右边的人。

B. Right Maximum

题面. 给定一个整数序列，每步找到其中最大元素（如有多个则取最右边的），删去它及其右边所有数。求序列变空需要的步数。

题解. 观察到如下事实：若一个数左侧的数都不大于它，则一定存在某一步选中的数是它；同时，若一个数左侧存在大于它的数，则该数的存在不影响答案（因为它会被左侧的这个数一同删去）。因此只要统计「左侧的数都不大于它」的数的个数即可。

代码.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

void solve(){
    int n;
    cin >> n;
    int ans = 0, maxn = 0;
    for(int i = 1; i <= n; ++ i) cin >> a[i];
    for(int i = 1; i <= n; ++ i){
        if(a[i] >= maxn){
            ans ++;
            maxn = a[i];
        }
    }
    cout << ans << "\n";
    return;
}

C. Spring

题面. 给定整数 。一共有 天，在 的倍数天 A 去打水（B、C 类似）。每天有 桶水，如果该天无人打水则无事发生，若有 人打水则打水的人每人打 桶。求 A、B、C 各自打了多少桶水。

题解. 利用容斥原理计算每种打水情况的天数即可。涉及公约数的计算应当使用欧几里得算法。开 long long。

代码.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

ll gcd(ll x, ll y){
    if(x < y){
        ll t = x;
        x = y;
        y = t;
    }
    if(x % y == 0) return y;
    return gcd(y, x % y);
}
 
void solve(){
    ll a, b, c, m;
    cin >> a >> b >> c >> m;
    ll ab = a * b / gcd(a, b);
    ll ac = a * c / gcd(a, c);
    ll bc = b * c / gcd(b, c);
    ll abc = ab * c / gcd(ab, c);
    ll cnt_abc = m / abc;
    ll cnt_ab = m / ab - cnt_abc;
    ll cnt_bc = m / bc - cnt_abc;
    ll cnt_ac = m / ac - cnt_abc;
    ll cnt_a = m / a - cnt_ab - cnt_ac - cnt_abc;
    ll cnt_b = m / b - cnt_ab - cnt_bc - cnt_abc;
    ll cnt_c = m / c - cnt_ac - cnt_bc - cnt_abc;
    ll ans_a = cnt_a * 6 + cnt_ab * 3 + cnt_ac * 3 + cnt_abc * 2;
    ll ans_b = cnt_b * 6 + cnt_ab * 3 + cnt_bc * 3 + cnt_abc * 2;
    ll ans_c = cnt_c * 6 + cnt_ac * 3 + cnt_bc * 3 + cnt_abc * 2;
    cout << ans_a << " " << ans_b << " " << ans_c << "\n";
    return;
}

D. Alternating Path

题面. 给定一无向图，没有自环和重边。给它的每条边赋予方向，可以使它变为有向图。对于这样一个有向图，称它的一个节点 为 beautiful，若果它满足如下性质：

对于原无向图中从 开始的任意一条道路（可以包含环），总是满足： 都是新的有向图中的边（也称这样的道路为 alternating path）。

考虑所有给原图赋方向的方法，求最多能够得到多少 beautiful 的点。

题解. 由于刻意的定义、晦涩的描述，该题在赛后被一致评价为屎题。事实上此题的实质是简单的。首先注意到，原图的各个连通分量是独立的，可以分别计算答案并加和。

我们断言：

对于每个连通分量，其中存在 beautiful 点，当且仅当它是二分图。

一个无向图是二分图，如果可以将其节点分为两个子集 ，使得边仅存在于两子集之间（而不是子集内部）。等价地，可以将图的节点染成两种颜色（-着色），使得相邻节点的颜色不同。可以证明，这也等价于图中不存在长度为奇数的环（证明）。一个例子如下图：

断言的证明

如果连通分量是二分图，只要把所有边的方向都定为从 到 ，那么 中的点显然全是 beautiful 的。

如果不是二分图，则它内部存在长度为奇数的环。考虑图中任一节点 ，由于考虑的是连通分量，总可以找到「从 进入奇数环，而后绕奇数环两圈」的道路，但「绕奇数环两圈」无论怎么赋方向怎么也不可能是 alternating path。因此任一节点都不是 beautiful 的。

至此，本题的解法就很显然了：只需要对每个连通分量判断它是否是二分图，如果不是则其答案为 ；如果是，则其答案为「-着色后，两种颜色的点的个数中较多者」。判断二分图的标准方法之一正是尝试 -着色（使用 bfs 或 dfs 均可），因此可以一边判断二分图，一边尝试着色并累加答案。复杂度 。

代码.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

vector<int> g[N]; // 邻接表
bool vis[N];
int color[N] = {0}; // 染色：0为未染色，颜色可以为1或2

int bfs(){
    queue<int> q;
    int ans = 0;
    for(int i = 1; i <= n; ++ i){ // 通过 i 枚举连通分量
        if(vis[i]) continue; // i 属于之前的连通分量（已经考虑过）
        
        int cnt = 0, cnt1 = 0;
        // 新连通分量，从节点 i 开始搜索
        q.push(i);
        color[i] = 1; // 起点染色为 1，尝试交替染色
        bool flag = true; // 该分量是否为二分图

        while(!q.empty()){
            int now = q.front();
            q.pop();
            if(vis[now]) continue;
            vis[now] = 1;

            if(color[now] == 1) cnt1 ++; // 计数颜色 1 的个数
            cnt ++; // 计数连通分量的点的总数

            for(int i = 0; i < g[now].size(); ++ i){ // 遍历 i 的邻居
                int nxt = g[now][i];
                if(color[nxt] && color[nxt] == color[now]) // 染色冲突：nxt 本应染与 now 不同的颜色，但已经被染上了相同颜色
                    flag = false;
                
                if(!vis[nxt]){ // 搜索新的节点
                    q.push(nxt);
                    color[nxt] = 3-color[now]; // 染另一种颜色
                }
            }
        }
        if(flag) ans += max(cnt1, cnt-cnt1); // 是二分图才累加答案
    }
    return ans;
}
 
void solve(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++ i){ // 初始化（因为多测）
        vis[i] = 0;
        color[i] = 0;
        g[i].clear();
    }
    for(int i = 1; i <= m; ++ i){ // 建邻接表
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    cout << bfs() << "\n";
}

E. Sum of Digits (and Again)

题面. 考虑正整数 ，定义 是如下伪代码构造的字符串：

1
2
3
4

S(x) = EmptyStr()
while x >= 10:
    S(x).append(str(x))
    x = SumOfDigits(x)

现在给定由 0~9 数码构成的字符串 （），保证：通过重排 的字符，可以使得对于某个正整数 ，。求出这个重排。

题解. 感觉本题比 D 简单。注意到，由于长度是 量级，即便是这么多个 加在一起，产生的数位和也不过是一个 位数。换言之，只要初始的 ，第一次求数位和的结果（记为 ）就至多有 位。

这启发我们枚举 ，从 枚举到 即可。对于给定的 ， 中位于 之后的字符串内容也是确定的。剩余没用过的数码都应该位于 之前（顺序无所谓），如果它们加起来恰好等于 ，则找到了满足要求的重排。复杂度为 的量级。

的情形需要特判（因为不需要计算第一次数位和，也就没有 ）。

代码.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

void solve(){
    cin >> s;
    int n = s.size();
    for(int i = 0; i <= 9; ++ i) cnt[i] = 0;

    if(n == 1){
        cout << s << "\n";
        return;
    }

    int tot = 0;
    for(int i = 0; i < n; ++ i){
        int x = s[i] - '0';
        cnt[x] ++;
        tot += x;
    }

    for(int k = 1; k <= 999999; ++ k){
        int r[15] = {0};
        for(int i = 0; i <= 9; ++ i){
            r[i] = cnt[i];
        }

        int now = k, sum = tot;
        bool flag = true; // 是否为可行的重排
        vector<int> ans; // S(x) 中从 k 往后的字符串内容

        while(now > 9){ // 从 now=k 开始尝试循环
            int tmp = now, add = 0;
            while(tmp){
                int dgt = tmp % 10;
                add += dgt;
                if(r[dgt] == 0){ // 要用的数码不够了，已经证明当前 k 不可行
                    flag = false;
                    break;
                }
                sum -= dgt; // 记录没用过的数的和，这里使用了 dgt，所以减去
                r[dgt] --; // 记录每个数码剩多少
                tmp /= 10;
            }
            now = add; // 将 now 更新为 now 的数位和
            ans.push_back(now);
            if(!flag) break;
        }
        if(!flag) continue;

        if(r[now] == 0) continue;
        sum -= now;
        r[now] --;

        if(sum != k) continue;

        // k 可行（把 k 及之后的字符串处理完后，没用过的数加起来确实是 k）

        for(int i = 9; i >= 0; -- i) while(r[i] --) cout << i; // 先输出剩余的数码（都应该在 k 前面，顺序无关）
        cout << k;
        for(int i = 0; i < ans.size(); ++ i) cout << ans[i]; 
        cout << "\n";

        break;
    }
}

The attacking idea in this game draws inspiration from the standard Grand Prix Attack, where white is able to play Bb5 after black’s Nc6. In this case, however, black prevents it with his early 4... a6 move. I responded by correctly playing 5. g3 transposing into a closed Sicilian with a tempo up, and carried out a similar attacking sequence Qe1 g4 f5 Qh4 f5 Bh6 Ng5 and the sacrifice Rxf6!.

Another nuance is that, normally white has a rook on a1 that can swing across to f1 when Kxf6 happens. In this game, the rook on a1 is also sacrificed, making the attack much more calculation-intensive. Luckily, black did not find the only defending move 20... Kxe5 (which is shocking!), and I was able to score a nice win.

笔者小时候幻想过如下问题：假设士兵 Alice 在一块空旷的草地上被敌方狙击手 Bob 瞄准，要如何让自己尽可能活命。专业人士告诉我们，如果 Bob 训练有素，Alice 的存活概率是 0。

当然，我们直觉上会认为，通过随机地跑 S 线（不断转向）躲开狙击手的枪线，无疑更有可能迷惑其判断使其空枪。因此，我们不妨假设 Bob 是一名吃晃的狙击手，来探讨 Alice 应该采取怎样的策略提高自身的存活概率。

游戏规则

我们把问题抽象为如下游戏：Alice 在 坐标的整数点上运动，初始位置为 。在每个整数时刻 ，Alice 可以选择向左或右移动一个身位（对应于逃跑过程中的转向），即 ；Bob 则可以在任何整数时刻 ，决定瞄准 轴上的任何一个位置 开枪。Alice 的位置在任何时刻都是被 Bob 知晓的（因为他有瞄准镜），但 Alice 并不知道 Bob 会在哪一时刻开枪。

那么，如何定义 Bob 的「吃晃」呢？我们假设 Bob 的反应很慢，从决定开枪到真正扣下扳机，需要 个时间步；或者也可以理解为，子弹要经过 个时间步才能飞行到目标。无论采用哪种理解方式，总而言之，游戏遵循「Bob 成功击中 Alice 并获胜，当且仅当 」。很显然，Bob 无论何时开枪，都只有三个合理的瞄准位置，让他有机会命中，分别是 。

为了让 Alice 有一丝存活的概率，我们假设 Bob 只有一发子弹。草地是无限大且没有掩体的，即该游戏的进行时间是无限的。这个游戏我们记为 。粗略地讲，我们希望求出，在双方的最优策略下，Alice 的存活概率是多少；稍后我们将给出这个问题的严格叙述。

为了便于分析，我们也定义该游戏的有限时间版本：我们定义 与上述游戏唯一的区别是，我们限制 Bob 必须在第 个时刻及之前开枪，即进一步要求 。我们将通过分析 时 的性质来获得 的性质。

博弈论科普

我们刚刚谈到，我们想要求解的问题是：

在双方的最优策略下，Alice 的存活概率是多少？

在开始分析之前，我们必须要先弄清楚两个问题： - 什么叫「双方的最优策略」？ - 为什么在双方策略都可以调整的情形下，Alice 的存活概率是一个可以计算的确切的值？

事实上，上述游戏是「双玩家零和博弈」的一个实例，这是博弈论研究的最简单的一类问题，有非常成熟的工具解决它。下面我们为没有接触过相关理论的读者介绍所需的基础概念。如果读者已经非常熟悉，请跳过这一节。

在一个双玩家零和博弈中，最基本的情形是，双方玩家都采取一个确定的策略；两名玩家（Alice 和 Bob）的策略集（考虑有限情形）是两个有限集（不妨编号为 和 ），而博弈的 payoff 完全由两个玩家的策略决定，因此可以总结为一个矩阵 。对于两个玩家而言，他们的收益总是互为相反数，即分别为 和 。Alice 的目标是使 尽可能大（即最小化 的值），Bob 的目标是使 尽可能大。

在博弈论中，我们更关心双方玩家在「随机化策略」的意义下，能够获得的期望 payoff、以及相对应的「混合策略」是什么。一个混合策略即是在所有的策略上的概率分布。将分布写成向量，即两个玩家的策略 分别属于 那么，最终「Alice 选择 ，Bob 选择 」这个事件出现的概率是 ，因此，payoff 的期望是

这是一个双线性形式。因此，这类游戏也被称为 finite-dimensional zero-sum bilinear game。

那么，作为玩家之一，在不事先知道对方策略的前提下，应该如何选择己方的策略呢？我们以 Alice 的视角为例：假定她选择策略 ，那么在最坏情形下（这里的变量即是对方的策略 ，对 Alice 来说，最坏情形即是 最大的时候，因为她希望最小化之），她能保证的结果是 其中 表示 的第 个列向量；第一个等号是因为，我们总可以在 最大的分量上赋予全部的概率（即取 是 one-hot 向量），以此最大化想要的值。

Alice 希望最坏情况下的结果尽可能好，因此她希望最小化「上述值」，即她希望从下式中求解 作为她的最优策略：容易看出，这等价于如下线性规划问题 因而是有程序化的方法求解的。

同理，Bob 的最优策略 通过求解下式得到 至此，问题的对称性已经初具雏形。由于其对称的形式，此类博弈也被称为 min-max game。

纳什均衡

下面的定理给出了我们要用到的核心结论： 定理 (von Neumann). 对于任意 min-max game，存在 满足 被称为这个博弈的纳什均衡。由纳什均衡定义的 被称为博弈的「价值」。

von Neumann 定理有诸多证明，网络上很容易搜索到。证明之一是：验证两个 min-max game 对应的线性规划问题互为对偶，并利用强对偶性。如果读者没有接触过优化理论的知识，也没有关系，本文的叙述并不依赖该定理的证明。

纳什均衡是一类更广泛的博弈的产物，其更广泛的存在性需要用更高等的数学工具来证明。但是对于这里的情形，它有一个基于线性对偶理论的证明。我们推荐数学基础较好的读者参看文末的证明。对于本文的目的而言，我们只希望读者验证以下重要事实：

在纳什均衡处，即使一方玩家事先知道对方策略，他也不能取得更好的结果。

这个结论是十分迷人的：虽然双方玩家都是在不知晓对方策略的情形下，独立导出的己方最优策略；但双方策略形成的均衡，却使得双方都没有改变策略的动机（即使知晓了对方的策略）。

对于一般的零和博弈，其价值往往难以计算，但上述定理保证了其存在性，并且可以通过构造策略来证明它的上下界。具体地，如果我们构造了某个策略 ，满足 即 因而 即 只会比任意 Alice 策略保证的下界更小，即给出了一个 的上界。同理，可以通过构造 Bob 的策略来给出 的下界。

有限时间

我们用 来作为实例，感受一下 von Neumann 定理的强度。在博弈 中，Bob 只能在 时刻开枪，因此其有意义的策略仅有 ，共 种；Alice 是否中枪，只取决于其前两个时刻的行为，因此其策略（用两个时刻先后到达的位置表示）包括 共 种。这个博弈的 payoff 矩阵 因而是

对于任意 Alice 的逃跑策略 ，Bob 都可以选择瞄准三个位置中 Alice 到达的概率最大的那个，以最大化其收益（即命中的概率），显然这个值不小于 。因此，Alice 应该让这三个概率相等，即使得 一个满足要求的策略是 ，请读者验证，无论此时 是什么， 的值都等于 。类似地，请读者进一步验证， 也满足类似的性质，从而 是纳什均衡，博弈的价值为 。

类似地，可以证明 。我们指出，。

也许一些敏锐的读者会感到惊讶：不管 Bob 在哪一时刻开枪，Alice 都可以选择让自己 个时刻后处在三个位置的概率相等，从而让中弹的概率（即游戏的价值）至多是 ；按照这个思路，对于任意 价值不应该恒等于 吗？问题的关键在于，Alice 并不知道 Bob 开枪的时刻。为了实现上述策略，她必须保证自己在每一时刻的概率都均摊，通过研究 的性质，就可以发现这是做不到的。当然，如果 Alice 确切地知道 Bob 何时开枪，那么确实有 了。

无限时间

至此，完整问题的严格叙述已经呼之欲出了。我们想要解决的问题：

在双方的最优策略下，Alice 的存活概率是多少？

事实上就是求：

因此，我们要研究 作为一个数列的性质。首先，它显然是单调不降的，这是因为对于狙击手 Bob 而言，在 中，他总可以采取 中的策略，这样他至少可以保证 的结果，因此至少有 。特别地，。

另一方面，对于任意 ，如前文所说，我们可以也构造一个 Alice 的策略 ，保证任何情况下 不大于某个常数，从而证明一个 的上界。我们尝试构造如下一类策略，它包含一个参数 ：

在 时，Alice 以 的概率向左走（到达 ），以 的概率向右走（到达 ）。此后，她每一步以 的概率保持上一步的方向继续前进，或以 的概率调转方向。

这个策略的重要之处在于，它每一步的决策过程都是完全对称的（这与我们上一节中为 构造的最佳策略不同）。按照这样定义的策略，无论 Bob 在何时 开枪， 时刻 Alice 的位置在 三个点的概率值总分别是 或 。对 Alice 而言的最坏情况下，Bob 总会选择瞄准这三个概率中最大者对应的位置，因此，Alice 应当尽可能使这三个值都很小。注意到 ，因此事实上，这一类策略中最优者应该最小化 求得 此时 Bob 的 payoff（即他能保证的最大命中概率）为 这不是最佳策略，因此该值只是一个上界，即 至此我们证明了， 是一个单调有界的序列，因此保证了 的存在性（事实上，如果读者足够细心，应当在此之前就提出了存在性的疑问）。那么，这个上界能取到吗？首先，我们观察到一个有趣的事实：

命题. 是有理数。 证明. 的 payoff matrix 是一个元素均为 0 或 1 的矩阵。这个 min-max game 对应的线性规划问题为：线性规划问题的解在可行域的顶点处取得，即 是某个由部分约束方程的等式形式确定的解。但是，三类约束方程的变量系数均为有理数，因此 也是有理数。

因此，事实上有： 命题. Samuel Karlin 于 1958 年证明了，虽然任意有限的 都取不到这个上界，但 确实收敛到这个值。证明没有用到任何高深的工具，只牵涉到一些计算技巧，对于掌握中学数学知识的读者是完全可以理解的。下面让我们来欣赏这个证明。

直面递推

很容易想到，由于问题是递归定义的，应该可以对问题进行递推的拆解。对于 ，我们定义 为：Alice 固定采取「 时，以 的概率向左， 的概率向右」的策略时， 的价值。显然有 。很显然也应该有 ，。

那么， 的递推是什么呢？这依赖于 Alice 第二步的策略，所以我们记其策略中，「第一步向左时，第二步也向左」的概率为 ，「第一步向右时，第二步向左」的概率为 。这样，用 三个参数，我们就可以描述 Alice 在两步之内的任何一种策略了。两步之后，她可以所处的位置和概率分别为 如果 Bob 在 时刻开枪，那么对 Alice 来说，最坏情况下 Bob 会瞄准这三个位置中概率最大的那一个（三个选项）；当然，只要 ，Bob 也可以不在 时刻开枪（第四个选项），这种情况下他只能在之后的 个时刻内开枪，因此他能获得的最大收益是 于是，对 Alice 的最坏情况下，Bob 会选择四种选项中 payoff 最大者，因此有递推：边界为 直接计算可得，，，且在剩余区间内它是线性函数。

设 收敛到 。 应该是递推式的不动点，即满足 我们要求的即是 这里取得最小值的 不是唯一的，所以我们记满足 的 中最小者为 。那么应当有 进一步设这里的 由 取得，那么有 注意到最后一行的 ，所以 ，所以 ，由对称性也有 再看第二行，我们有 ，因此 。

下面我们来证明 也不能成立。若不然，由 相加得 右边在 上是单调递减的，且 ，因此 解得 ，这与 是矛盾的。因此，。

因此 中的第二项至少是 ，因而必须等于 ，从而 从而 解得 。由此证明了

我是一个身无寸铁二十年的学生。我试着去想这期间我所做过最英勇的行为，终究没有在众人自危的年代挺身而出的勇气；唯一让我燃起英雄主义的烈焰的，只有在众人熟睡的时刻熬穿大夜。

我自诩没有烟酒作为爱好，是个稀有的良民。然而，莫非人终究要依靠损伤身体获得精神上的慰藉，我竟然是喜欢熬夜的。大考之前是也许必要熬的，因为半数的书还没有开始念；大考之后也是应当熬的，弥补为这俗事折损的时光。无事也是可以熬的，只因次日早晨可以恣意地睡懒觉。我在一般男孩染上烟酒的年纪染上了熬夜。父母对此是深恶痛绝的，倘若我摆出正当的理由要熬夜，他们便称他们做父母的，儿子不睡他们也无心睡，先在道德上消磨我的防线；如果软法不成，则凌晨一点左右，二人商议过后便硬来阻止。可惜科学家计算出一根烟折损寿命五分钟，乃至于印在包装盒上；我却不知熬一小时折损多少，只觉赚出一小时。因此虽然知道有害健康，也便自欺欺人地坚持下来。

曾经看到一个说法：由于夜里黑，人的大脑要处理的视觉信息少，省出的神经元便可以拿去做别的事情。我深以为然，因为我确切地觉得，夜里较白天不容易分心；坏处便是脑子运转的较慢——黑夜仿佛染进时间，让它的流动变得粘稠而稳定。从小时候起，我总是该睡觉时却不困，幼儿园的午觉一次也没有睡着过，晚上更是久久才能睡着，躺在床上看着窗帘被风鼓动，晚归的汽车进入地库时前灯扫过我的卧室；很早先的时候，还能听到中华门火车站的汽笛。小学时的诗歌比赛，我为这个场景写了一首愚蠢的三行诗，收获了众人的嘲笑。然而我清晰地记得那时夜色充盈着我的脑髓；我此生再也没有像那时一样清醒过。后来的我仿佛再也没有在夜里听见过声音，或者失去了对它们的任何记忆。

归根结底我知道熬夜加速着我的死亡，即使作为一个身无寸铁二十年的学生，也是不可以不管不顾的。然而每到了午夜，我总还是不愿意撒下手里的事情上床睡觉。深深的夜给我以时间无穷的幻觉，让我感到我的一切烦恼都是可以在这一夜里被解决的，否则太阳也不会升起。熬夜是因为愧疚过往浪费的时日，又是因为期待未成而可成的事功。它们是我闭上眼睛时，即使努力地想象一片黑暗，眼前仍然浮现出的光影。我想，一个足够幸福的人，闭上眼睛是不会看到这些光的；恐怕也是不必熬夜的。

小时候我常怀疑，人睡着再醒来，该如何证明还身处同一个世界。我长大了，熬的夜愈来愈深，我看到北京的马路上车流从来不会间断，我发现大夜熬穿太阳真的还会升起，我发现无论我清醒、昏睡抑或醉倒，时间依旧流逝，世界依旧漠然。我怕我长大到二十岁以后，熬再多的夜也不再拥有清醒的权利。

We consider an optimization problem over domain in standard form, i.e. which we do not assume to be convex. We assume the optimal value to be .

The Lagrangian associated with this problem is defined as where the vectors and are the dual variables. In fact, the primal problem is equivalent to solving as can be seen by noting that the supremum for feasible , and is for infeasible ones.

The dual function is defined as The dual function is always concave, even when the primal is not convex. We would refer to the set as , because restrictedly working on this set would not cause any loss of generality.

Proposition. , we have which means the dual function always yields lower bounds for the primal.

Proof. If is feasible, then , thus . Thus,

The dual problem is asking about the tightest of such lower bounds, i.e. the solution of which we denote which is primal with max/min inverted.

We have already shown:

Theorem (Weak Lagrangian Duality). which is in satisfying symmetric form. This in fact does not depend on any property of , because it’s an instance of the general max-min theorem.

Strong duality, however, does not hold in general. But if the primal problem is convex, with minimal additional condition, we do have strong duality. One of these is Slater’s condition:

Theorem (Strong Lagrangian Duality). For a standard form convex optimization problem, namely which satisfies Slater’s condition: such that and (i.e. at least one feasible point exists for all inequalities to hold strictly), we have .¹ Further, the optimals can be attained by some primal and dual variables (so the / can be replaced by /).²

Proof. cf. Boyd, p235.

KKT Optimality Conditions

We still work without convexity assumptions. Suppose that the primal and dual optimal values are attained and equal (strong duality holds), with and respectively. We have so we must have . This condition is known as complementary slackness.