AMC 10 · 2005 · #25

학년 7 probability

유형 Casework by Position / Vertex Type └ 세부 유형 Count of Type

probability-basicpermutations-basicderangementfundamental-counting-principle caseworksystematic-enumerationspatial-visualization ↑ 선수 지식: probability-basicpermutations-basicfundamental-counting-principle

📏 긴 풀이 💡 4 개 인사이트

문제

정팔면체의 여섯 꼭짓점에 개미가 한 마리씩 서서 각자 무작위로 모서리 하나를 따라 이동한다. 어느 두 개미도 같은 꼭짓점에 도착하지 않을 확률을 구하여라.

답을 골라 클릭하세요.

(A)

$\frac {5}{256}$

(B)

$\frac {21}{1024}$

(C)

$\frac {11}{512}$

(D)

$\frac {23}{1024}$

(E)

$\frac {3}{128}$

풀이 과정

전략 다르게 정리하기

이 문제에서 정팔면체의 성질 중 중요한 것은 '각 꼭짓점이 맞은편 하나를 뺀 나머지 모두와 이어져 있다'는 것뿐이다. 그래서 여섯 꼭짓점을 마주 보는 세 쌍으로 묶으면 '제자리에 못 있고 맞은편으로도 못 간다'는 규칙이 '자기 쌍 안에는 도착할 수 없다'는 한 문장으로 줄어든다. 그다음에는 각 쌍에서 각 쌍으로 개미가 몇 마리 가는지만 기록한다. 이는 행과 열의 합이 모두 2이고 대각선이 0인 3 × 3 표이며, 그런 표는 단 세 가지뿐이라 손으로 끝까지 나열할 수 있고 경우를 빠뜨리거나 중복해 셀 위험이 없다.

1STEP 1

확률을 세는 문제로 바꾸기

확률이 똑같이 가능한 4096가지에 대한 세기가 된다.

4⁶ = 4096 (모두 같은 확률의 경우)

2STEP 2

이웃: 맞은편만 빼고 전부

이어지지 않은 쌍은 마주 보는 세 쌍뿐이다.

C(6, 2) - 12 = 15 - 12 = 3 개의 비이웃 쌍 = 마주 보는 세 쌍

3STEP 3

충돌이 없다는 것은 완전한 재배열

충돌이 없다는 것은 이동이 완전한 재배열이라는 뜻이다.

σ 는 6 개 꼭짓점의 순열이고 σ(v) ≠ v, σ(v) ≠ v

4STEP 4

마주 보는 꼭짓점을 세 쌍으로 묶기

마주 보는 것을 묶으면 모든 것이 한 규칙이 된다: 어느 개미도 제 쌍에 남지 않는다.

P₁ = {1, 1'}, P₂ = {2, 2'}, P₃ = {3, 3'}; v ∈ P_i → σ(v) ∉ P_i

5STEP 5

3×3 이동량 표 만들기

삼 곱하기 삼 이동량 표가 쌍 사이의 이동을 기록한다.

Σ_j M_ij = 2, Σ_i M_ij = 2, M_ii = 0

6STEP 6

가능한 표는 셋뿐

한 수가 표 전체를 정해 표는 셋뿐이다.

M = 0 & x & 2-x ; 2-x & 0 & x ; x & 2-x & 0 , x ∈ {0, 1, 2}

7STEP 7

x = 0과 x = 2: 쌍이 통째로 이동

회전하는 두 경우가 16가지를 준다.

2 · 2 · 2 = 8 (각각), 8 + 8 = 16

8STEP 8

x = 1: 모든 쌍이 갈라짐

갈라지는 경우가 64가지를 더한다.

2³ · 2³ = 8 · 8 = 64

9STEP 9

경우를 더하고 나누기

더하고 약분하면 5/256, 보기 (A).

(16 + 64)/4096 = 80/4096 = 5/256

정답

5/256

이동량 표가 아니라 재배열의 순환 모양으로 분류해 같은 80을 다시 센다. 제자리에 머무는 개미가 없으므로 길이 1인 순환은 불가능하고 2+2+2, 3+3, 4+2, 6만 남는다. 길이 2인 순환 셋은 여섯 꼭짓점을 모서리 세 개로 나누는 것인데, 여섯 점을 세 쌍으로 나누는 15가지에서 금지된 마주 보는 세 쌍에 대해 포함배제를 하면 15 - 3 · 3 + 3 - 1 = 8이 남는다. 길이 3인 순환 둘: 삼각형은 마주 보는 각 쌍에서 한 꼭짓점씩 가져와야 하므로 분할이 2³/2 = 4가지이고 각 삼각형의 방향이 2가지씩이라 4 · 2 · 2 = 16이다. 길이 4와 2: 길이 2인 순환이 될 모서리가 12가지이고, 남은 네 꼭짓점은 정확히 하나의 사각형 순환을 이루며 방향이 2가지이므로 24이다. 길이 6인 순환 하나: 여섯 점의 순환 60가지에서 금지된 세 쌍에 대해 포함배제하면 60 - 3 · 24 + 3 · 12 - 8 = 16가지(방향 무시)이므로 방향을 세면 32이다. 합하면 8 + 16 + 24 + 32 = 80으로, 완전히 다른 분류에서 같은 값이 나온다. 이 확인이 중요한 이유는 다섯 선택지가 각각 4096분의 80, 84, 88, 92, 96에 해당해 모두 2% 근처이기 때문이다. 어림으로는 절대 가려낼 수 없다.

💡핵심 정리

정팔면체에서는 각 꼭짓점이 맞은편만 빼고 전부와 이어져 있으므로, 마주 보는 것끼리 묶어 버리면 공간을 뛰어다니는 개미 여섯 마리가 손으로 끝낼 수 있는 아홉 칸짜리 표가 된다.

확률을 세는 문제로 바꾸기
이웃: 맞은편만 빼고 전부
충돌이 없다는 것은 완전한 재배열
마주 보는 꼭짓점을 세 쌍으로 묶기
3×3 이동량 표 만들기
가능한 표는 셋뿐
x = 0과 x = 2: 쌍이 통째로 이동
x = 1: 모든 쌍이 갈라짐
경우를 더하고 나누기