비서 문제 · 상자 속의 우주

멈추는 순간의 딜레마The stopping dilemma

너무 일찍 뽑으면 뒤에 더 좋은 사람이 있었을지 모릅니다. 너무 오래 기다리면 최고를 이미 거절해버렸을 수 있습니다. 이건 채용뿐 아니라 집 구하기, 주차 자리 찾기, 심지어 배우자 고르기까지 관통하는 문제입니다.

Hire too early and someone better may come later. Wait too long and you may have already rejected the best. This runs through hiring, apartment-hunting, finding a parking spot: even choosing a partner.

놀랍게도 최적 전략은 깔끔합니다:

Remarkably, the optimal strategy is clean:

37% 법칙: 처음 N/e ≈ 37%는 무조건 거절하되 기준점으로 관찰만 한다. 그 후, 지금까지 본 누구보다 나은 첫 사람이 나오면 즉시 뽑는다. 이러면 최고를 뽑을 확률이 약 1/e ≈ 37%가 되며, 이보다 잘하는 방법은 없습니다. The 37% rule: reject the first N/e ≈ 37% no matter what, using them only to set a benchmark. After that, hire the first person better than everyone seen so far. This gives about a 1/e ≈ 37% chance of getting the best: and no strategy does better.

지원자가 많아져도 이 확률은 37% 아래로 떨어지지 않습니다. "3분의 1만 버려라"가 마법의 숫자인 셈이죠.

Even with many applicants, this probability never drops below 37%. "Throw away the first third" is the magic number.

🧑‍💼 직접 채용해 보기🧑‍💼 Hire someone yourself

관찰 단계 비율을 바꿔가며 한 번 실행 / 1000번 실행을 눌러보세요Vary the observation ratio, then try Run once / Run 1000×

지원자 수 NApplicants N

관찰 단계 비율Observation ratio

관찰 단계 (거절)Observation (rejected)

–

뽑은 사람 순위Hired person's rank

–

이번 결과This result

–

1000번 성공률Success over 1000

–

관찰 단계 (무조건 거절)Observation (always reject) 채용 단계 (거절)Hiring phase (rejected) 채용!Hired! 마지막 사람 강제 채용Forced to hire the last 놓친 진짜 1등The true best, missed

📈 성공률은 몇 %에서 최고가 될까?📈 At what % is success highest?

모든 관찰 비율(0~90%)에 대해 자동으로 실험해 곡선을 그립니다Auto-runs every observation ratio (0–90%) and plots the curve

봉우리가 37% 근처에 생기는지 확인하세요Check that the peak forms near 37%

스스로 확인할 것See for yourself

① 관찰 비율을 0%로. 첫 사람을 무조건 뽑게 됩니다 → 최고일 확률은 1/N, 즉 지원자가 많을수록 처참합니다.

① Set the observation ratio to 0%. You always hire the first person → the chance it's the best is 1/N, dismal when there are many applicants.

② 관찰 비율을 90%로. 거의 다 관찰만 하다가 끝 무렵 아무나 급하게 뽑게 되어 또 실패가 잦습니다.

② Set it to 90%. You observe almost everyone, then grab whoever's left at the end: failure is common again.

"기준을 넘는 사람이 끝까지 안 나오면?" 규칙상 반드시 한 명은 뽑아야 하므로, 어쩔 수 없이 맨 마지막 지원자를 강제로 채용합니다(주황색 표시). 특히 진짜 1등이 관찰 구간 안에 있었다면, 그 사람이 곧 기준이 되어 이후엔 아무도 넘지 못하므로 무조건 실패합니다. 관찰을 너무 오래 할수록 이 사고가 잦아지고, 그래서 성공률 곡선이 37%를 지나면 다시 떨어집니다. "What if no one ever beats the benchmark?" The rules force you to hire someone, so you're stuck with the very last applicant (shown in orange). In particular, if the true best was inside the observation window, they become the benchmark and no one after can beat it: guaranteed failure. The longer you observe, the more often this happens, which is why the success curve falls again past 37%.

