AMC 10 · 2005 · #19

학년 7 counting
digit-countingfundamental-counting-principlebase-conversion complementary-countingsystematic-enumeration ↑ 선수 지식: digit-countingfundamental-counting-principleplace-value
📏 중간 풀이 💡 2 개 인사이트
문제
고장 난 주행 거리계는 어느 자리에서도 숫자 4를 보이지 않고 3에서 곧바로 5로 넘어간다. 지금 표시가 2005다. 실제로 달린 거리를 구하여라.

답을 골라 클릭하세요.

(A)
1404
(B)
1462
(C)
1604
(D)
1605
(E)
1804
풀이 과정
전략 관점 바꾸기

주행 거리계를 1마일씩 따라가는 것은 가망이 없다. 세는 대상을 바꾸면 된다. 표시는 1마일마다 정확히 한 칸씩 나아가므로, 달린 거리는 1부터 002005까지 나타날 수 있는 표시의 개수와 같다. 나타날 수 있는 표시란 숫자 4가 없는 수일 뿐이고, 그런 수는 자리마다 하나씩 따져 세면 된다.

1STEP 1

마일이 아니라 표시를 세기

실제 거리는 허용된 수의 개수다.

m = #{ n : 1 ≤ n ≤ 2005, n has no digit 4 }
2STEP 2

2000에서 범위 자르기

마지막 몇 개를 떼면 규칙적인 범위가 남는다.

{1,…,2005} = {1,…,1999} ∪ {2000,…,2005}
3STEP 3

허용되는 네 자리 문자열 세기

0을 채우면 각 자리가 독립적인 선택이 된다.

2 × 9 × 9 × 9
4STEP 4

계산하고 문자열 0000 빼기

모두 0인 문자열을 빼면 1457이 남는다.

2 · 9³ - 1 = 2 · 729 - 1 = 1458 - 1 = 1457
5STEP 5

짧은 꼬리 나열하기

짧은 꼬리가 5개를 더한다.

2000, 2001, 2002, 2003, 2005 ⟹ 5
6STEP 6

두 개수 더하기

더하면 1462, 보기 (B).

1457 + 5 = 1462
정답
1462
이번에는 건너뛴 수를 세서 두 개수가 범위를 꽉 채우는지 확인한다. 1부터 2005까지 천의 자리는 결코 4가 아니므로, 어떤 수가 건너뛰어지는 것은 백의 자리나 십의 자리나 일의 자리에 4가 있을 때뿐이다. 백의 자리가 4인 수가 200개, 십의 자리가 4인 수가 200개, 일의 자리가 4인 수가 201개이고, 두 조건이 동시에 성립하는 수는 어느 쌍이든 20개이며, 셋 모두가 성립하는 수는 444와 1444뿐이다. 포함과 배제로 200 + 200 + 201 - 20 - 20 - 20 + 2 = 543개가 건너뛴 수이고 2005 - 543 = 1462로 같은 답이 나온다. 크기도 그럴듯하다. 자유로운 자리가 세 개이고 각 자리가 대략 9/10의 비율로 살아남으므로, 2005 · 0.9³은 약 1462이다.
💡핵심 정리

숫자 하나를 거부하는 계기는 열 개가 아니라 아홉 개의 기호로 세고 있는 셈이므로, 그 계기가 보여 줄 수 있는 수만 세면 된다.

  • 마일이 아니라 표시를 세기
  • 2000에서 범위 자르기
  • 허용되는 네 자리 문자열 세기
  • 계산하고 문자열 0000 빼기
  • 짧은 꼬리 나열하기
  • 두 개수 더하기