스무고개는 스무 번이면 100만 개 중 하나를 찾습니다 — 반씩 나누는 질문의 힘

왜 반씩 나누는 질문이 최선인가

"예"와 "아니오" 중 어느 답이 나올지 반반인 질문을 받으면, 답을 듣는 순간 모르던 것의 절반이 사라집니다. 이 양을 1비트라고 부릅니다. 예/아니오 질문 하나로 얻을 수 있는 정보의 최대치입니다.

질문이 치우치면 받는 정보가 줄어듭니다. 예를 들어 "예"가 나올 확률이 10%뿐인 질문을 생각해 보세요. 대부분 "아니오"가 나오고, 그러면 후보가 10%만 걸러집니다. 이런 질문이 주는 평균 정보는 계산하면 0.469비트, 반반 질문의 절반도 안 됩니다.

100만 개 중 하나를 찾는 데 필요한 정보는 log₂(1,000,000) = 19.93비트입니다. 1비트짜리 질문이면 20번이면 되는 이유가 여기 있습니다. 1,000개는 9.97비트라 10번, 100개는 6.64비트라 7번입니다.

치우친 질문은 얼마나 손해일까

100만 개에서 시작해, 매 질문이 후보를 같은 비율로 가른다고 두고 평균 질문 수를 정확히 계산했습니다. "최악"은 답이 매번 큰 쪽으로 떨어지는 경우입니다.

질문이 가르는 비율	질문 하나의 정보량	평균 질문 수	최악
50 : 50	1.000비트	19.95번	20번
40 : 60	0.971비트	20.52번	27번
30 : 70	0.881비트	22.49번	37번
20 : 80	0.722비트	27.29번	59번
10 : 90	0.469비트	40.97번	118번
5 : 95	0.286비트	65.47번	231번

두 가지가 눈에 띕니다.

첫째, 꼭 정확히 반이 아니어도 됩니다. 60:40으로 갈라도 평균 20.52번, 반반보다 0.6번 더 들 뿐입니다. 스무고개에서 "살아 있는 건가요?" 같은 질문이 쓸 만한 이유입니다. 딱 반은 아니어도 한쪽으로 크게 쏠리지 않는 편이니까요.

둘째, 많이 치우치면 급격히 나빠집니다. 90:10 질문은 평균 40.97번으로 두 배가 넘고, 최악에는 118번이 듭니다. "혹시 빨간색인가요?"처럼 맞으면 크게 좁혀지지만 대개 아니라고 나오는 질문이 여기에 해당합니다.

평균값이 맞는지 보려고 90:10 질문만 하는 경우를 20만 번 돌려 봤습니다(시드 고정). 평균 40.93번, 중앙값 39번, 열 번 중 한 번은 56번 이상 걸렸고 가장 길었던 판은 109번이었습니다. 운 좋게 "예"가 연달아 나오면 훨씬 빨리 끝나지만, 그런 행운은 드뭅니다.

그리고 극단이 하나 있습니다. "이거예요?" 하고 하나씩 물으면 100만 개에서 평균 약 50만 번이 필요합니다. 스무고개에서 "사과예요?"를 일찍 묻는 게 아까운 이유입니다.

이진 탐색으로 돌려 보면

컴퓨터가 정렬된 목록에서 값을 찾을 때 쓰는 이진 탐색이 바로 반씩 나누는 스무고개입니다. 1부터 1,000,000 중 무작위로 정답을 하나 정하고, "X 이하인가요?"를 남은 범위의 가운데에 대고 묻는 일을 100만 번 반복했습니다.

• 평균 19.951번
• 가장 적을 때 19번, 가장 많을 때 20번
• 20번 걸린 경우 95.1%, 19번 4.9%

한 번도 20번을 넘지 않았습니다. 100만은 2^20(1,048,576)보다 조금 작아서 일부 갈래는 19번 만에 끝납니다. 앞 표의 정확 계산값 19.95번과도 맞습니다.

숫자 맞히기와 업다운 게임

"1부터 100 중에 생각한 수를 맞혀 봐" 하고 부르면 "업", "다운"으로 답하는 업다운 게임은 스무고개와 조금 다릅니다. 답이 업·다운·정답 셋이고, 정답을 부른 것도 한 번으로 셉니다. 그래도 반씩 가르는 원리는 같습니다. 첫 수로 50을 부르고, 이후에는 남은 범위의 가운데를 부릅니다.

정답 100가지를 전부 넣어 보니 1번째에 1개, 2번째에 2개, 3번째에 4개… 이렇게 두 배씩 늘다가 7번째에 남은 37개가 모두 맞혀집니다. 최대 7번, 평균 5.80번입니다.

사람들이 흔히 하는 "남은 범위에서 아무 수나 부르기"와 비교해 봤습니다. 정답 범위별 정확 계산값이고, 괄호 안은 20만 번 시뮬레이션 값입니다.

