MathDB

Juli is a mathematician and devised an algorithm to find a husband. The strategy is: • Start interviewing a maximum of

1000

prospective husbands. Assign a ranking

r

to each person that is a positive integer. No two prospects will have same the rank

r

. • Reject the first

k

men and let

H

be highest rank of these

k

men. • After rejecting the first

k

men, select the next prospect with a rank greater than

H

and then stop the search immediately. If no candidate is selected after

999

interviews, the

1000th

person is selected.
Juli wants to find the value of

k

for which she has the highest probability of choosing the highest ranking prospect among all

1000

candidates without having to interview all

1000

prospects. (a) (6 points:) What is the probability that the highest ranking prospect among all

1000

prospects is the

(m + 1)th

prospect? (b) (6 points:) Assume the highest ranking prospect is the

(m + 1)th

person to be interviewed. What is the probability that the highest rank candidate among the first

m

candidates is one of the first

k

candidates who were rejected? (c) (6 points:) What is the probability that the prospect with the highest rank is the

(m+1)th

person and that Juli will choose the

(m+1)th

man using this algorithm? (d) (16 points:) The total probability that Juli will choose the highest ranking prospect among the

1000

prospects is the sum of the probability for each possible value of

m+1

with

m+1

ranging between

k+1

and

1000

. Find the sum. To simplify your answer use the formula

In N \approx \frac{1}{N-1}+\frac{1}{N-2}+...+\frac{1}{2}+1

(e) (6 points:) Find that value of

k

that maximizes the probability of choosing the highest ranking prospect without interviewing all

1000

candidates. You may need to know that the maximum of the function

x ln \frac{A}{x-1}

is approximately

\frac{A + 1}{e}

, where

A

is a constant and

e

is Euler’s number,

e = 2.718....

Problem Statement