몇 번이면 반드시 맞힐 수 있을까

UP·DOWN 숫자 게임에는 "가장 적게 묻는 방법"이 정해져 있습니다. 매번 남은 범위의 한가운데 숫자를 고르는 것입니다. 이렇게 하면 답이 무엇이든 한 번 물을 때마다 후보가 절반으로 줄어듭니다. 컴퓨터 과학에서는 이 방법을 이진 탐색이라고 부릅니다.

후보가 매번 절반으로 줄어들기 때문에, 최악의 경우에도 필요한 질문 수는 범위의 크기를 2로 몇 번 나누어야 1이 되는지와 같습니다. 오르락내리락의 빠른 범위 버튼 기준으로 계산하면 다음과 같습니다.

숫자 범위 후보 수 최악의 경우 필요한 질문 수
1~100 100개 7번
1~500 500개 9번
1~1,000 1,000개 10번
1~10,000 10,000개 14번

후보가 100배로 늘어나도 질문은 7번만 늘어난다는 점이 이진 탐색의 힘입니다. 그래서 질문 횟수를 위 표보다 하나 적게 설정하면 "운이 조금 따라야 이기는" 적당한 긴장감이 생깁니다. 1100 범위에서 질문 5번, 11,000에서 질문 8번 정도가 도전하기 좋은 설정입니다.

직접 해 보는 예시

정답이 73이고 범위가 1~100이라고 해 봅시다.

  1. 가운데인 50을 입력 → UP. 이제 후보는 51~100입니다.
  2. 51과 100의 가운데인 75 → DOWN. 후보는 51~74.
  3. 62 → UP. 후보는 63~74.
  4. 68 → UP. 후보는 69~74.
  5. 71 → UP. 후보는 72~74.
  6. 73 → 정답!

여섯 번 만에 맞혔습니다. 오르락내리락은 지금 가능한 최솟값과 최댓값을 화면에 계속 보여 주므로, 가운데 값을 계산하기도 쉽습니다. 범위 밖의 숫자를 입력하면 시도 횟수에 포함하기 전에 안내해 줍니다.

수업에서 활용하기

이 게임은 초등 고학년부터 중학생까지 수학이나 정보 수업의 도입 활동으로 쓰기 좋습니다.

  • 수학 — 어림과 범위: "지금 가능한 숫자는 몇 개일까?"를 매번 묻게 하면 범위와 개수 세기를 자연스럽게 연습합니다.
  • 정보 — 알고리즘 첫 수업: 처음에는 아무 숫자나 부르게 하고, 다음 판에서는 가운데 숫자 전략을 알려 준 뒤 질문 수를 비교하게 합니다. "규칙을 따르는 방법"이 왜 빠른지 몸으로 이해할 수 있습니다.
  • 2의 거듭제곱 감각 익히기: 표의 질문 수가 왜 그렇게 나오는지 2, 4, 8, 16, …, 1,024를 직접 써 보게 하면 로그를 배우기 전에 감각을 잡을 수 있습니다.

모임에서 쓰는 변형 규칙

  • 팀 대항전: 두 팀이 번갈아 숫자를 부르고, 정답을 맞힌 팀이 점수를 얻습니다. 상대 팀의 질문 덕분에 범위가 좁아지기 때문에 언제 승부를 걸지 전략이 생깁니다.
  • 폭탄 숫자: 정답을 맞힌 사람이 벌칙을 받는 방식입니다. 범위가 좁아질수록 모두가 피하려 해서 마지막까지 긴장감이 큽니다.
  • 질문 횟수 경매: 각자 "나는 몇 번 안에 맞힐 수 있다"고 말하고, 가장 적은 횟수를 말한 사람이 도전합니다.

질문 횟수는 2회부터 무제한까지 고를 수 있습니다. 처음 해 보는 사람과 함께라면 무제한으로 규칙을 익히고, 익숙해지면 표를 참고해 횟수를 줄여 보세요.

질문 횟수를 줄이면 이길 확률은 얼마나 될까

가운데 숫자 전략을 쓰면 질문 k번으로 확실하게 찾을 수 있는 숫자는 최대 2의 k제곱에서 1을 뺀 개수입니다. 질문 횟수가 그보다 적으면 운이 따라야 합니다. 최선의 전략을 썼을 때 이길 확률은 다음과 같습니다.

질문 횟수 1~100에서 이길 확률 1~1,000에서 이길 확률
5번 31% 3.1%
6번 63% 6.3%
7번 100% 12.7%
8번 100% 25.5%
9번 100% 51.1%
10번 100% 100%

질문 횟수를 하나 줄일 때마다 이길 확률이 대략 절반으로 떨어지는 것을 볼 수 있습니다. 대결 게임에서 "적당히 어려운" 설정을 원한다면 이길 확률이 5060% 정도인 1100에 6번, 1~1,000에 9번을 추천합니다.