苏丹嫁妆问题

一位苏丹给予一位平民机会娶他 个女儿中的一位。这位平民将一次见到一位女儿，并且当每位女儿被介绍时，平民将被告知女儿的嫁妆（嫁妆是预先确定的）。当被介绍一位女儿时，平民必须立即决定接受还是拒绝她（他不能回到之前拒绝过的女儿）。然而，只有当平民选择了嫁妆总额最高的女儿时，苏丹才会允许婚姻发生。那么，假设他对嫁妆的分布一无所知（Mosteller 1987），平民的最佳策略是什么？

由于平民对嫁妆的分布一无所知，最佳策略是等待直到一定数量 的女儿被介绍之后，再选择之后遇到的嫁妆最高的女儿（Havil 2003, p. 134）。要跳过的确切数量由以下条件确定：最高嫁妆已经被看到的几率略高于它仍然有待被看到并且如果它被看到将被选中的几率。这相当于找到最小的 使得

更具体地说，在等待了 位女儿之后，在总共 位女儿中获得最高嫁妆的概率是

其中 是一个 调和数 (Havil 2003, p. 137)，上面绘制了一些特定的 值，作为 的函数（上左图），以及在 和 中的表面图（右图）。

因此，解决方案是最小的 使得

解得，

数值求解并取 上限函数 ，然后给出对于 , 2, ... 个女儿的解为 0, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 5, 5, 5, ... (OEIS A054404)。

令人惊讶的是， 的 连分数 的收敛值，由 0, 1/2, 1/3, 3/8, 4/11, 7/19, 32/87, 39/106, 71/193, 465/1264, ... (OEIS A007676 和 A007677) 给出，与数对 完全对应，其中 是对于 个女儿的最佳值 (Havil 2003, p. 137)。

可以通过使用 在无穷远处的级数展开获得近似解，

其中 是 欧拉-马歇罗尼常数，并将此近似代入 (4)，得到

这可以以闭合形式求解，以给出 的近似解，

其中 是 兰伯特W函数。事实上，取 对于 给出了正确的结果。

另一种近似可以通过取 的级数展开来获得，得到

对上述式子求导并设为 0，然后得到

对于所有 ，这都在正确答案的 1 以内。

上面的图说明了这两个近似值（红色和蓝色曲线）以及实际值（黑点）。这两个近似都具有以下形式的级数展开

其中 和 是小常数。

这个问题最常见的表述是 个女儿，这给出的结果是，平民应该等到他见过 37 个女儿之后，再选择第一个嫁妆比之前任何一个都大的女儿。使用这种策略，他选择嫁妆最高女儿的几率出奇地高：大约 (Honsberger 1979, pp. 104-110, Mosteller 1987; Havil 2003, p. 136)。随着女儿数量的增加，这个概率趋于 (OEIS A068985)。