AMC 8 · 2009 · #22

학년 5 counting

유형 Small-Domain Constrained Search └ 세부 유형 Logic-Deduction / Elimination

systematic-enumerationdigit-constraintsplace-valuecomplementary-counting complementary-countingcasework ↑ 선수 지식: multi-digit-arithmeticplace-value

📏 중간 풀이 💡 3 개 인사이트

📘 쉬운 버전 보기 →

문제

1 보다 크고 1000 보다 작은 정수 중에서, 십진법 표기에 숫자 "1" 이 단 한 번도 들어가지 않는 수의 개수를 구하는 문제입니다. 즉 1 ＜ n ＜ 1000 인 정수 n 중에서 모든 자리수가 1 이 아닌 것의 개수입니다.

답을 골라 클릭하세요.

(A)

512

(B)

648

(C)

720

(D)

728

(E)

800

AMC 8 2009 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

풀이 과정

전략 경우의 수 세기

특정 숫자 하나를 피하는 길이 3 의 수 문자열 개수를 세는 전형적인 곱셈 원리 상황으로, 도구 #13(경우의 수 세기) 이 바로 들어맞습니다. 핵심 트릭은 모든 수를 세 자리로 패딩하는 것입니다 — 7 은 "007", 42 는 "042" 처럼요. 그러면 0 부터 999 까지의 모든 정수가 세 칸짜리 문자열이 되고, 각 칸은 독립적으로 {0,1,2,…,9} 중에서 고르며 1 만 금지하면 됩니다. 도구 #7(작은 문제로 쪼개기) 은 경계 끝부분을 처리하는 데 씁니다 — 패딩한 개수에는 000 (우리 범위 밖) 이 들어가 있으므로 한 번 빼 주기만 하면 됩니다.

1STEP 1

0–999 를 세 자리 문자열로 패딩하면, 세 칸 각각이 독립적으로 9 개 숫자(1 을 뺀)를 가집니다.

한 칸당 허용 숫자 = 10 - 1 = 9

2STEP 2

독립적인 세 개의 9 가지 선택을 곱하면 729 개의 문자열이 1 을 피합니다.

9 × 9 × 9 = 729

3STEP 3

범위 밖 0 을 뜻하는 000 한 개만 빼면 됩니다 — 1 은 스스로 제외되고 1000 은 네 자리라, 남는 것은 728 입니다.

729 - 1 = 728

4STEP 4

구한 값 728 은 선택지 (D) 와 일치합니다.

728 → (D)

정답

728

각 칸의 약

\frac{9}{10}

가 허용되므로 세 칸 모두 1 을 피할 확률은 약 (

\frac{9}{10}

)³ = 0.729. 000 부터 999 까지 1000 개 문자열 중 약 729 개라는 어림이 나오고, 000 한 개를 빼면 정확히 728 로 답과 일치합니다. 다른 선택지는 이 어림과 맞지 않습니다 — 512 = 8³ 은 금지 숫자가 둘일 때, 800 은 더 느슨한 조건일 때 나오는 수입니다.

💡핵심 정리

모든 수를 세 자리로 채워 보면, 각 칸은 따로따로 9 가지 중 하나를 고르는 일이 됩니다 — 5학년 때 배운 곱셈 그대로에 작은 보정 하나만 더하면 됩니다.

비슷한 유형 더 풀어보기