A sultan has granted a commoner a chance to marry one of his 
daughters. The commoner will be presented with the daughters
one at a time and, when each daughter is presented, the commoner will be told the
daughter's dowry (which is fixed in advance). Upon being presented with a daughter,
the commoner must immediately decide whether to accept or reject her (he is not allowed
to return to a previously rejected daughter). However, the sultan will allow the
marriage to take place only if the commoner picks the daughter with the overall highest
dowry. Then what is the commoner's best strategy, assuming he knows nothing about
the distribution of dowries (Mosteller 1987)?
Since the commoner knows nothing about the distribution of the dowries, the best strategy is to wait until a certain number 
of daughters have been presented, then pick the highest dowry
thereafter (Havil 2003, p. 134). The exact number to skip is determined by the
condition that the odds that the highest dowry has already been seen is just greater
than the odds that it remains to be seen and that if it is seen it will be picked.
This amounts to finding the smallest 
such that
 |
(1)
|
More specifically, the probability of obtaining the maximum dowry after waiting for 
out of 
daughters is
 |
(2)
|
where 
is a harmonic number (Havil 2003, p. 137),
plotted above for a number of specific values of 
as a function of 
(left figure above) and as a surface plot in 
and 
(right figure).
The solution is therefore the smallest 
such that
 |
(3)
|
Solving,
 |
(4)
|
numerically and taking the ceiling function ![[x]](/images/equations/SultansDowryProblem/Inline12.svg)
then gives the solutions 0, 1, 1,
2, 2, 2, 3, 3, 3, 4, 4, 5, 5, 5, ... (OEIS A054404)
for 
,
2, ... daughters.
Surprisingly, the convergents for the continued fraction of 
,
given by 0, 1/2, 1/3, 3/8, 4/11, 7/19, 32/87, 39/106, 71/193, 465/1264, ... (OEIS
A007676 and A007677),
correspond exactly to pairs 
, where 
is the optimal value for 
daughters (Havil 2003, p. 137).
An approximate solution can be obtained by using a series expansion for 
about infinity,
 |
(5)
|
where 
is the Euler-Mascheroni constant, and
plugging this approximation into (4), giving
 |
(6)
|
This can be solved in closed form to give an approximate solution to 
,
 |
(7)
|
where 
is the Lambert W-function. In fact, taking
![[x^^_1]](/images/equations/SultansDowryProblem/Inline22.svg)
gives the correct result for 
.
Another approximation can be obtained by taking a series expansion of 
to obtain
 |
(8)
|
Taking the derivative and setting equal to 0 then gives
![x^^_2=ne^(-[1+1/(2n)]),](/images/equations/SultansDowryProblem/NumberedEquation9.svg) |
(9)
|
which is within 1 of the correct answer for all 
.
The plot above illustrates these two approximations (red and blue curves) together with the actual values (black dots). Both approximations have series expansions of the form
 |
(10)
|
where 
and 
are small constants.
The problem is most commonly stated with 
daughters, which gives the result that the commoner should
wait until he has seen 37 of the daughters, then pick the first daughter with a dowry
that is bigger than any preceding one. With this strategy, his odds of choosing the
daughter with the highest dowry are surprisingly high: about 
(Honsberger 1979, pp. 104-110, Mosteller 1987; Havil
2003, p. 136). As the number of daughters increases, this tends towards 
(OEIS A068985).
