최적 멈춤(비서 문제) 계산기

n명의 후보를 한 명씩 만나되 그 자리에서 뽑거나 보내야 하고, 한 번 보낸 사람은 다시 부를 수 없을 때 최고를 뽑을 확률을 최대로 하는 문제입니다. 만나 보면 지금까지 본 사람들과의 우열은 알 수 있지만 앞으로 올 사람은 모른다고 봅니다. 집 구하기, 면접, 주차 자리 고르기가 같은 구조입니다.

앞 r−1명을 보내고 r번째부터 «지금까지 최고»를 만나면 즉시 고릅니다. 성공확률은 P(r) = (r−1)/n × Σ_{i=r}^{n} 1/(i−1)이며, 이 계산기는 r을 1부터 n까지 실제로 계산해 가장 큰 것을 찾습니다. n=100이면 r=38, 즉 앞 37명을 보내는 것이 최적입니다.

n이 클 때만 맞습니다. n이 커지면 최적 r/n이 1/e = 0.3679로 수렴하지만 n이 작으면 다릅니다. n=3이면 최적 r이 2(r/n = 0.667)이고, n=4에서 «4/e = 1.47이니 1»로 잡으면 성공확률이 0.25로 최적 0.458의 절반 남짓으로 떨어집니다. 그래서 이 계산기는 근사식을 쓰지 않습니다.

정보가 늘어나는 만큼 고를 기회도 늘어나 서로 상쇄되기 때문입니다. 후보가 100명이든 100만 명이든 최고를 잡을 확률이 3분의 1을 넘습니다. 직관과 어긋나는 이 결과가 이 문제를 유명하게 만들었습니다.

그렇지 않습니다. 이 전략은 «최고를 잡을 확률»만 최대로 하며, 실패했을 때는 아주 나쁜 사람을 집습니다. 앞 구간 안에 전체 최고가 있으면 끝까지 아무도 못 만나 마지막 사람을 억지로 데려가기 때문입니다. n=1,000이면 최고를 잡을 확률은 36.8%지만 뽑는 사람의 기대 순위는 185등입니다.

훨씬 일찍 고르기 시작해야 합니다. n=1,000이면 r=32(앞 31명만 보기)가 기대 순위 31등으로 가장 좋은데, 대신 최고를 잡을 확률은 10.8%로 떨어집니다. 목적이 다르면 답도 다르며, 「37% 규칙」을 «평균적으로 좋은 선택을 하는 법»으로 소개하는 글은 두 문제를 섞은 것입니다.

그럴 필요 없습니다. 성공확률 곡선이 최적 근처에서 뭉툭해서 조금 벗어나도 확률이 크게 떨어지지 않습니다. n=100이면 r을 33에서 42 사이에 두면 최적의 99% 이상이고, 30~45로 넓혀도 97% 이상입니다. 실전에서 «대충 3분의 1쯤»으로 해도 되는 이유입니다.

조건이 좁습니다. 후보의 점수는 모르고 우열만 안다고 보며, 순서가 무작위여야 하고, 보낸 사람은 다시 부를 수 없고, 뽑겠다고 하면 반드시 승낙한다고 봅니다. 현실에서는 이 중 여러 개가 깨집니다. 다만 «충분히 보기 전에는 고르지 마라, 그러나 끝까지 재지도 마라»는 뼈대는 남습니다.

있지만 이 계산기의 규칙과 모양이 다릅니다. 여기서 내는 «평균 순위 최적»은 앞 r−1명을 무조건 보내는 같은 모양의 규칙 안에서만 최적입니다. 기대 순위를 진짜로 최소화하는 정책은 시간이 갈수록 눈높이를 낮추는 규칙이며, 그때 기대 순위는 n이 아무리 커져도 3.87 근처에 머뭅니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이루어지며 입력값은 이 기기에만 남습니다.