AMC 10 · 2017 · #25

학년 11 counting

유형 Modular Cycle Frequency Count └ 세부 유형 Floor Count Across Residue Bins

combinations-basicdivisibility-ruleschinese-remainder-theoremfactorial double-countingcasework ↑ 선수 지식: combinations-basicdivisibility-rules

📏 긴 풀이 💡 4 개 인사이트

문제

사람이 n명 있습니다. 팀은 정확히 다섯 명으로 이루어진 모임이고 두 팀이 같은 다섯 명을 갖지 않으므로, 팀들은 서로 다른 다섯 명 부분집합의 모음입니다. 아홉 명으로 된 모든 부분집합을 보고 그 안에 통째로 들어 있는 팀 수의 평균을 냅니다. 여덟 명으로 된 모든 부분집합에 대해서도 같은 평균을 냅니다. 이 두 평균이 서로 역수가 됩니다. 9 이상 2017 이하의 n 중에서 그런 팀 모음이 존재할 수 있는 n의 개수를 세세요.

답을 골라 클릭하세요.

(A)

477

(B)

482

(C)

487

(D)

557

(E)

562

풀이 과정

전략 대수로 바꾸기

문제는 평균에 관한 한 문장이므로 도구 #13 (대수로 바꾸기)이 전체를 이끈다: "한 평균이 다른 평균의 역수"를 식으로 옮기고 그 식이 무엇을 강제하는지 본다. 도구 #4 (변수 도입하기)로 평균이 의존할 수 있는 유일한 양, 곧 팀의 개수 T 에 이름을 붙인다. 도구 #15 (다르게 정리하기)가 실제 계산을 맡는다: 팀과 그룹의 짝을 그룹 쪽이 아니라 팀 쪽에서 세면 C(n, 9) 개 부분집합에 대한 합이 곱셈 한 번으로 바뀌고, 같은 이중 세기로 지저분한 비가 (C(9, 5))/(C(n, 5))로 접힌다. 조건이 나눗셈 문제로 바뀌면 도구 #7 (작은 문제로 쪼개기)로 소수 거듭제곱 2⁵, 3², 5, 7 각각에 대한 독립된 질문으로 나눈다. 도구 #5 (패턴 찾기)가 세기를 마무리한다: 남은 조건은 나머지만 읽으므로 주기 7 · 9 · 32=2016으로 반복되고, 한 주기에 양 끝 보정만 더하면 총합이 나온다.

1STEP 1

팀의 개수에 이름 붙이기

팀의 개수를 문자 하나로 둡니다.

1 ≤ T ≤ C(n, 5), TinZ

2STEP 2

평균은 전체를 그룹 수로 나눈 값

평균은 전체 나누기 모임 수입니다.

A₉=(TC(n-5, 4))/(C(n, 9)), A₈=(TC(n-5, 3))/(C(n, 8))

3STEP 3

두 평균을 접기

두 평균이 같은 인수로 접힙니다.

A₉=126 T/(C(n, 5)), A₈=56 T/(C(n, 5))

4STEP 4

역수 조건을 식으로 읽기

역수 조건이 곱을 완전제곱으로 만듭니다.

126 · 56 T²=C(n, 5)² ⟹ (84T)²=C(n, 5)² ⟹ 84T=C(n, 5)

5STEP 5

나눗셈 판정으로 바꾸기

팀 수가 정수여야 하므로 나눗셈 판정이 생깁니다.

84 | C(n, 5)⇔ 2⁵ · 3² · 5 · 7 | n(n-1)(n-2)(n-3)(n-4)

6STEP 6

소수 거듭제곱별로 나누기

소수 거듭제곱마다 남는 나머지를 따로 봅니다.

mod 7: n≡ 0,1,2,3,4; mod 9: n≢ 5,8; mod 32: n≡ 0,2,4 ( mod 8) 또는 n≡ 1,3 ( mod 16)

7STEP 7

한 주기를 세기

한 주기를 세어 옮기면 557입니다.

560-3=557 → (D)

정답

557

세 가지 확인이 서로 맞아떨어진다. 첫째, 구체적인 경우: n=10이면 C(10, 5)=252=84 · 3 이므로 T=3 개의 팀이 되어야 하고, 실제로 A₉=(126 · 3)/252=3/2, A₈=(56 · 3)/252=2/3 이며 곱이 1이다. 둘째, 밀도 추정: 세 조건은 전체 정수 중 5/7·7/9·1/2=5/18 만큼을 통과시키고 범위에는 2017-9+1=2009 개의 값이 있으므로 대략 2009·5/18≈ 558 개가 통과해야 한다. 557은 바로 그 자리에 있고, 477, 482, 487은 밀도가 1/4 근처여야 나오는 값이며 562는 끝 보정을 반영한 주기 개수를 넘어선다. 셋째, 창을 옮겨 다시 세기: 1 ≤ n ≤ 2016도 완전한 한 주기라 560 개가 통과한다. 9 ≤ n ≤ 2017로 옮기면 n=1,2,3,4가 빠지는데 이 넷은 모두 합동 조건을 만족하고, n=2017이 들어오는데 이는 2016 보다 1 크므로 n=1과 같은 나머지를 갖고 통과한다. 따라서 560-4+1=557로, 완전히 다른 계산 방식으로도 같은 값이 나온다.

💡핵심 정리

두 평균은 모두 같은 분수 T/(C(n, 5))에 상수를 곱한 것이므로 "하나가 다른 하나의 역수"라는 조건은 C(n, 5)=84T 로 접히고, 이 대회 문제 전체는 어떤 n 에서 C(n, 5)가 84의 배수가 되는지 세는 일이 된다.

팀의 개수에 이름 붙이기
평균은 전체를 그룹 수로 나눈 값
두 평균을 접기
역수 조건을 식으로 읽기
나눗셈 판정으로 바꾸기
소수 거듭제곱별로 나누기
한 주기를 세기