AMC 10 · 2023 · #17

학년 11 probability

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

probability-basicgeometric-series-infinitestars-and-barsrecursive-sequence easier-related-problempattern-recognitionidentify-subproblems ↑ 선수 지식: probability-basicgeometric-series-infinite

📏 긴 풀이 💡 3 개 인사이트

문제

개구리가 수직선의 0에서 시작해 오른쪽으로만 뜁니다. 한 번 뛸 때 길이가 정수이고 길이 m으로 뛸 확률은 2의 마이너스 m제곱이며 이전 도약과 무관합니다. 개구리는 끝없이 뜁니다. 돌아오지 않으므로 어느 순간 10에 정확히 내려앉거나 10을 뛰어넘어 기회를 영영 잃습니다. 정확히 10에 내려앉을 확률을 구하세요.

답을 골라 클릭하세요.

(A)

$\frac{5}{512}$

(B)

$\frac{45}{1024}$

(C)

$\frac{127}{1024}$

(D)

$\frac{511}{1024}$

(E)

$\frac{1}{2}$

풀이 과정

전략 빠짐없이 나열하기

처음 보면 끝없는 확률 계산처럼 보입니다. 도약 한 번짜리 여정, 두 번짜리 여정, 열 번짜리 여정까지 있고, 각각 따로 무게를 재야 할 것 같기 때문입니다. 도구 #15(다르게 정리하기)가 이 두려움을 한 줄로 걷어 냅니다. 한 여정의 확률을 여러 개의 곱이 아니라 2의 거듭제곱 하나로 다시 쓰면, 지수들이 더해져 이동한 총거리가 됩니다. 그러면 10에 닿는 모든 여정은 도약 횟수와 상관없이 값이 정확히 같습니다. 무게가 모두 같아진 순간, 확률 문제는 조용히 세는 문제로 바뀝니다. 여기서부터는 도구 #2(빠짐없이 나열하기)가 주 엔진입니다. 10을 양의 정수들의 순서 있는 합으로 쓰는 방법을 세면 되고, 이는 열 개의 단위 칸 사이에 있는 아홉 개의 틈마다 끊을지 말지를 정하는 깔끔한 예-아니오 선택입니다. 도구 #4(변수 도입하기)는 결말을 우연이 아니라 필연으로 만듭니다. 목표 10을 일반적인 n으로 바꾸면 가짓수는 2^ n-1, 무게는 1/2ⁿ이 되어 n이 약분되고, 어떤 목표든 답이 같아집니다. 도구 #7(작은 문제로 쪼개기)은 첫 도약으로 경우를 나누어 완전히 독립적인 두 번째 확인을 제공합니다. 문제가 자기 자신의 축소판으로 바뀌면서 점화식이 나오고, 이를 수학적 귀납법으로 마무리하면 작은 경우에서 추측한 것이 아니라 모든 n에 대해 증명한 것이 됩니다. 도구 #5(패턴 찾기)는 그에 앞서 밑작업을 합니다. 도약 확률들의 부분합을 늘어놓으면 등비급수가 드러나고, 애초에 이것이 정당한 확률 규칙인지가 확인됩니다.

1STEP 1

규칙의 합 확인하기

확률의 합이 1입니다.

Σ_m=1^M1/2^m = 1-1/2^M ⟹ Σ_m=1^∞1/2^m = 1/2/(1-1/2) = 1

2STEP 2

모든 목표를 한꺼번에

모든 목표를 한꺼번에 묻습니다.

p_n = P(개구리의 위치가 어느 순간 n 과 같음), p₀=1, 목표: p₁₀

3STEP 3

여정 하나의 값 매기기

모든 여정의 확률이 같습니다.

P(m₁,m₂,…,m_k) = 1/2^m₁·1/2^m₂…1/2^m_k = 1/(2^ m₁+m₂+…+m_k) = 1/2ⁿ

4STEP 4

여정의 개수 세기

틈을 끊는 방법으로 셉니다.

n 에 닿는 여정의 개수 = 2^ n-1; n=10 ⟹ 2⁹ = 512

5STEP 5

개수와 값 곱하기

곱하면 목표와 무관한 값이 됩니다.

p_n = 2^ n-1·1/2ⁿ = (2^ n-1)/2ⁿ = 1/2; p₁₀ = 512·1/1024 = 512/1024 = 1/2

6STEP 6

점화식으로 확인

점화식으로 확인하면 2분의 1입니다.

p_n = 1/2ⁿ · 1 + Σ_m=1ⁿ⁻¹1/2^m·1/2 = 1/2ⁿ + 1/2(1-1/(2^ n-1)) = 1/2ⁿ + 1/2 - 1/2ⁿ = 1/2 (E)

정답

1/2

먼저 거친 점검입니다. 1/2는 0과 1 사이에 있고, 양 끝 어느 쪽에도 붙어 있지 않아야 마땅합니다. 10에 닿는 길이 512개나 되니 성공이 드물 리 없고, 반대로 11 이상으로 한 번 크게 뛰어 버리면 그것으로 끝이니 성공이 거의 확실할 리도 없습니다. 다음으로 점화식 p_n = Σ_m=1ⁿ1/2^mp_n-m을 p₀=1에서 시작해 분수 그대로 정확히 계산해 값을 읽어 봅니다. p₁=p₂=p₃=…=p₁₂=1/2로, 하나도 빠짐없이 같고 흔들림이 없습니다. 이와 별개로 여정을 전부 나열하는 완전탐색도 모든 크기에서 일치합니다. 목표 n의 여정은 2^ n-1개이고(n=1부터 10까지 1, 2, 4, 8, …, 512), 그 확률의 합은 매번 1/2입니다. 논리가 다른 두 계산이 같은 수에 닿았습니다. 마지막으로 오답 선택지를 짚어 둘 만합니다. (D) 511/1024는 아슬아슬한 함정입니다. 512/1024에서 여정 딱 하나가 모자란 값이고, 이는 틈을 셀 때의 하나 차이에서 나옵니다. '아무 데도 끊지 않는다'가 한 번에 뛰는 정당한 여정 (10)이라는 사실을 잊고 2⁹-1가지만 센 경우입니다. 512/1024가 깔끔한 1/2로 약분되기 때문에 두 선택지의 차이는 겨우 1/1024이고, 그래서 가짓수는 '거의 맞게'가 아니라 '정확히 맞게' 세야 합니다. (C) 127/1024는 (2⁷-1)/2¹⁰으로 역시 틈 세기의 실수이고, (A)와 (B)는 똑같이 유력한 여정이 512개나 있는 상황에 비해 지나치게 작습니다.

💡핵심 정리

10에 닿는 모든 길의 값이 1/1024로 똑같으므로 확률 문제가 세는 문제로 바뀝니다. 그리고 길은 512개, 곧 1024의 정확히 절반입니다.

도약 규칙의 합이 1인지 확인
모든 목표를 한꺼번에 묻기
여정 하나의 값 매기기
틈을 끊어 여정 수 세기
가짓수에 값을 곱하기
첫 도약 점화식으로 확인하기