100 candidates are interviewed one at a time in random order, and after each you know only its rank among those seen so far. Accept or reject on the spot with no recall, and you win only by taking the single best of all 100. Under the rule that rejects the first k and then takes the first candidate better than all of them, what k is optimal?

100 candidates are interviewed one at a time in random order, and after each you know only its rank among those seen so far. Accept or reject on the spot with no recall, and you win only by taking the single best of all 100. Under the rule that rejects the first k and then takes the first candidate better than all of them, what k is optimal?

Approach: Write the win probability as a sum over the position of the overall best candidate, requiring the best of everything before it to fall inside the rejected block.

37. Under the cutoff rule you win when the best candidate sits at position i > k and the best of the first i - 1 lies inside the rejected block, which happens with probability (k/n) * sum_{i=k+1}^{n} 1/(i-1). For large n this is approximately x ln(1/x) with x = k/n, and differentiating gives x = 1/e, so k is near 100/e = 36.8. Evaluating the exact sum at n = 100 gives 0.3710 at k = 37, marginally above k = 36 and k = 38, so 37 is the optimal stopping cutoff. The win probability tends to 1/e = 0.3679 as n grows, so the chance of taking the single best does not shrink to zero with the field size.

Follow-up: If you win by taking either the best or the second best candidate, what does the optimal rule look like?

Key concepts: optimal stopping, cutoff rule, 1/e law.