文章
来源：中国数学
下面的问题来自姚期智教授的理论计算机的授课内容——我是其助教之一：
现假设你在PIE上征友，或者以其它方式，选定了某些约会对象，比如
n=20
个。
约会当然得一个一个来，那么假设
-
可以将所有已约会的对象按优劣排序，但无法得知他们在所有的人里面的排名。
在约会过程中，你知道某人是你目前已见到的最好的，但当时还不能确定是不是所有人里面最好的。
-
如果你在约会当时决定放弃某人，后面再没有机会和此人和好——好马不吃回头草。
-
选定意中人后，约会结束——骑驴找马是不道德的。
OK，现在目标当然是找到你心目中最喜欢的人。
关系定得太早，会因为第2条假设——精彩的还在后头，定得太晚，会因为第3条——而后悔莫及。
所以，什么策略才能让你以最大概率找到你最满意的那个人呢？
一个简单而且自然的方法是，待定
k
，与前
k
个人约会，不做任何选择。
继续约会直到遇到比这前k个人还好的那个人为止。
通过概率计算得出，这个方法比我们想象中要好得多。
通过选取合适的
k=n/e～0.37n～7
，有接近40%的机会选中最好的那位，有几乎70%的机会选中最好或者次好的那位。
可以证明，上面的策略已经是最优的了。
这个问题在日常生活中有更多应用。
比如你打算在30岁前结婚，现在20岁。
那么在24岁前先别确定目标，24岁以后遇到比之前都好的就可以定下来。
这几乎就是你能达到最好的结果了——假设你的候选人在这十年是均匀或者随机出现的。
这种策略也许能说明为何初恋成功率低？
以上所用都是爱情和婚姻的简化模型，没有考虑爱情中的主观因素。
所以，请只把它当作一个脑力游戏。
下面将证明：
最佳约会策略里提到策略，忽略前37%的对象，然后在剩下的对象里挑第一个比前37%都好的对象，这个策略是最优的。
更准确地，我们将证明：
任何约会策略的成功概率都不可能超过
un∑n−1i=u1i
，其中
u
为满足
∑n−1i=u1i≥1
的最大值。
这个
u
大约为37%，最后成功的概率大约为40%。
首先定义一些符号，
∏n
表示
{1,2,⋯,n}
的排列的集合。
我们可以定义排列之间的半有序关系。
对于任何两个排列
α∈∏a
和
β∈∏b
，如果
a≤b
并且
α
的前a项的大小顺序和
β
一样(即对任意
1≤i,j≤a
都有
αi
)，我们则认为
α≤β
，我们也可以用另外一种说法，满足这样的条件的
α
被认为是
β
的字排列。
对任意
α∈∏n
，令
Fk(α)=β∈∏ks. t.β≤α
下面开始证明。
随机策略是确定性策略的随机组合，所以任何一个随机策略的胜率都不会超过其中最好的确定性策略的胜率。
所以我们只需要对确定性策略证明上述胜率上届。
而首先，我们需要对一个约会策略建模。
任何一个策略面对一个约会对象的序列，这个序列可视作一个排列组合。
策略一项一项检验这个排列组合，并且决定在什么时候停止。
假设这个策略在检查
α
时停止在第
k
项，那么该策略只知道
α
的前
k
项的相对顺序，也就是
Fk(α)
，便决定停止。
令
Sk∈∏k
为所有这样的
Fk(α)
，并令
sk=|Sk|
。
我们也称
S=S1∪S2∪⋯∪Sn
为策略的停止集。
显然，对于任意
α∈Sk
, 都有
n!k!
个排列比它大。
这其中，有
(n−1)!(k−1)!
个排列被策略成功找出最大值(即第
k
项为
n
)。
所以策略在第
k
项停止并成功的概率为：
P=1n!∑k(n−1)!(k−1)!⋅sk
从上面概率等式看，一个策略的停止集越大越好。
现在我们需要指明一个事实，这是证明我们结论的关键。
一个策略的停止集
S
并不能无限制的大，它必须满足其中的任意一个排列都不能是另外一个排列的字串，即对任意
i
,
α∈Si
且
β∈Sj
,
α
不可能是
β
的自排列。
如果同为停止集元素的排列
α
是另一个停止集元素
β
的子排列，那么当策略在遇到
β
时，策略将直接停止在第
i
个元素，不会等到第
j
个元素才停止，从而
β
不可能也是停止集合的成员。
从上面的事实，我们计算
