AMC 10 · 2021 · #15

학년 11 counting
유형 Casework by Position / Vertex Type └ 세부 유형 Count of Type
combinations-basiccombinatorial-identitycomplementary-countingmodular-arithmetic identify-subproblemssystematic-enumeration ↑ 선수 지식: combinations-basic
📏 긴 풀이 💡 3 개 인사이트
문제
합창 지휘자가 테너 여섯 명과 베이스 여덟 명에서 조를 만듭니다. 테너 수와 베이스 수의 차가 4의 배수이고 조가 비어 있지 않으면 허용됩니다. 허용되는 조의 개수를 100으로 나눈 나머지를 구하세요.

답을 골라 클릭하세요.

(A)
47
(B)
48
(C)
83
(D)
95
(E)
96
풀이 과정
전략 관점 바꾸기

그대로 쓰면 N 은 C(6, t)C(8, b) 꼴의 곱을 열다섯 개쯤 더한 값입니다. 끝까지 계산할 수는 있지만 느리고, 답이 왜 깔끔하게 떨어지는지도 보이지 않습니다. 문제는 빼기 기호입니다. 두 집단을 뺄셈으로 비교하니 하나로 합쳐지지 않습니다. 해결책은 "뽑은 베이스" 대신 "남긴 베이스" 를 세는 것입니다. 뽑을 사람을 정하는 일과 남길 사람을 정하는 일은 같은 결정이므로 개수는 전혀 달라지지 않고, 대신 뺄셈이 덧셈으로 바뀝니다. 조건이 "두 수의 합이 4의 배수" 가 되는 순간 테너와 베이스가 똑같은 질문을 받게 되고, 문제 전체가 14 명짜리 하나의 집단에 대한 한 가지 질문으로 줄어듭니다. 그다음은 이항계수 네 개, 공집합을 빼는 뺄셈 한 번, 나눗셈 한 번이면 끝입니다.

1STEP 1

두 개수에 이름 붙이기

조건이 차에 대한 것입니다.

C(6, t)C(8, b), 0 ≤ t ≤ 6, 0 ≤ b ≤ 8, 4 ∣ (t - b)
2STEP 2

남긴 베이스를 세기

남긴 베이스를 세면 차가 합이 됩니다.

u = 8 - b, C(8, b) = C(8, u), t - b = t + u - 8 ⟹ 4 ∣ (t - b) ⇔ 4 ∣ (t + u)
3STEP 3

열네 명으로 합치기

두 무리가 하나로 합쳐집니다.

S = T ∪ U, |T| = t, |U| = u, |S| = t + u, #{S : |S| = s} = C(14, s)
4STEP 4

살아남는 크기 나열

4의 배수인 크기만 남습니다.

0 ≤ |S| ≤ 14, |S| ∈ {0, 4, 8, 12}
5STEP 5

이항계수 더하기

네 이항계수를 더하면 2의 거듭제곱입니다.

C(14, 0) + C(14, 4) + C(14, 8) + C(14, 12) = 1 + 1001 + 3003 + 91 = 4096 = 2¹²
6STEP 6

공집합 빼고 나누기

공집합을 빼고 나누면 95입니다.

N = 4096 - 1 = 4095, 4095 = 40 · 100 + 95
정답
95
서로 독립인 두 가지 검산을 합니다. 첫째, 크기 감각입니다. 조건을 무시하면 비어 있지 않은 그룹은 2¹⁴ - 1 = 16383 개이고, 네 가지 나머지 중 하나만 남기는 조건이라면 대략 그 4 분의 1이 남아야 합니다. 16383/4 ≈ 4096 이므로 N = 4095는 정확히 있어야 할 자리에 있습니다. 둘째, 원래 변수로 다시 세어 같은 수가 나오는지 봅니다. 가능한 차는 t - b = -8, -4, 0, 4입니다. t - b = -8은 (0,8) 하나뿐이라 1 · 1 = 1입니다. t - b = -4는 (0,4), (1,5), (2,6), (3,7), (4,8)이라 1 · 70 + 6 · 56 + 15 · 28 + 20 · 8 + 15 · 1 = 1001입니다. t - b = 0은 (0,0)부터 (6,6) 까지라 1 · 1 + 6 · 8 + 15 · 28 + 20 · 56 + 15 · 70 + 6 · 56 + 1 · 28 = 3003입니다. t - b = 4는 (4,0), (5,1), (6,2) 라 15 · 1 + 6 · 8 + 1 · 28 = 91입니다. 이 네 값 1, 1001, 3003, 91은 합쳐서 센 방법에서 나온 이항계수 네 개와 정확히 같고, 합은 4096입니다. 빈 그룹을 빼면 다시 N = 4095, 나머지는 95입니다.
💡핵심 정리

누구를 남기는지 세는 것은 누구를 데려가는지 세는 것과 똑같이 좋은 방법이고, 여기서는 그 한 번의 바꿔치기가 "차" 조건을 "크기" 조건으로 만듭니다. 그러면 문제는 결국 "14 명의 부분집합 중 크기가 4의 배수인 것은 몇 개인가?" 하나로 줄어듭니다.

  • 두 개수에 이름 붙이기
  • 남긴 베이스를 세기
  • 14 명을 하나로 합치기
  • 살아남는 크기 나열하기
  • 이항계수 네 개 더하기
  • 공집합을 빼고 100으로 나누기

비슷한 유형 더 풀어보기

같은 archetype · 비슷한 학년부터.