### BdMO 2016 national

Posted:

**Wed Mar 28, 2018 8:03 pm**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....$

• 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....$