You are interviewing 6 candidates for a job. As you proceed, you determine the relative ranks of the candidates (you won't know the "true rank" until you have interviewed all of them). Thus, if there are 6 candidates with true rank \(6,1,4,2,3,5\), then after interviewing the first three candidates you would rank them \(3,1,2\).

Alas, after you interview a candidate, you either hire that person or the candidate leaves and can no longer be considered.

You want a strategy when to stop and accept a candidate, maximizing the likelihood of getting the best candidate. Assume there are 6 candidates, and they arrive in a random order.

a) What is the probability that you get the best candidate if you interview all of the candidates? What if you immediately choose the first candidate?

b) Say you adopt the strategy of interviewing the first half of the candidates and then accept the first of the following candidates who is better than any seen so far (if you have seen all the candidates so are at the last candidate then by these rules you must accept that person). Show (by a crude estimate) that you have a chance of less than \(50 \%\) of getting the the best candidate - but better than a \(25 \%\) chance of getting the the best candidate.