AMC 10 · 2023 · #16

학년 8 arithmetic

combinations-basicdigit-countingsystematic-enumerationcombinatorial-identity easier-related-problemcomplementary-countingidentify-subproblems ↑ 선수 지식: combinations-basicsystematic-enumeration

📏 긴 풀이 💡 3 개 인사이트

문제

upno 는 자릿수가 왼쪽에서 오른쪽으로 엄격히 증가하는 2 자리 이상의 양의 정수이고, downno 는 자릿수가 엄격히 감소하는 2 자리 이상의 양의 정수입니다. U 를 upno 의 총 개수, D 를 downno 의 총 개수라 할 때 |U - D| 를 구하세요.

답을 골라 클릭하세요.

(A)

~512

(B)

~10

(C)

(D)

(E)

~511

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

풀이 과정

전략 더 쉬운 문제로 줄이기

자릿수 집합을 고르고 순서대로 적기만 하면 되므로 세기 문제로 단번에 환원됩니다. U 는 {1,…,9} 의 크기 ≥ 2 부분집합의 개수, D 는 {0,1,…,9} 의 크기 ≥ 2 부분집합의 개수. 도구 #9(작은 사례) 가 일대일 대응을 발견하게 하고, 도구 #2(체계적 나열) 가 작은 사례를 손으로 확인, 도구 #16(차이에만 집중) 이 |U-D| 를 한 가지 부분집합 세기로 줄여 줍니다.

1STEP 1

두 자리로 예열: upno=C(9,2)=36, downno=C(10,2)=45; 차이 9는 0 으로 끝나는 downno 개수와 같음.

C(9, 2)=36, C(10, 2)=45, 45-36=9

2STEP 2

일반화: 각 수는 자릿수 집합으로 정해지니, U는 {1..9} 의 크기 ≥2 부분집합 수, D는 {0..9} 의 크기 ≥2 부분집합 수.

U = #{S⊆{1,…,9}: |S| ≥ 2}, D = #{T⊆{0,1,…,9}: |T| ≥ 2}

3STEP 3

0 없는 downno 집합은 upno 집합과 일대일 대응이니, 차이는 결국 D - U = 0 을 포함하는 downno 수.

D - U = #{T⊆{0,1,…,9}: 0∈ T, |T| ≥ 2}

4STEP 4

0 을 포함하는 집합 세기: {1..9} 의 공집합 아닌 부분집합에 0 을 더해 2⁹ - 1 = 511, 즉 |U - D| = 511.

|U - D| = 2⁹ - 1 = 512 - 1 = 511 → (E) 511

정답

~511

두 자리 사례 점검: 0 으로 끝나는 두 자리 downno 는 10, 20, …, 90 의 9 개 — 정확히 맞음. 일반 공식은 모든 길이를 합쳐서 2⁹ - 1 = 511 개의 "0 끝" downno 를 예측. 총 개수 교차 확인: U = 2⁹ - 9 - 1 = 502, D = 2¹⁰ - 10 - 1 = 1013 이고 D - U = 1013 - 502 = 511. 선택지 (E) 와 정확히 일치.

💡핵심 정리

Upno 는 {1,…,9} 에서 고른 자릿수 집합을 작은 수부터 적은 것이고, downno 는 0 도 쓸 수 있는 집합을 큰 수부터 적은 것 (단 0 은 맨 끝). 두 개수는 0 을 포함하는 downno 만큼 차이가 나는데, 그 수는 {1,…,9} 의 공집합 아닌 부분집합 수와 같으므로 |U-D| = 2⁹ - 1 = (E) 511.