AMC 10 · 2006 · #9

학년 7 counting
combinations-basicdigit-constraintssystematic-enumeration casework ↑ 선수 지식: combinations-basic
📏 중간 풀이 💡 2 개 인사이트
문제
어떤 세 자리 짝수의 자릿수가 왼쪽에서 오른쪽으로 갈수록 엄격히 커진다. 그런 수가 몇 개인지 구하여라.

답을 골라 클릭하세요.

(A)
21
(B)
34
(C)
51
(D)
72
(E)
150
풀이 과정
전략 빠짐없이 나열하기

유한하고 작은 범위에서 "몇 개인가"를 묻는 문제이므로 도구 #2(빠짐없이 나열하기)를 쓴다. 다만 세 자리 짝수 450개를 모두 나열하는 것이 계획이 아니라, 무엇을 나열할지 제대로 고르는 것이 계획이다. 먼저 도구 #3(가능성 지우기)으로 사용할 수 있는 숫자를 줄인다 — 어떤 자리에도 0은 오지 않고, 일의 자리 숫자는 단 세 가지 값뿐이다. 그다음 도구 #15(다르게 정리하기)가 핵심 역할을 한다. 엄격히 증가하는 수는 어떤 세 숫자를 쓰는지 말고는 아무 정보도 담고 있지 않다. 배열 순서가 이미 정해져 있기 때문이다. 그래서 수를 숫자들의 집합으로 다시 볼 수 있다. 이 다시 보기가 문제의 전부이며, 반드시 양쪽 방향으로 논증해야 한다. 유효한 수는 저마다 숫자 집합을 내어 주고, 거꾸로 — 보통은 논증 없이 주장만 하고 넘어가는 부분인데 — 허용된 숫자 집합은 저마다 유효한 수를 정확히 하나씩 되돌려 준다. 바로 이 두 번째 방향에서 "어떤 숫자도 0이 아니다"라는 사실이 값을 한다. 되살린 수가 정말로 세 자리임을 보장해 주는 것이 그 사실이기 때문이다. 마지막으로 도구 #7(작은 문제로 쪼개기)이 일의 자리 숫자에 따라 서로 겹치지 않는 세 경우로 나누고 그 합을 구한다.

1STEP 1

모든 자리에서 0을 지우기

엄격히 커지는 자릿수가 모든 자리에서 0을 밀어낸다.

a ≠ 0이고 a < b < c → 1 ≤ a < b < c ≤ 9
2STEP 2

일의 자리 숫자 좁히기

마지막 자릿수는 짝수이면서 자리를 남겨야 해 가지만 남는다.

c는 짝수, c ≠ 0, 그리고 c=2는 a < b < c를 놓을 자리를 남기지 않음 → c∈{4,6,8}
3STEP 3

수와 숫자 쌍을 짝지어 대응시키기

순서가 정해져 있어 각 수가 더 작은 자릿수 과 대응된다.

{abc : 1 ≤ a < b < c} ⟷ { {p,q}⊆{1,2,…,c-1} }
4STEP 4

각 c 아래의 쌍 개수 세기

각각보다 작은 쌍을 세면 3, 10, 21이다.

C(n, 2)=(n(n-1))/2; C(3, 2)=3, C(5, 2)=10, C(7, 2)=21
5STEP 5

세 경우를 합하기

더하면 34, 보기 (B).

3+10+21=34 → (B)
정답
34
마지막 자리 대신 가운데 자리 숫자를 축으로 삼아 다시 세어 보자 — 부분집합 세기를 전혀 쓰지 않는 길이다. b를 고정하면 백의 자리 숫자는 1,2,…,b-1 중 아무것이나 될 수 있어 b-1가지이고, 일의 자리 숫자는 b보다 큰 짝수 숫자 중 아무것이나 될 수 있다. 두 선택은 서로 독립이므로 곱한다. b=2: 1 × 3=3(c=4,6,8). b=3: 2 × 3=6. b=4: 3 × 2=6(c=6,8). b=5: 4 × 2=8. b=6: 5 × 1=5(c=8). b=7: 6 × 1=6. 그 밖에는 살아남는 것이 없다. b=1이면 a=0이 되어야 하고, b ≥ 8이면 b보다 큰 짝수 숫자가 없기 때문이다. 합은 3+6+6+8+5+6=34로 앞의 결과와 일치한다. 선택지를 직접 공략할 수도 있다. 짝수든 홀수든 엄격히 증가하는 세 자리 수는 모두 {1,…,9}의 세 원소 부분집합과 대응하고 그런 부분집합은 C(9, 3)=84개뿐이므로, 150은 전체 우주보다도 크다 — (E)는 보자마자 불가능하다. 그 84개 안에서 각 짝수 끝자리를 바로 위의 홀수 끝자리와 짝지어 보자. c=4 대 c=5는 3 < 6, c=6 대 c=7은 10 < 15, c=8 대 c=9는 21 < 28이고, 게다가 c=3이 짝 없이 홀수 쪽에 1을 더 얹는다. 따라서 짝수로 끝나는 수는 84의 절반보다 엄격히 적어 42 미만이며, 이로써 (C) 51과 (D) 72도 지워진다. 남는 것은 (A) 21과 (B) 34인데, 21은 정확히 c=8 경우만의 소계이다 — 가장 큰 경우 하나를 세고 멈춘 사람의 답인 셈이다.
💡핵심 정리

숫자가 반드시 커지도록 정해져 있으면 순서는 이미 결정된 것이므로, 이런 수를 세는 일은 어떤 숫자를 쓸지 고르는 경우를 세는 일과 같다.

  • 모든 자리에서 0을 지우기
  • 일의 자리 숫자 좁히기
  • 수와 숫자 쌍을 짝지어 대응시키기
  • 각 c 아래의 쌍 개수 세기
  • 세 경우를 합하기