橘子，草莓，排序不等式

昨晚BB罗同学大驾光临吃晚饭，饭后吃水果环节，由于草莓放得有些久了，我切掉了变软的部分。剩下的总量不够，又拿了橘子补上。由于大家都很饱了，吃了几块就不想吃了，但是我觉得好像罗老师只吃了橘子还没吃草莓就饱了好像有些亏。

于是我们抽象出了一个问题模型。假设两种水果各有N块，吃每块水果的Utility既和这是这种水果的第几块有关，涉及新鲜感，又和总共已吃了几块水果有关，涉及饱腹感。直觉告诉我，某种模型下的最优解是两种水果交替吃，但是罗老师却觉得，吃每块水果时对饱腹感的影响已经算进那个slot的utility了，具体吃某种水果可能没关系。我们决定设计一个价值函数来表示新鲜感和饱腹感共同影响，然后看看最优解的形式会不会出现两种水果交替吃。

我们的第一个模型是最简单的线性模型，某品种第i块水果、总计第n块水果的Utility直接等于(N-i)+(2N-n)。我很快意识到，这样不论如何排序，Utility总和都是常数。该死，线性不行！

董老师提出了一个更合理的非线性函数1/n，然而如果用1/i+1/n作为价值函数还是不行；重点在于加法导致了前后两块水果可交换，所以总和还是常数。于是我想到了引入乘法，水果的估价函数变成了(N-i)/n。对于每种水果都是一个随块数线型递减的新鲜感指数，乘以一个倒数递减的饱腹感。看上去这个函数很合理。

我还在脑中想象为啥最优解应该是交替吃时，董老师已经瞬间给出了一句话证明：排序不等式。这好像是我高中开始就多次听说过但没有真正用过的不等式，于是我赶紧趁这个机会了解了一下：如果有两个序列需要排序后两两对应乘起来求和，那双方各自排序时求和最大，反向排序时求和最小。在刚刚的模型中，每个水果各自的新鲜感指数总共2N项必须从大到小排序，才能与固定的排好序的饱腹感指数相乘时有最大的乘积。因此，交替吃是最优解。类似的证明也可以推广到Utility取1/(in)的情况。

我继续推广问题模型，说如果把离散改成连续情况，那最优解应该是每种水果每次各吃epsilon后就交换，对应现实生活中相当于全部一起打碎变成水果冰沙，而这也是我平常喜欢的方式。罗老师表示反对，他认为喝冰沙彻底磨灭了每种水果各自的口味，但是要说明这一点的模型很难建。我们觉得应当需要某种moving window，他提出的模型是每次切换水果后delta t之内吃同一种水果有加成，或者切换水果有惩罚；我觉得一个更合理的方案是每种水果是高维空间中的单位长向量，算过去delta t之内所有种类的向量加权平均离原点的距离。虽然两种模型都惩罚频繁交换，但我的模型允许在有多种水果时把味道相近的几种打成冰沙。

最后，我联想到了量化金融领域存在类似的问题，有两个冲突的目标，一个是使股票持仓精准的遵守某个函数来最大化收益，另一个是每次通过交易改变数值都需要付出额外的成本，因此要限制频繁改变。这个和吃水果时需要多切换才能最大化收益但又不希望频繁切换水果种类影响口感的模型是一样的。如果不存在后一种限制，问题就可以简化成最优化打冰沙。

我突然有点感慨，我自己真是怪异，很难再找到一些吃水果时还能煞有介事的跟我讨论不等式的人了。

2018 年 02 月 14 日

quiz, 数学

叽叽歪歪