AMC 10 · 2023 · #24

학년 10 counting

유형 Branching State Enumeration └ 세부 유형 Ordered Placement Count

fundamental-counting-principleexponentsmodular-arithmetic-mod-10symmetry-argument easier-related-problempattern-recognitionidentify-subproblems ↑ 선수 지식: fundamental-counting-principleexponents

📏 긴 풀이 💡 3 개 인사이트

문제

1부터 10까지의 부분집합으로 사슬을 만듭니다. 먼저 10 이하의 길이를 고른 뒤 그 길이만큼 부분집합을 고르되 각 집합이 앞의 집합을 포함해야 합니다. 같은 집합이 반복돼도 됩니다. 모든 허용된 길이에 대해 만들 수 있는 사슬의 총 개수를 10으로 나눈 나머지를 구하세요.

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

풀이 과정

전략 관점 바꾸기

집합을 하나씩 골라 가며 사슬을 세는 길은 막다른 길이다. A₁을 고르고 나면 그것이 얼마나 큰지에 따라 A₂의 후보 수가 달라지므로 선택들이 서로 얽히고 경우 나누기가 폭발한다. 빠져나갈 길은 집합에서 눈을 떼고 원소를 보는 것이다. 포함 조건을 원소 하나씩 읽으면 집합 전체에 대해서는 아무 말도 하지 않는다. 그저 한 번 들어온 원소는 나갈 수 없다는 말일 뿐이다. 그러면 원소 하나의 일생 전체가 들어온 순간이라는 숫자 하나로 정해지고, 열 개의 원소는 서로 완전히 독립이 된다. 독립인 선택 열 개는 그냥 곱하면 되므로 길이가 고정된 사슬의 개수가 한 줄에 끝난다. 그다음은 깔끔한 두 조각이다. 길이별 개수 열 개를 더하고, 마지막 자리 숫자만 남기고 나머지는 버린다.

1STEP 1

원소 하나씩 읽기

한 번 들어오면 계속 남습니다.

j ∈ A_i-1 → j ∈ A_i → j ∈ A_i+1 → … → j ∈ A_n

2STEP 2

들어온 시각 적기

원소마다 들어온 시각을 적습니다.

t(j) ∈ {1, 2, …, n} ∪ {never}, A_i = { j : t(j) ≤ i }

3STEP 3

독립인 선택 곱하기

열 개의 선택이 독립입니다.

(길이 n 인 사슬의 수) = (n+1) × (n+1) × … × (n+1)₁₀ 개의 원소 = (n+1)¹⁰

4STEP 4

작은 경우로 시험

작은 경우로 식을 시험합니다.

바탕집합 {1}: 2¹ = 2, 3¹ = 3 바탕집합 {1,2}: 2² = 4, 3² = 9, 4² = 16

5STEP 5

모든 길이에 대해 더하기

허용된 모든 길이에 대해 더합니다.

K = Σ_n=1¹⁰ (n+1)¹⁰ = 2¹⁰ + 3¹⁰ + 4¹⁰ + … + 11¹⁰ = Σ_m=2¹¹ m¹⁰

6STEP 6

마지막 자리만 남기기

일의 자리만 남깁니다.

K ≡ Σ_m=2¹¹ m¹⁰ ≡ Σ_r=0⁹ r¹⁰ (mod 10)

7STEP 7

숫자를 짝지어 마무리

짝지어 더하면 5입니다.

Σ_r=0⁹ r¹⁰ ≡ 0 + 5 + 2(1 + 4 + 9 + 6) = 5 + 40 = 45 ≡ 5 (mod 10)

정답

마지막 자리는 위와 아무것도 공유하지 않는 다른 길로도 확인할 수 있다. 법 10을 2와 5로 쪼개는 방법이다. 먼저 홀짝을 보자. 짝수를 몇 제곱해도 짝수이고 홀수를 몇 제곱해도 홀수인데, 밑 2, 3, …, 11 중 홀수는 3, 5, 7, 9, 11의 다섯 개이다. 홀수 다섯 개와 짝수 다섯 개의 합은 홀수이므로 K는 홀수이다. 선택지가 모두 홀수이므로 이 결과는 다섯 선택지 전부와 어긋나지 않으며, 애초에 홀짝만으로는 답이 갈리지 않는다는 뜻이기도 하다. 이번에는 5로 나눈 나머지를 보자. m이 5의 배수가 아니면 페르마의 소정리에 의해 m⁴ ≡ 1 (mod 5)이므로 m¹⁰ = m⁸ · m² ≡ m² (mod 5)이다. 밑 5와 10은 0을 보태고, 남은 여덟 개의 밑 2, 3, 4, 6, 7, 8, 9, 11의 제곱은 각각 4, 4, 1, 1, 4, 4, 1, 1과 합동이어서 합이 20 ≡ 0 (mod 5)이다. 그러므로 K는 홀수이면서 5의 배수이고, 10으로 나눈 나머지 중 그런 값은 5뿐이다. 두 길의 결론이 같다. 크기도 확인해 두자. 실제 값은 K = 2¹⁰ + 3¹⁰ + … + 11¹⁰ = 40851766525로 정말 5로 끝나며, 마지막 항 11¹⁰ = 25937424601이 전체를 좌우한다. 항이 이렇게 빠르게 커지는 합에서는 당연한 모습이다.

💡핵심 정리

포개진 집합의 사슬은 사실 초시계 열 개다. 원소마다 하나씩, 그 원소가 들어와 머물기 시작한 순간을 기록한 것이다. 그러니 사슬을 세는 일은 초시계 눈금을 세는 일에 지나지 않는다.

조건을 원소 하나씩 읽기
원소마다 들어온 시각 적기
독립인 선택 열 개는 곱해진다
작은 경우로 식을 시험하기
허용된 모든 길이에 대해 더하기
마지막 자리 숫자만 남기기
숫자를 짝지어 마무리하기