AMC 10 · 2017 · #25

학년 12 probability

유형 Modular Cycle Frequency Count └ 세부 유형 Power-Cycle Residue

complex-polar-formroots-of-unityprobability-basicmodular-arithmetic identify-subproblemscasework ↑ 선수 지식: complex-polar-formprobability-basic

📏 긴 풀이 💡 4 개 인사이트

문제

작은 대칭 집합에서 열두 값을 뽑아 모두 곱한다. 정해진 곱이 나올 확률을 구하여라.

답을 골라 클릭하세요.

(A)

$\dfrac{5\cdot11}{3^{10}}$

(B)

$\dfrac{5^2\cdot11}{2\cdot3^{10}}$

(C)

$\dfrac{5\cdot11}{3^{9}}$

(D)

$\dfrac{5\cdot7\cdot11}{2\cdot3^{10}}$

(E)

$\dfrac{2^2\cdot5\cdot11}{3^{10}}$

풀이 과정

전략 다르게 정리하기

직교형(a+bi)으로 보면 여섯 꼭짓점은 아무 관련 없어 보이고, 이들의 12 개 곱은 손댈 수가 없다. 그런데 극형식으로 다시 쓰면 각 꼭짓점은 두 가지 길이 중 하나에 ζ = e^iπ/4의 거듭제곱을 곱한 형태가 되고, 곱은 깔끔하게 갈라진다: 길이는 곱해지고 지수는 mod 8로 더해진다. 이 한 번의 재정리가 문제를 서로 독립인 두 개의 작은 문제로 바꾼다 — 긴 꼭짓점을 몇 번 뽑았는지에 대한 세기 문제, 그리고 지수의 합에 대한 합동식 문제.

1STEP 1

모든 꼭짓점을 극형식으로 다시 쓰기

극형식이 각 값을 길이와 각으로 만든다.

V = {√(2) ζ², √(2) ζ⁶, 1/2ζ¹, 1/2ζ³, 1/2ζ⁵, 1/2ζ⁷}, ζ = e^iπ/4

2STEP 2

목표를 길이 조건과 각 조건으로 나누기

목표가 두 조건으로 나뉜다.

P = (Π_j=1¹² r_j)ζ^{Σ_j=1¹² e_j} = -1 ⇔ Π_j=1¹² r_j = 1 그리고 Σ_j=1¹² e_j ≡ 4 (mod 8)

3STEP 3

길이 조건이 긴 꼭짓점 여덟 개를 강제한다

길이 조건이 여덟 대 넷 분할을 정한다.

(√(2))ⁿ(1/2)¹²⁻ⁿ = 2³n/2-12 = 1 → n = 8

4STEP 4

8 대 4 분할이 나올 확률

그 분할의 확률은 단순한 이항확률이다.

Pr(|P| = 1) = C(12, 4)(1/3)⁸(2/3)⁴ = (495 · 2⁴)/3¹²

5STEP 5

긴 블록이 만드는 각은 0 아니면 4

한 블록은 각을 두 가지만 만든다.

Σ_긴 e_j ≡ 4b (mod 8), #{b 짝수} = #{b 홀수} = 2⁷ = 128

6STEP 6

짧은 블록은 mod 8로 균등하다

다른 하나는 고르게 퍼져 있다.

Σ_짧은 e_j = 2K + 4 (mod 8), K 는 mod 4 에서 균등 → {0,2,4,6} 각각 64 개

7STEP 7

두 조건을 합치기

합치면 보기 (C)다.

C(12, 4)(1/3)⁸(2/3)⁴·1/4 = (495 · 2²)/3¹² = (3² · 5 · 11 · 2²)/3¹² = (2² · 5 · 11)/3¹⁰

정답

(2²·5·11)/3¹⁰

전체를 정수 개수 세기로 다시 계산해도 일치한다. 긴 선택이 여덟 번이어야 하므로 |P| = 1 인 수열은 C(12, 4) · 2⁸ · 4⁴ = 495 · 65536 = 32,440,320 개이고, 그중 정확히 4분의 1인 8,110,080 개가 지수 합 ≡ 4 (mod 8)도 만족한다. 전체 6¹² = 2,176,782,336 개에 대해 8110080/2176782336 = 220/59049 = (2² · 5 · 11)/3¹⁰이고 이는 보기 (E)이다. 크기도 그럴듯하다: 약 0.0037 인데, 필요한 8 대 4 분할이 나오는 것부터가 약 1.5% 사건이기 때문이다. 대칭성에서 검증 하나가 공짜로 더 나온다 — z₁을 역시 V 의 원소인 -z₁로 바꾸면 P = -1 인 수열과 P = +1 인 수열이 일대일로 짝지어지므로 두 개수는 같아야 하는데, 위 계산은 양쪽 모두 8,110,080을 준다.

💡핵심 정리

극형식에서 복소수의 곱은 동시에 두 개의 문제다 — 길이는 곱해지고 각은 더해진다 — 그러니 길이를 먼저 못 박고, 그다음 각을 한 바퀴로 나눈 나머지로 세면 된다.

모든 꼭짓점을 극형식으로 다시 쓰기
목표를 길이 조건과 각 조건으로 나누기
길이 조건이 긴 꼭짓점 여덟 개를 강제한다
8 대 4 분할이 나올 확률
긴 블록이 만드는 각은 0 아니면 4
짧은 블록은 mod 8로 균등하다
두 조건을 합치기