③ "37%로 맞추기"를 누르고 1000번 실행. 성공률이 약 37%로 수렴합니다. 곡선을 그려보면 봉우리가 정확히 그 지점에 있습니다. 극단은 둘 다 나쁘고, 답은 가운데의 특정 지점입니다. ③ Press "Set to 37%" and run 1000 times. The success rate converges to about 37%. Plot the curve and the peak sits exactly there. Both extremes are bad; the answer is a specific point in the middle.

왜 하필 37%(1/e)일까?Why exactly 37% (1/e)?

가볍게 따라가 봅시다. 지원자가 아주 많다고 보고, 전체의 비율 x만큼을 관찰 단계로 버린다고 하죠. 최고를 뽑을 확률은 서로 반대로 당기는 두 힘의 곱으로 정해집니다.

Let's follow it lightly. Suppose there are very many applicants and you discard a fraction x as the observation phase. The chance of hiring the best is set by two forces pulling in opposite directions.

관찰을 길게 할수록(x↑) 더 믿을 만한 기준이 생겨 성급하게 뽑는 실수가 줄어듭니다 → 유리
하지만 너무 길면 진짜 1등이 관찰 구간에서 이미 지나가 버릴 위험이 커집니다 → 불리

The longer you observe (x↑), the more reliable your benchmark, so fewer hasty mistakes → helps
But too long and the true best has likely already passed during observation → hurts

이 줄다리기는 직접 세어보면 식이 됩니다. 지원자가 n명이고, 앞의 k명은 관찰만 하고 보낸다고 하죠(x = k/n). 성공은 딱 한 가지, 진짜 1등을 뽑는 것입니다. 그러니 1등이 몇 번째로 오느냐로 나눠서 세면 됩니다.

Counting it out turns this tug-of-war into a formula. Say there are n applicants and the first k are observed and let go (x = k/n). Success means one thing, hiring the actual best. So it can be counted by where in the line the best arrives.

① 1등이 i번째에 올 확률은 1/n입니다. 순서가 무작위라 어느 자리나 똑같습니다.

① The best arrives at position i with probability 1/n. The order is random, so every seat is equally likely.

② 1등이 i번째에 있을 때, 그 앞에서 멈추지 않을 확률은 k/(i−1)입니다. 규칙은 관찰이 끝난 뒤 "지금까지 최고"가 나오면 바로 멈추는 것이었죠. 그러니 i번째까지 아무도 뽑지 않으려면, k+1번째부터 i−1번째 사이에 "지금까지 최고"가 한 명도 없어야 합니다. 이건 앞의 i−1명 중 최고가 관찰 구간 안에 있다는 말과 같습니다. 그 최고도 i−1개 자리 어디에나 똑같이 앉으니, 앞의 k자리에 앉을 확률은 k/(i−1)이고요.

② Given the best sits at i, the chance of not stopping before it is k/(i−1). The rule was to stop at the first applicant who beats everyone seen so far. So reaching position i without hiring anyone means nobody between k+1 and i−1 was a new leader. That is the same as saying the best of the first i−1 fell inside the observed block. That one is equally likely to sit anywhere among the i−1 seats, so it lands in the first k with probability k/(i−1).

③ 두 확률을 곱하고, 1등이 앉을 수 있는 자리를 전부 더합니다.

③ Multiply the two, then add over every seat the best could take.

P = Σ (1/n)·(k/(i−1)) = (k/n) · Σ 1/(i−1)

④ 뒤에 남은 합은 로그가 됩니다. 1/k부터 1/(n−1)까지 더한 값은 곡선 1/t 아래 넓이에 가깝습니다. k부터 n까지 그 넓이가 바로 ln(n/k)예요.

④ The sum that is left becomes a logarithm. Adding 1/k through 1/(n−1) is close to the area under the curve 1/t. From k to n that area is ln(n/k).

1/k + ⋯ + 1/(n−1) ≈ ∫ dt/t = ln(n/k)

