Marriage Problem

If you are in Hong Kong and you need help for university mathematics courses, please visit www.all-r-math.com.

女孩：我想知道姻緣。
相士：您一生會遇到十個要娶您的男人。
女孩：哪一個是最好？
相士：天機不可涉漏！
女孩：！！！

Girl: I want to know my future.
Fortuneteller: I see. You will meet ten men that want to marry you. 
Girl: Who will be the best?
Fortuneteller: Oh, I just can't tell!
Girl: !!!

In many Hong Kong old films, there is a know-all who loves to do fortunetelling but hold back the most important bit, and hence tragedy happens.

As the story goes, several guys have proposed to the girl, but she refuses as she dreams to have a better one coming.  The latter are worse and worse. As the magical "ten" approaches, she panics and gets married, and it turns out the best is just around the corner.

Not really too tragic. However, if the girl knows some mathematics, she may have a higher chance to marry the best one: She should refuse the first three men and she must marry once she meet a guy who is better than the first three men.

Using this strategy, her chance of marrying the best one is $0.44$, whereas if she makes her decision randomly, her chance is just $0.10$.

In general, suppose the girl knows that there will be $N$ men and she marries the first one who is better than the first $k$ guys, then her chance of marrying the best one is $$\frac{k}{N}\sum_{i=k}^{N-1}\frac{1}{n}.$$
How do we come up with this probability?
Well, the probability that the $(i+1)$-th one is the best is $\frac{1}{N}$. In this case, the girl may marry him only if the best among the first $i$ guys is one of the first $k$ guys, and hence the probability is $\frac{k}{i}$.
To find the optimal $k$ is not easy for large $N$, but it is not that hard to see that (Can you do it?) $$(N-\frac34)^{1/2}-\frac14\le k\le \frac{N}{2}.$$ In our case, $N=10$ and the optimal $k$ is $3$.

The mathematics problem has a name: Marriage Problem. (Note there are other mathematics problems of the same name.) Its another name is Secretary Problem.

Lets end this with one very important point: The girl can achieve the highest probability only if she sticks with the strategy!