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 | B_{i} ) * Pr( B_{i} ),
where the sum for i=1 to n of Pr(B_{i})=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(A|x+1) - Pr(A|x) < 0.

Pr(A|x+1) - Pr(A|x) = 1/n * [ 1/(x+2) + 1/(x+3) + 1/(x+4) + ... + 1/99 - x/(x+1) ].

let y=x+1.

Pr(A|x+1) - Pr(A|x) = 1/n * [ 1/(y+1) + 1/(y+2) + 1/(y+3) + ... + 1/99 - (y-1)/y ]. =

Pr(A|x+1) - Pr(A|x) = 1/n * [ 1/(y+1) + 1/(y+2) + 1/(y+3) + ... + 1/99 - 1 + 1/y ]. =

Pr(A|x+1) - Pr(A|x) = 1/n * [ 1/y + 1/(y+1) + 1/(y+2) + 1/(y+3) + ... + 1/99 - 1 ].

If Pr(A|x+1) - Pr(A|x) = 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

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%For more information I suggest section 2.5 of

**Here another version of my solution to this problem**

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 you will select the highest dowry is:

Sum for i=1 to 100-x of: ( Probability that i of the
remaining ladies will have a dowry greater than max_{x} )
* (1/i).

This probability for any i is:

(100-x)*(99-x)*(98-x)*...*(101-x-i) * x --------------------------------------- 100*99*98*...*(100-i)For example suppose you let 30 ladies go my first and planned to choose the next one with a dowry greater than the maximum of the first 30. max

Pr(n_{1}) * 1 +

Pr(n_{2}) * 1/2 +

Pr(n_{3}) * 1/3 +

Pr(n_{4}) * 1/4 +

Pr(n_{5}) * 1/5 +

.

.

.

Pr(n_{70}) * 1/70.

To derive Pr(n_{i}) consider the probability that the i highest
dowrys fall in the last 100-x ladies, multiplied the the probability that
the (i+1)th highest dowry falls in the first x ladies. For example:

Pr(n_{3}) = 70/100 * 69/99 * 68/98 * 30/97.

70/100 = Probability that the highest dowry is not in first 30.

69/99 = Probability that the second highest dowry is not in first 30 (99 positions left, 69
not if first 30).

68/98 = Probability that the third highest dowry is not in first 30.

30/97 = Probability that fourth highest dowry is in first 30.

Personally I had to use a spreadsheet to find that the maximum probability was for x=37, which was 37.1%.

If you change the number of total ladies from 100 to any other number the strategy seems to still be to let 37% of them go by first.

Michael Shackleford, A.S.A.