AMC 10 · 2016 · #19

학년 7 probability
probability-basiclattice-pathsrecursive-sequencecombinations-basic systematic-enumerationidentify-subproblems ↑ 선수 지식: probability-basiccombinations-basic
📏 긴 풀이 💡 4 개 인사이트
문제
길이가 정해진 무작위 걸음이 어느 순간 주어진 위치에 닿아야 한다. 기약 확률의 성분을 답하여라.

답을 골라 클릭하세요.

(A)
69
(B)
151
(C)
257
(D)
293
(E)
313
풀이 과정
전략 다르게 정리하기

256개의 동전 순서열을 정리하는 가장 뻔한 방법은 제리가 어디서 끝나는지로 나누는 것이다. 그런데 여기서는 그 정리가 치명적으로 정보를 잃는다. "4에 닿는다"는 것은 도착점이 아니라 여정 전체에 대한 사실이라서, 도착점이 같은 두 순서열이 서로 다른 답을 가질 수 있다. 도구 #15(다르게 정리하기)가 바로 이것을 고친다. 하나가 아니라 두 가지 정보 — 현재 위치와, 4에 이미 닿았는지를 알려주는 표시 — 로 순서열을 다시 세면 아무것도 잃지 않는다. 도구 #1(그림 그리기)은 그 표시가 의미를 갖게 하는 그림을 준다. 던지기들이 수직선 위의 걸음을 그리므로 "4에 닿았다"는 자취 전체의 성질이 된다. 도구 #7(작은 문제로 쪼개기)은 표의 각 새 줄을 서로 독립인 두 조각 — 앞서 성공한 것들을 그대로 옮긴 몫과, 이번에 처음 도착한 몫 — 으로 나눈다. 그러면 도구 #2(빠짐없이 나열하기)로 한 번씩 던지며 표를 밀어내기만 하면 되는데, 이는 순전한 덧셈이고 빠뜨리는 것이 없다.

1STEP 1

던지기를 걸음으로 바꾸기

각 던지기가 걸음 옮긴다.

t 번 던진 뒤 위치 = (지금까지 앞면 수) - (지금까지 뒷면 수), 2⁸ = 256 가지의 같은 확률 걸음
2STEP 2

도착점만으로는 부족하다

도착점만으로는 부족하다.

HHHHTTTT 와 HTHTHTHT 는 둘 다 0 에서 끝나지만, 4 에 닿는 것은 앞의 것뿐이다
3STEP 3

처음 네 번을 훑기

한 단계씩 훑으면 각 위치를 추적한다.

t=3: N(-3)=1, N(-1)=3, N(1)=3, N(3)=1, A₃=0 t=4: N(-4)=1, N(-2)=4, N(0)=6, N(2)=4, A₄=1
4STEP 4

성공은 옮기고 새 성공은 더하기

한 번 닿은 성공은 계속 이어진다.

A_t+1 = 2A_t + N_t(3) t=5: N(-5)=1, N(-3)=5, N(-1)=10, N(1)=10, N(3)=4, A₅=2 t=6: N(-6)=1, N(-4)=6, N(-2)=15, N(0)=20, N(2)=14, A₆=8
5STEP 5

일곱 번째와 여덟 번째 마무리

마지막 단계가 집계를 끝낸다.

t=7: N(-7)=1, N(-5)=7, N(-3)=21, N(-1)=35, N(1)=34, N(3)=14, A₇=16 A₈ = 2 · 16 + 14 = 46
6STEP 6

256가지 전체로 나누기

모든 걸음으로 나누면 분수가 된다.

P = A₈/2⁸ = 46/256, 46 + 210 = 256
7STEP 7

기약분수로 줄이기

약분하면 151, 보기 (B).

46/256 = 23/128, gcd(23, 128) = 1, a + b = 23 + 128 = 151 ⟹ (B)
정답
151
하한 하나와 표본 점검 하나가 23/128을 뒷받침한다. 하한: 4 이상에서 끝나는 걸음은 반드시 도중에 4에 닿았고, 그런 도착점의 개수는 256개 중 28 + 8 + 1 = 37개다. 그러므로 참값은 적어도 37/256 ≈ 0.145이고, 23/128 = 46/256 ≈ 0.180은 4에 닿았다가 다시 그 아래로 내려온 걸음 9개만큼 정확히 그 하한을 넘어선다. 이 하한만으로도 선택지 셋이 걸러진다. 256의 약수인 2의 거듭제곱을 분모로 갖는 확률은 분자와 분모가 강제되기 때문이다. (A) 69는 5/64 = 20/256을, (C) 257은 1/256을, (D) 293은 37/256을 뜻하는데, 앞의 둘은 하한보다 작고 셋째는 하한과 정확히 같다. 그런데 HHHHTTTT는 4에 닿고 0에서 끝나므로 하한과 같을 수는 없다. 표본 점검: 그 추가 9개 중 0에서 끝나는 것은 정확히 하나여야 한다. 0에서 끝난다는 것은 앞면 넷, 뒷면 넷이라는 뜻이고, 4에 닿으려면 앞면 넷이 먼저 와야 하므로 HHHHTTTT 하나뿐이다. 표를 훑어 얻은 값도 이와 일치한다. 마지막으로 앞서 한 전체 검산 46 + 210 = 256이 집계가 빠짐없음을 확인해 준다.
💡핵심 정리

어떤 수에 닿는다는 것은 도착점이 아니라 여정 전체에 대한 이야기다. 그러니 표에 "이미 닿았음"이라는 예/아니오 칸을 하나 더 만들고, 한 번씩 던지며 앞으로 밀어라.

  • 던지기를 걸음으로 바꾸기
  • 도착점만으로는 부족하다
  • 처음 네 번을 훑기
  • 성공은 옮기고 새 성공은 더하기
  • 일곱 번째와 여덟 번째 마무리
  • 256가지 전체로 나누기
  • 기약분수로 줄이기