AMC 10 · 2019 · #16

학년 7 probability

유형 Branching State Enumeration └ 세부 유형 Markov State Probability

probability-basicindependent-eventscaseworkrecursive-sequence identify-subproblemssystematic-enumerationcasework ↑ 선수 지식: probability-basicindependent-events

📏 긴 풀이 💡 3 개 인사이트

문제

연잎이 0번부터 11번까지 한 줄로 놓여 있습니다. 피오나는 0번에서 시작해 계속 뜁니다. 한 번 뛸 때마다 앞으로 한 칸 또는 두 칸을 각각 2분의 1의 확률로 독립하게 이동합니다. 3번과 6번에는 포식자가, 10번에는 먹이가 있습니다. 3번과 6번을 한 번도 밟지 않고 어느 시점에 10번에 닿을 확률을 구하세요.

답을 골라 클릭하세요.

(A)

$\frac{15}{256}$

(B)

$\frac{1}{16}$

(C)

$\frac{15}{128}$

(D)

$\frac{1}{8}$

(E)

$\frac14$

풀이 과정

전략 작은 문제로 쪼개기

도구 #1(그림 그리기): 연잎을 한 줄로 그리고 3번과 6번에 가위표를 치면 좁은 길목이 한눈에 보인다. 도구 #3(가능성 지우기): 한 번에 최대 2칸이므로 가위표 친 연잎을 넘어가는 방법이 하나로 정해지고, 여정 중간의 선택지가 거의 다 사라진다. 도구 #7(작은 문제로 쪼개기): 그렇게 강제된 착지점이 검문소 역할을 해서 여정을 서로 독립인 세 구간으로 자르고, 독립인 구간은 곱하면 된다. 도구 #2(빠짐없이 나열하기): 각 구간은 경로를 직접 다 적을 만큼 짧다. 도구 #5(패턴 찾기): 연잎을 하나씩 따라가는 점화식 p_n = 1/2p_n-1 + 1/2p_n-2은 같은 답에 이르는 두 번째 기계적인 길을 주어 검산에 쓸 수 있다.

1STEP 1

줄을 그리고 함정을 표시하기

줄을 그리고 함정을 표시합니다.

P(+1) = P(+2) = 1/2, P(k 번 뛰는 특정 경로) = (1/2)^k

2STEP 2

함정을 넘으려면 착지점이 정해진다

함정을 넘으면 착지점이 강제됩니다.

2 → 4 그리고 5 → 7

3STEP 3

가운데 구간에는 선택의 여지가 없다

가운데 구간은 선택의 여지가 없습니다.

2 → 4 → 5 → 7

4STEP 4

여정을 세 구간으로 자르기

여정을 세 구간으로 자릅니다.

P = P(0 → 2) · P(2 → 4 → 5 → 7) · P(7 → 10)

5STEP 5

구간 (a): 2번에 도달할 확률

첫 구간의 확률을 구합니다.

P(0 → 2) = 1/4 + 1/2 = 3/4

6STEP 6

구간 (b): 강제된 길목도 세 번의 도약이 든다

강제된 길목도 도약 비용이 듭니다.

P(2 → 7) = (1/2)³ = 1/8, 3/4 · 1/8 = 3/32

7STEP 7

구간 (c): 7번에서 10번까지

마지막 구간의 확률을 구합니다.

P(7 → 10) = 1/8 + 1/4 + 1/4 = 5/8

8STEP 8

세 구간을 곱하기

세 구간을 곱하면 256분의 15입니다.

P = 3/4 · 1/8 · 5/8 = 15/256

정답

15/256

서로 독립인 두 가지 검산이 일치한다. 첫째, 분모로 확인하기. 살아남는 경로 중 가장 긴 것은 0 → 1 → 2 → 4 → 5 → 7 → 8 → 9 → 10으로 8번 뛰며 1/256을 기여한다. 8번 뛰는 생존 경로는 이것 하나뿐이고, 나머지 생존 경로는 모두 7번 이하로 뛰므로 분모가 128의 약수인 분수를 기여한다. 128분모짜리 더미에 1/256 하나를 더하면 분자가 홀수인 256분모가 되므로, 답의 기약분모는 정확히 256이다. 그런 분모를 가진 선택지는 15/256 뿐이다. 둘째, 크기로 확인하기. 15/256 ≈ 0.059로 1/16 = 0.0625 보다 조금 작다. 포식자 둘을 지나고도 10번을 지나치지 않고 정확히 내려앉아야 하니 이 정도 크기가 자연스럽다. 마지막으로 아래의 연잎별 점화식도 15/256을 그대로 재현한다.

💡핵심 정리

한 번에 1칸이나 2칸만 갈 수 있다면, 나쁜 칸을 지나는 유일한 방법은 바로 옆에 서서 뛰어넘는 것이다. 이렇게 강제된 착지점들이 길고 위험한 여정 하나를 확률을 그냥 곱하면 되는 짧은 세 구간으로 바꿔 준다.

줄을 그리고 함정을 표시하기
함정을 넘으려면 착지점이 정해진다
가운데 구간에는 선택의 여지가 없다
여정을 세 구간으로 자르기
구간 (a): 2번에 도달할 확률
구간 (b): 강제된 길목도 세 번의 도약이 든다
구간 (c): 7번에서 10번까지
세 구간을 곱하기