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(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 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%For more information I suggest section 2.5 of Probability and Statistics, second edition by Morris H. DeGroot.
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 maxx 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 maxx ) * (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. max30 is the largest dowry of the first 30 ladies. Let Pr(ni) equal the probability that there are i ladies left with a dowry greater than maxx. The probability of you winning would be:
Pr(n1) * 1 +
Pr(n2) * 1/2 +
Pr(n3) * 1/3 +
Pr(n4) * 1/4 +
Pr(n5) * 1/5 +
.
.
.
Pr(n70) * 1/70.
To derive Pr(ni) 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(n3) = 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.