4个数盲排序游戏的得分期望计算与双方最优策略问询

嘿，咱们把这个游戏问题拆解清楚，一步步来解答：

先明确游戏核心规则（避免误解） #

首先得把规则理透，不然容易跑偏：

• Bob会依次给Alice4个小于100的不同自然数（例子里都是不同的，默认不重复）
• Alice每收到一个数，必须立刻插入到当前的序列里（不能回头调整之前的数的位置，也不知道后面会收到什么数）
• 最终得分是序列里满足「大数在小数左侧」的数对总数：比如升序序列33,56,57,89里，所有数对都是小数在前，得分0；而89,54,90,99里只有89>54这一对符合，得分1。

一、得分期望E(s)的计算 #

这里的得分期望取决于Bob和Alice的策略选择，我们先看最公平的场景：

Bob随机选4个不同的数，随机选择给出顺序；Alice采用随机插入策略（每个可选位置等概率选）。

这种情况下，最终的所有4!种排列是等概率出现的。4个数总共有C(4,2)=6个数对，对于任意一对数，大数在左侧的概率是1/2（因为两种顺序对称）。所以期望得分就是：
E(s) = 6 × 1/2 = 3

如果Bob采用最优策略来压分，期望会更低；如果Alice用最优策略提分，期望会更高。

二、Alice的策略：能不能保证得分超过1？ #

当然可以，甚至能保证远高于1分，分两种情况说：

情况1：Alice知道每个数的具体大小（正常情况，毕竟收到的是自然数） #

Alice可以用贪心降序策略，每收到新数就插入到序列中保持降序：

• 第一个数直接放，序列[x1]
• 第二个数x2：比x1大就插左边，小就插右边，此时序列是降序，得分1（这一对数肯定符合要求）
• 第三个数x3：不管大小，插入到能保持降序的位置，比如当前序列是[a,b]（a>b）：
  • x3比a大→插最左，新增2个符合的数对，总得分3
  • x3在a和b之间→插中间，新增2个符合的数对，总得分3
  • x3比b小→插最右，新增2个符合的数对，总得分3
• 第四个数x4：同样插入降序位置，至少新增3个符合的数对，最终得分至少6（满分）。

也就是说，只要Alice能看到数的大小，她完全可以保证拿满分，根本不用担心得分低于1。

情况2：Alice不知道数的大小（极端假设，比如只收到符号不知道数值） #

这种情况下，Alice至少能保证得1分：第二个数时，随便选左边或右边，只要后面不调整这个位置，至少有一对数的顺序是固定的；甚至可以用更谨慎的策略，比如第二个数插左边，第三个数插中间，保证至少得2分。

三、Bob的最优策略：能不能限制Alice的得分？ #

这要看Alice是否知道数的大小：

• 如果Alice能看到数的大小：Bob完全没办法限制，因为Alice总能把序列排成降序拿满分。
• 如果Alice不知道数的大小：Bob可以采用交替给出最大/最小剩余数的策略，比如对于数1,2,3,4，按2,4,1,3的顺序给出。这种顺序会让Alice难以判断后续数的大小范围，无法准确插入到最优位置，从而把Alice的得分尽可能拉低到接近期望3分的水平。

备注：内容来源于stack exchange，提问作者Swastik Sanyal