k/n을 x로 썼으니 ln(n/k)는 ln(1/x)입니다. 앞에 남은 k/n도 곧 x고요. 그래서 지원자가 아주 많을 때 성공 확률은 x와 ln(1/x)의 곱이 됩니다. 관찰을 늘리면 앞의 x는 커지고 뒤의 ln(1/x)는 작아지죠. 줄다리기가 그대로 곱으로 나타난 셈입니다.

Since k/n was written as x, ln(n/k) is ln(1/x), and the k/n left in front is x too. So with very many applicants the success probability is x times ln(1/x). Observing longer grows the x in front and shrinks the ln(1/x) behind it. The tug-of-war shows up as a product.

P(x) ≈ −x · ln x

이제 이 값을 가장 크게 만드는 x만 찾으면 됩니다. 미분해서 0으로 놓으면:

Now just find the x that maximizes it. Differentiate and set it to zero:

P′(x) = −(ln x + 1) = 0 ⟹ ln x = −1 ⟹ x = 1/e ≈ 0.368

두 번 놀라는 지점: 최적의 관찰 비율이 1/e ≈ 37%인 것도 놀랍지만, 바로 그 순간의 성공 확률마저 P(1/e) = 1/e ≈ 37%로 똑같습니다. 게다가 이 값은 지원자가 100명이든 100만 명이든 거의 변하지 않습니다. 위 그래프의 보라색 점선이 바로 이 −x·ln x 곡선이며, 직접 그린 실험 곡선과 봉우리가 같은 자리에서 만납니다. Two surprises at once: not only is the optimal observation ratio 1/e ≈ 37%, but the success probability at that point is also P(1/e) = 1/e ≈ 37%. And this barely changes whether there are 100 applicants or a million. The purple dashed line in the graph above is exactly this −x·ln x curve, and it meets the experimental curve at the same peak.

누가 만든 문제일까?Who came up with this?

이 문제는 한 사람이 뚝딱 낸 게 아니라, 여러 수학자를 거치며 다듬어졌습니다. 널리 알려진 계기는 1960년 2월 마틴 가드너(Martin Gardner)가 Scientific American의 'Mathematical Games' 칼럼에 "게임 오브 구골(game of googol)"이라는 이름으로 소개한 것입니다. 문제 자체의 착상은 그보다 앞서 메릴 플러드(Merrill M. Flood)가 1940~50년대에 제기한 것으로 여겨집니다.

No single person invented it in one shot, it was shaped by several mathematicians. It became widely known in February 1960, when Martin Gardner presented it in his 'Mathematical Games' column in Scientific American as the "game of googol." The underlying idea is generally credited to Merrill M. Flood, who posed versions of it in the 1940s–50s.

1/e 라는 깔끔한 답은 1960년대 초 여러 수학자가 잇따라 증명했습니다. 데니스 린들리(Dennis Lindley, 1961), 유진 딘킨(Eugene Dynkin, 1963), 그리고 길버트와 모스텔러(Gilbert & Mosteller, 1966)의 정밀한 분석이 대표적입니다. 그 뒤로 이 문제는 '최적 정지(optimal stopping)' 이론의 교과서적 출발점이 되었고, '결혼 문제', '술탄의 지참금 문제' 같은 여러 별명으로도 불립니다. The clean 1/e answer was proved by several people in the early 1960s, notably Dennis Lindley (1961), Eugene Dynkin (1963), and the thorough analysis of Gilbert & Mosteller (1966). The problem became a textbook starting point for optimal stopping theory, and goes by several nicknames, the "marriage problem" and the "sultan's dowry problem" among them.

이름이 "비서 문제"인 건, 지원자를 한 명씩 면접해 즉석에서 채용/거절을 결정하는 상황이 이 규칙과 딱 맞았기 때문입니다. 본질은 채용이 아니라 "되돌릴 수 없는 순차적 선택에서 언제 멈출 것인가"라는, 삶 곳곳에 숨은 물음입니다.

The name "secretary problem" stuck because interviewing applicants one by one (hiring or rejecting on the spot) fits the rules perfectly. But the real question isn't about hiring; it's "when to stop in an irreversible, sequential choice", a question hiding all over life.