You need a new staff assistant, and you have n people to interview. You want to hire the best candidate for the position. When you interview a candidate, you can give them a score, with the highest score being the best and no ties being possible. You interview the candidates one by one. Because of your company's hiring practices, after you interview the kth candidate, you either offer the candidate the job before the next interview or you forever lose the chance to hire that candidate. We suppose the candidates are interviewed in a random order, chosen uniformly at random from all n! possible orderings. We consider the following strategy. First, interview m candidates but reject them all; these candidates give you an idea of how strong the field is. After the mth candidate, hire the first candidate you interview who is better than all of the previous candidates you have interviewed. (a) Let E be the event that we hire the best assistant, and let Ei be the event that ith candidate is the best n 1 Pr(E) and we hire him. Determine Pr(Ei), and show that n 1 (b) Bound j=m+1 1 m == to obtain n n j=m+1 m (Inn - Inm) Pr(E) m (ln(n 1) In(m 1)) n (c) Show that m(In n - In m)/n is maximized when m = n/e, and explain why this means Pr(E) > 1/e for this choice of m.