범위	반씩 부르기 평균	반씩 최악	아무 수나 부르기 평균
1~10	2.90번	4번	3.44번 (3.44)
1~100	5.80번	7번	7.48번 (7.47)
1~1,000	8.99번	10번	11.99번 (11.98)
1~10,000	12.36번	14번	16.58번 (16.56)

아무 수나 불러도 생각보다 나쁘지 않습니다. 1~100에서 평균 1.7번 더 들 뿐입니다. 차이는 최악에서 납니다. 반씩 부르면 7번을 절대 넘지 않지만, 아무 수나 부르면 시뮬레이션에서 20번까지 걸린 판이 나왔습니다. 1부터 하나씩 올라가며 부르면 평균 50.5번입니다.

숫자야구와 한글 낱말은 왜 더 빠를까

숫자야구도 후보를 좁혀 가는 게임입니다. 정답 후보는 504가지, 정보로 따지면 8.98비트입니다. 예/아니오 질문만 쓴다면 9번은 물어야 합니다.

그런데 숫자야구의 판정은 둘이 아니라 "1스트라이크 1볼"처럼 9가지입니다. 판정이 9가지면 한 번에 최대 log₂9 = 3.17비트를 받을 수 있어서, 이론상 하한은 3번입니다(9 × 9 = 81로는 504를 덮지 못하고, 9 × 9 × 9 = 729는 덮습니다). 다만 9가지 판정이 고르게 나오지 않습니다. 첫 수로 123을 부르면 504가지 정답 중 180가지가 "1볼"로 몰리기 때문에 실제로 받는 정보는 2.35비트입니다. 숫자야구의 실전 평균이 4점대인 이유가 여기 있고, 판정을 고르게 만드는 추리 요령은 아래 숫자야구 글에 정리돼 있습니다.

한글 낱말도 같습니다. 후보 370개는 8.53비트지만, 한 번 넣을 때마다 여섯 칸이 저마다 색으로 답해 주니 예/아니오 한 번보다 훨씬 많은 것을 알려 줍니다. 어느 게임이든 핵심은 스무고개와 같습니다. 답이 고르게 갈리는 질문이 가장 많이 좁혀 줍니다.

정리하면

• 예/아니오 질문 20개 = 2^20 = 1,048,576가지 — 100만 개 중 하나를 찾을 수 있습니다
• 질문 하나의 정보는 최대 1비트, 반반으로 가를 때만 다 받습니다
• 60:40이면 평균 20.52번으로 거의 손해가 없지만, 90:10이면 평균 40.97번, 최악 118번
• 100만 번 이진 탐색 시뮬레이션: 평균 19.951번, 한 번도 20번을 넘지 않았습니다
• 1~100 업다운은 반씩 부르면 최대 7번, 평균 5.80번 — 아무 수나 부르면 평균 7.48번

자주 묻는 질문

스무고개로 정말 100만 개 중 하나를 맞힐 수 있나요?

질문마다 후보를 정확히 반씩 가를 수 있다면 그렇습니다. 2를 스무 번 곱하면 1,048,576이라 100만 개를 넘습니다. 실제 놀이에서는 반반 질문을 떠올리기 어렵고 후보도 딱 정해져 있지 않아서, 스무 번 안에 못 맞히는 일이 흔합니다.

좋은 질문은 어떤 질문인가요?

"예"와 "아니오"가 비슷한 확률로 나올 질문입니다. 60:40 정도로만 갈라도 평균 20.52번으로 반반(19.95번)과 거의 같습니다. 반대로 대개 "아니오"가 나올 질문은 맞으면 크게 좁혀지지만 평균적으로는 손해입니다.

1부터 100까지 숫자 맞히기는 몇 번이면 되나요?

매번 남은 범위의 가운데를 부르면 최대 7번, 평균 5.80번입니다. 2를 일곱 번 곱하면 128이라 100을 넉넉히 덮습니다. 1부터 1,000까지는 최대 10번, 1부터 10,000까지는 최대 14번입니다.

90:10으로 치우친 질문만 하면 몇 번이 걸리나요?

100만 개 중 하나를 찾는 데 정확 계산으로 평균 40.97번, 최악 118번입니다. 20만 번 시뮬레이션에서도 평균 40.93번이 나왔습니다. 반반 질문의 두 배가 넘습니다.

비트가 뭔가요?

반반으로 나뉜 두 가지 중 하나를 알게 될 때 얻는 정보의 양입니다. 예/아니오 질문 하나로 얻을 수 있는 최대치가 1비트이고, 가짓수가 N개인 것을 가려내려면 log₂N비트가 필요합니다. 100만 개는 19.93비트라 반반 질문 20번이면 충분합니다.

함께 읽기

• 숫자야구, 몇 번이면 맞힐 수 있을까 — 504가지를 전부 돌려봤습니다
• 한글 낱말 첫 수로 "강물"을 넣으면 후보가 370개에서 6개로 줍니다
• 직접 좁혀 보고 싶다면 → 숫자야구 · 한글 낱말