(10 marks) We need to hire a new staff. There are n applicants for this job. Assume that we will know how good they are (as a score) when we interview them, and the score for each applicant is different. So there is a unique candidate with the highest score, but we don't know that the applicant is the best when we interview him/her until we have interviewed all the applicants. The problem is that after we interview one applicant, we need to make an online decision to either give him/her an offer or forever lose the chance to hire that applicant. Suppose the applicants come in a random order (i.e. a uniformly random permutation), and we would like to come up with a strategy to hire the best applicant. Consider the following strategy. First, interview m applicants but reject them all. Then, after the m-th applicant, hire the first applicant you interview who is better than all of the previous applicants that you I have interviewed. Let E be the event that you hire the best applicant. Let E; be the event that the i-th applicant is the best and you hire him/her. Compute Pr(E) and show that Pr(E) n = M n 1 j=m+1 Then, show that Pr(E) m (Inn - Inm), and that Pr(E) can be arbitrarily close to 1/e for an appropriate choice of m when n tends to infinity.