AMC 10 · 2018 · #15

학년 7 number-theory
유형 Branching State Enumeration └ 세부 유형 Ordered Placement Count
divisibility-rulesdigit-sumdigit-constraintsfundamental-counting-principlemodular-arithmetic identify-subproblemscaseworksystematic-enumeration ↑ 선수 지식: divisibility-rulesfundamental-counting-principle
📏 중간 풀이 💡 3 개 인사이트
문제
100부터 999까지의 정수 중에서 세 조건을 동시에 만족하는 수가 몇 개인지 세세요. 홀수여야 하고, 3의 배수여야 하며, 세 자릿수 중 어느 것도 숫자 3이 아니어야 합니다.

답을 골라 클릭하세요.

(A)
96
(B)
97
(C)
98
(D)
102
(E)
120
풀이 과정
전략 작은 문제로 쪼개기

세 조건 중 둘은 한 자리 안에서만 작동한다. '홀수'는 일의 자리만 건드리고, '숫자 3 금지'는 자리마다 따로 걸리는 금지 조건이다. 자리들을 서로 묶는 것은 '3의 배수' 조건 하나뿐인데, 수를 다시 써 보면 이 조건이 각 자리 숫자의 합에 대한 조건으로 바뀐다. 그래서 각 자리를 하나의 작은 세기 문제로 다루고, 조건이 까다로운 자리를 먼저 채운 뒤 마지막 자리에 배수 조건을 떠넘길 계획이다. 마지막 자리에서 쓸 수 있는 숫자의 개수가 언제나 같다면, 전체 개수는 긴 경우 나누기 없이 곱셈 한 번으로 끝난다.

1STEP 1

세 자리 숫자에 이름 붙이기

세 자리에 각각 이름을 붙입니다.

N = 100A + 10B + C, A ∈ {1,…,9}, B ∈ {0,…,9}, C ∈ {1,5,7,9}
2STEP 2

배수 조건을 숫자의 합으로 바꾸기

3의 배수를 자릿수 합으로 바꿉니다.

100A + 10B + C = (99A + 9B)₃의 배수 + (A + B + C)
3STEP 3

백의 자리와 일의 자리 세기

백의 자리와 일의 자리를 셉니다.

A ∈ {1,2,4,5,6,7,8,9} (8가지), C ∈ {1,5,7,9} (4가지)
4STEP 4

십의 자리를 나머지로 분류하기

십의 자리는 나머지별로 늘 세 개씩 있습니다.

{0,6,9}, {1,4,7}, {2,5,8} → 어떤 경우에도 B는 3가지
5STEP 5

세 자리의 가짓수를 곱하기

세 가짓수를 곱하면 96입니다.

8 · 4 · 3 = 96
정답
96
두 가지 점검이 서로 맞아떨어진다. 첫째, 조건을 만족하는 쌍 (A, C) 하나마다 정확히 3개의 수가 나오므로 전체 개수는 반드시 3의 배수여야 한다. 이 사실만으로 97과 98은 즉시 배제되고, 96은 조건에 들어맞는다. 둘째, 제한 없는 개수와 비교해 보자. 세 자리 홀수 3의 배수는 105, 111, …, 999로 6씩 떨어져 있으므로 (999 - 105)/6 + 1 = 150개이다. 숫자 3 금지는 백의 자리에서 8/9, 십의 자리에서 9/10, 홀수인 일의 자리에서 4/5만 남기는데, 150 · 8/9 · 9/10 · 4/5 = 96이다. 두 경로가 모두 96을 가리키고, 96은 마땅히 그래야 하듯 150보다 작다. 세 번의 금지를 거친 뒤에도 150개짜리 목록의 부분집합이어야 하므로 102나 120은 지나치게 크다.
💡핵심 정리

까다로운 자리를 먼저 채우고 고르게 갈리는 자리를 마지막에 남겨 두면, 모든 경우에서 선택지 수가 같아져 전체 개수가 곱셈 한 번으로 끝난다.

  • 세 자리 숫자에 이름 붙이기
  • 배수 조건을 숫자의 합으로 바꾸기
  • 백의 자리와 일의 자리 세기
  • 십의 자리를 나머지로 분류하기
  • 세 자리의 가짓수를 곱하기

비슷한 유형 더 풀어보기

같은 archetype · 비슷한 학년부터.