Maximize Dowry

The king has 100 young ladies in his court each with an individual dowry. No two dowrys are the same. The king says you may marry the one with the highest dowry if you correctly choose her. The king says that he will parade the ladies one at a time before you and each will tell you her dowry. Only at the time a particular lady is in front of you may you select her. The question is what is the strategy that maximizes your chances to choose the lady with the largest dowry?


Answer:

You should let x ladies go by and choose the first one with a dowry greater than the maximum of the first x. Of course you will pass the highest one if she is among the first x, but that is part of the game. Let x be the number of ladies you pass before choosing the next lady with a dowry greater than the first x ladies. Let max(x) be the maximum dowry in the first x ladies.
The probability of winning is sum for i=(x+1) to 100 of the probability that the highest dowry is in the ith position multiplied by the probability that you choose it if it is in that position.
This is based on the condition probability formula: Pr(A)=Sum for i=1 to n of Pr( A Bi ) * Pr( Bi ), where the sum for i=1 to n of Pr(Bi)=1.
For all i the probability that the highest dowry is in that position is 1/100.
The probability that you will choose the dowry if it is in the ith position is equal to the probability that the highest of the first i-1 dowries belongs to one of the first x ladies. This equals x/(i-1). If the highest dowry of the first i-1 were not in the first x ladies you would choose it before getting to the largest dowry, thus losing the game.
For example if you let 30 ladies pass the probability that the highest dowry is in the 75th postion and that you will choose it equals 1/100 * 30/74.
Let A denote the overall probability of winning. The proability of winning given x is the sum for i=x+1 to 100 of x/(i-1) * 1/n. This equals:
Pr(1/n * [ 1 + x/(x+1) + x/(x+2) + ... + x/99 ] ).
Some value of x must be optimal to maximize this formula. This value of x must the first such that Pr(Ax+1) - Pr(Ax) < 0.
Pr(Ax+1) - Pr(Ax) = 1/n * [ 1/(x+2) + 1/(x+3) + 1/(x+4) + ... + 1/99 - x/(x+1) ].
let y=x+1.
Pr(Ax+1) - Pr(Ax) = 1/n * [ 1/(y+1) + 1/(y+2) + 1/(y+3) + ... + 1/99 - (y-1)/y ]. =
Pr(Ax+1) - Pr(Ax) = 1/n * [ 1/(y+1) + 1/(y+2) + 1/(y+3) + ... + 1/99 - 1 + 1/y ]. =
Pr(Ax+1) - Pr(Ax) = 1/n * [ 1/y + 1/(y+1) + 1/(y+2) + 1/(y+3) + ... + 1/99 - 1 ].
If Pr(Ax+1) - Pr(Ax) = 0, then 1/y + 1/(y+1) + 1/(y+2) + 1/(y+3) + ... + 1/99 = 1.
Theorem: The integral from r to n of 1/x = log(n) - log(r) = log(n/r).
The equation above the theorm is an approximation of the integral in the theorem. By applying the theorem log(100/y) = 1.
Taking e to the power of both sides: 100/y = e.
y=100/e.
Since e=~2.7182818 y=~36.79, since x=y-1 x=~35.79.
Since the integral is an underestimate of the series look at some specific values of Pr(A) for values of x close to 35.79:
x A
--- ---
35 37.0709%
36 37.1015%
37 37.1043%
38 37.0801%
So the optimal strategy is to let 37 ladies pass and then choose the first lady with a dowry larger than the greatest of the first 37.
In general the answer is going to be n/e, where n is the total number of ladies. Because the answer must be an exact integer and error in applying the theorem mentioned above you should check the few integers just above the optimal value. As n increases the error decreases. The probability of winning turns out to approach 1/e =~ 36.79% as n approaches infinity (I'll leave this proof up to you).
Here are some optimal values of x for various values of n and the probability of winning given x:
n x Pr(winning)
----------------------------- -----------
3 2 50.00%
4 2 43.83%
5 3 43.33%
6 3 42.78%
7 3 41.43%
8 4 40.98%
9 4 40.60%
10 4 39.87%
15 6 38.94%
20 8 38.42%
30 12 37.87%
50 19 37.42%
100 38 37.10%
1000 369 36.82%