最佳的选择：

首先我们先规定几个标记，以方便论证：

:表示第 k 个物品的名次，即实际名次。显然，这是个随见变量，而且我们对于该名次，之前是一无所知的，但是我们知道的，是每个物品的临时名次，也就是说，当我们看到第 k 个物品时，该物品在前 k 个物品中排第几我们是知道的。

前面简单的办法，即放弃前面一半，结果已经十分不错了，我们自然会想到跟一般的办法。

: 放弃前面 k-1 位。自第 r 位起，首次遇到较前均佳者即停。

也就是说，自第 r 位起，选择首次出现的临时第一名。请注意，所谓放弃前面 r-1 位，当然是你决不选他们，但是你仍应对这些物品打量一番，以便与后来的作个比较，也就是说，以便决定后来者的临时名次。又 M₁，没有什么意思：你必须选取第一位，因为第一位一定是一个临时第一名。

为根据上述办法，选中第一名的机率 

S_k为根据上述办法，第k件物品被选的事件 

则，可得：

这里代表,即A和B同时发生的概率。

好的，让我们一步一步地阐明这个公式的意义，

首先，我们利用这个策略，要获胜，只有可能是取了再中选取了一个，且我们取得的物品(第 k 个物品)一定要是实际排名第一位的物品。

这个事件有可能发生在中的任何一个物品上面，所以这 n-k+1 个随机事件中只要有一个发生（即为真），则为真。

所以这 n-k+1 个事件之间是“或”的关系，所以，这里我们用求和。之后的就很好理解了，

这是利用条件概率的公式：,这在任何一本概率统计的书都会讲到。意义也很好理解：

即 A 事件与 B 事件要同时发生的概率 等于 在 A 事件发生的情况下 B 也发生 且同时 A 也发生的这个事件的概率，注意是同时发生，所以 P(A|B)和P(B) 之间是相乘的关系，A,B 位置反之亦然。

显然，

那么， 又等于什么呢？

我们可以这么看，假如第一名在第 k 个位置，那么，按照，只有下面的情形我们才能选到它：

前面k-1个物品中的最好的物品（不是实际的最好）要发生在最前面r-1个位置里。

这里为了方便表述，这个情形，记作：事件N。

这个很好理解，因为如果不是这样，即前面 k-1 个物品中的最好的物品在这个区间中，那么必然会在检查第k件物品之前就做出了选择，拿走了物品，不可能检查得到 k 个物品。所以，以上的这个事件N是: 在的条件下，发生的必要条件，即：

在的成立的条件下，发生 事件N 发生。反过来，如果在的条件下，事件N 发生，那么我们也必然会做出 取走第k个的选择，即，发生。

可知： 如果在的条件下，发生 事件N 发生。所以，在的条件下，与事件N 是等价的事件。

综上所述，

因此，

显然,，

同时，（2）式是个仅仅与 r 有关的函数，可以记作：,而我们要求的便是一个 使得取得到最大值，那么，就是最佳的选择方法。看到这里，比较细心一点的读者也许会问：你怎么可以保证没有再好的办法呢？换句话说：最好的办法，一定是在上述这类里面吗？答案是肯定的，证明也不是很难；等我以后时间，会在blog上给出证明。读者如要深究，可参照资料下篇文章文末的参看数目中的[4][5]，好好想一想。

接下来，以 代表的“增率”。即，的差分。

从（2）式我们可以看到：

此处，n 为定值，若 r 增加，则，求和的项数减少，而每项又都是正的，由此可知，是r的单调减函数。

同时，的初始值，即 r=2 时，可以取得到最大值，

, 该式在  的时候为正数，其实，我们可以发现，当n不大的时候，用这样的策略的意义并不是很大，因为即使是随机地去，概率：1/n 也会很大，所以在此不妨设 n 的范围是 ^, 继而，我们可以论证 的情况（利用（2）式）：

n=1: 只有一个可选，不得不选第一个。

n=2：

n=3: 

n=4: 

之后对于， 的情况的分析如下，

 而 

所以在 的定义区间内，必定存在一点 使得最接近0（可能大于0，也可能等于0，不能是小于0），同时也使得，即取得最大值。

如，图（1）(此处 n=12)

所以就有,  且 ,即：

任意定了n后，就可自(4)式中计算出来。

这里有趣的是，虽然随n而变，但当 n 很大时，几乎没有什么变化。（事实上，实际的数据显示，n =20已经可算“很大”了）。怎样看出这点来？这里我们要提到“自然对数”。这是以为底的对数函数。（有人将这写作或者）。它是怎样来的？最好的定义方法是：  是曲线与 x 轴在  和 之间的面积，如图(2)。这样说的话，就是的唯一的实数解。图中红色部分的面积为 1.

接下来，让我们继续看两幅图，

由（图3）可知，所有矩形的面积和：

而由（图4）可知，所有矩形的面积和：

经过简单的移项，可得：

所以, 与 的差在 之间，最多不过差1.

事实上当n增加时， 会有一个极限,这个极限叫做欧拉（Euler）常数,其值约为0.5772，即：

关于欧拉常数的证明，稍后会出现在blog上，有情趣的看管，可以前去查看。

所以，可以合理的做出假设：

根据式（5）：

当 n 很大时,(4)式中左右两边相差无几,(两边相差只一项。请注意(4)式的左边显示,当 n 很大时，r ^* 也必很大,否则左面就会超过1 ), 因此(4 )式可以大约写为：

因为，所以 

这时，大约是 

所以，使用该策略使得我们有近 0.36 的几率选到第一名。当n很大时，该策略的优越性不言而喻。

其实在计算的时候，也可以利用，化离散为连续的思想，当然需要一点技巧和高等数学的基础。

现在，我们令： （且此时，n 和 都很大）,则（2）式可化为 ^, 令，可得：,而由 可知，在这一点上取到最大值，即，当  时，取得到最大值，此时，,于之前得出的结论相同。

特别说明：

根据式（5）：

也许很多人会对上式中“约等于”的准确性有所疑问，但是事实是，上式用了两次（5）式的近似，当 n 和 r^* 很大的时候，（5）式左右两边的差十分趋向于欧拉常数，导致在对于两次近似的误差做减法的时候完全可以把这两个误差的差值视作为0.而对于 n 和 r* 都比较小的情况下，误差也许会很大，但是绝对是在可以接受的范围之内的，因为根据上面所说，在n很小时候，不是很能体现这种策略的优越性，因为和直接随机取得第一名的概率相差也不是很大。即使有误差，也不会离最佳策略的概率差很多。反过来说，当 n 很大时，我们用该策能很好的提高优越性之外，准确性也大幅提高。而准确性的提高又使得我们更佳地接近最终被优化的概率。希望下面的几幅图能给读者一个更形象的认识：

图（5）中，y轴上的 r* 是精确值，而不是估算值，可以看到，当 n 很大时，

图（6）是精确的 r* 与 n 的关系，可以看出，近似于一条斜率为 0.36 的直线。

图（7），是百分比误差与 n 的关系，可以明显看出，百分比误差随 n 的增大急剧减小。

图（8），是由在估算 r* 时造成误差引起概率的误差 与 n 的关系，同样可以看出，百误差随 n 的增大急剧减小。

至此，我们得出了一个比较优化的策略，使得我们取到第一名的概率提高了很多，但是，如果我们退而求其次，即，如果，我们取到实际的第一名或者第二名也满足胜利条件的，我们又会用什么更好的策略呢？如果存在这种策略，届时取到第一或第二的概率又会是多少呢？

（未完待续……）