El secretario problema es un bien estudiado de la parada óptima problema con una solución simple. Supongamos que un conjunto de $N$ de los candidatos son entrevistados por una secretaría problema, de una en una, en orden aleatorio. Cada entrevistado debe ser aceptada en el acto o rechazado por buena. El objetivo es seleccionar el mejor candidato (es decir, el resultado es 1 si el mejor candidato es contratado, y 0 en caso contrario). Bajo estas condiciones, ¿cuál es la mejor política de contratación?
Como resulta, la estrategia óptima es la entrevista de la primera $N/e$ candidatos y los rechazan, y luego contratar al candidato siguiente que es mejor que todos esos. Sorprendentemente, esta estrategia conduce a la contratación de los mejores candidatos, uno de cada $e$ veces (o acerca de $37\%$ del tiempo), independientemente de $N$.
Ahora supongamos que, en lugar de ser entrevistado de una en una, las secretarias pueden ser entrevistados en grupos de hasta el $k$ (para algunos fijos $k>1$), después de que uno de los del grupo podrá ser aceptado en el lugar o en el de todo el grupo puede ser rechazado por buena. No es difícil ver que esta estrictamente aumenta la probabilidad de que la contratación de los mejores candidatos. La pregunta es, ¿por cuánto? ¿La probabilidad de hacer el mejor contratar aún tienden a $1/e$, o es que hay un no-cero ventaja sobre el $k=1$ de los casos en el límite de un gran $N$?
