Aasma 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 $H$ be the 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.
Aasma wants to find the value of $k$ for which she has the highest possibility 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 Aasma will chose the $(m+1)th$ person using this algorithm?
- $(d)(16\; points)$ The total probability that Aasma will chose the highest tanking 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 $$\ln N = \frac{1}{N-1} + \frac{1}{N-2} + \cdots + \frac{1}{2} + \frac{1}{1} $$
- $(e)(6\; points)$ Find that value of $k$ that maximizes the probability of chossing 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.....$
Actually I didn't even get much time to read the problem, let alone solving it. I didn't even get the meaning of this problem. Any partial solution (in comment) or full solution will be helpful.
Note: This is a problem from BdMO $2016$ National Secondary $7/8$ and Higher Secondary $7/9$.