경시 · AMC 대비 · 4단계 중 4

AMC 10 · 2023B · #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)
0
(D)
9
(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이 있는지로 나누기

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

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

0을 포함한 집합 세기

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.

  • 두 자리 경우 먼저 세기
  • 수와 숫자 집합 대응시키기
  • 0이 있는지로 나누기
  • 0을 포함한 집합 세기

가족의 부모 대시보드는 sensimlab.com에 있습니다.