AMC 10 · 2017 · #17

학년 7 arithmetic

유형 Overlap / Complement Counting └ 세부 유형 Two-Set Inclusion-Exclusion: Solve for Missing Region

combinations-basicsystematic-enumerationexponents caseworkcomplementary-counting ↑ 선수 지식: combinations-basic

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

문제

양의 정수가 한 자리 수이거나, 자릿수를 왼쪽에서 오른쪽으로 읽었을 때 순전히 커지거나(strictly increasing) 순전히 작아지면(strictly decreasing) 그 수를 단조수(monotonous)라 한다. 단조수인 양의 정수가 모두 몇 개인지 세어라.

답을 골라 클릭하세요.

(A)

1024

(B)

1524

(C)

1533

(D)

1536

(E)

2048

AMC 10 2017 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

풀이 과정

전략 빠짐없이 나열하기

"몇 개"라는 물음은 도구 #2(빠짐없이 나열하기)를 부르지만, 수천 개의 수를 손으로 나열하는 것은 무리이므로 도구 #16(관점 바꾸기)으로 세는 방식을 다시 짠다. 자릿수를 하나하나 쌓는 대신 어떤 자릿수들을 쓸지 고른다. 서로 다른 자릿수의 집합을 하나 고르면 그것을 순전히 커지게 배열하는 방법이 딱 하나, 순전히 작아지게 배열하는 방법이 딱 하나뿐이다 — 순서는 정해져 버린다. 도구 #7(작은 문제로 쪼개기)로 커지는 경우와 작아지는 경우로 나누고, 도구 #5(패턴 찾기)로 부분집합의 개수를 얻는다: n개짜리 집합의 부분집합은 2ⁿ개이다.

1STEP 1

수가 아니라 자릿수를 고른다

단조수는 자릿수 집합과 방향으로 정해지고, 집합마다 방향별 배열이 하나뿐이다 — 그러니 수 말고 자릿수 집합을 세자.

{2,3,5,7,8}→ 23578 (커짐) 또는 87532 (작아짐)

2STEP 2

커지는 수의 개수

커지는 수는 0을 못 쓴다(맨 앞에 와야 하니); 1~9의 비어 있지 않은 부분집합마다 수 하나라 2⁹-1=511개다.

2⁹-1=512-1=511

3STEP 3

작아지는 수의 개수

작아지는 수는 0이 끝에 올 수 있어 0~9를 다 쓴다; 공집합과 {0} 하나짜리를 빼면 2¹⁰-2=1022개다.

2¹⁰-2=1024-2=1022

4STEP 4

겹쳐 센 것 없이 합치기

더하면 511+1022=1533이지만 한 자리 수 9개가 두 목록에 겹쳐 세였으니 빼면 1533-9=1524 — 선택지 (B)이다.

511+1022-9=1533-9=1524 → (B)

정답

1524

총합 1524는 선택지 중 하나이며 어림과도 맞는다: 각 방향은 자르기 전에 대략 2¹⁰≈ 1000개의 부분집합이므로 합이 1500 근처가 되리라 예상된다. 작은 길이로 점검해도 맞는다: 한 자리 단조수는 9개이고, 두 자리 단조수는 커지는 C(9, 2)=36개에 작아지는 C(10, 2)=45개를 더해 81개로, 두 원소 자릿수 집합의 개수와 정확히 일치한다. 부분집합 구조가 유지되므로 1524는 믿을 만하다.

💡핵심 정리

어떤 자릿수를 쓸지 고르면 순서는 정해지므로 자릿수 집합만 세면 된다: 커지는 511개에 작아지는 1022개를 더하고, 두 번 센 한 자리 수 9개를 빼면 1524 — 선택지 (B)이다.

수가 아니라 자릿수를 고른다
커지는 수의 개수
작아지는 수의 개수
겹쳐 센 것 없이 합치기

수가 아니라 자릿수를 고른다

커지는 수의 개수

작아지는 수의 개수

겹쳐 센 것 없이 합치기

비슷한 유형 더 풀어보기