AMC 10 · 2017 · #22

학년 11 probability

유형 Branching State Enumeration └ 세부 유형 Constrained Sequence or Path Count

probability-basicpermutations-basiccombinations-basic caseworksystematic-enumeration ↑ 선수 지식: probability-basicpermutations-basic

📏 중간 풀이 💡 4 개 인사이트

문제

네 사람이 각각 동전 4개로 시작합니다. 네 번의 라운드마다 한 사람을 무작위로 골라 다른 한 사람에게 동전 한 개를 건네게 합니다. 주는 사람과 받는 사람의 순서쌍은 모두 똑같이 나올 수 있습니다. 네 번째 라운드가 끝났을 때 네 사람이 다시 정확히 4개씩 갖고 있을 확률을 구하세요.

답을 골라 클릭하세요.

(A)

$\dfrac{7}{576}$

(B)

$\dfrac{5}{192}$

(C)

$\dfrac{1}{36}$

(D)

$\dfrac{5}{144}$

(E)

$\dfrac{7}{48}$

풀이 과정

전략 다르게 정리하기

네 사람의 동전 더미를 네 라운드 내내 쫓아다니면 문제가 계산 장부에 파묻힌다. 도구 #15(다르게 정리하기)는 각 라운드를 주는 사람에서 받는 사람으로 향하는 화살표 하나로 다시 기록한다. 그러면 게임 전체가 이름 붙은 점 네 개 위에 화살표 네 개를 그린 그림 하나가 되고, 목표는 "모든 점에서 나가는 화살표 수와 들어오는 화살표 수가 같아야 한다"는 깔끔한 구조 조건으로 바뀐다. 도구 #1(그림 그리기)은 그 재해석을 종이 위에 눈으로 보이게 만든다. 이어서 도구 #7(작은 문제로 쪼개기)이 세는 일을 서로 독립인 두 부분으로 나눈다. 어떤 화살표 네 개가 등장하는가, 그리고 네 라운드가 그것들을 어떤 순서로 만들어 내는가이다. 마지막으로 도구 #2(빠짐없이 나열하기)가 균형을 이룰 수 있는 화살표 모양을 겹침 없이, 빠짐없이 나열해 마무리한다.

1STEP 1

한 라운드를 화살표 하나로

한 라운드는 화살표 하나입니다.

4 × 3 = 12 ⟹ 12⁴ = 20736 (같은 확률의 수열 개수)

2STEP 2

원상 복귀는 나감과 들어옴이 같다는 뜻

원상 복귀는 각자 준 만큼 받는다는 뜻입니다.

4 - 나감 + 들어옴 = 4 ⇔ 모든 사람에 대해 나감 = 들어옴

3STEP 3

균형 잡힌 화살표는 고리로 쪼개진다

균형 잡힌 화살표는 고리로 쪼개집니다.

4 = 2 + 2 또는 4 = 4 (4 = 3 + 1 은 불가능)

4STEP 4

고리 두 개짜리 모양 세기

고리 두 개짜리는 같은 짝을 두 번 쓰는 경우도 포함합니다.

C(4, 2) · 4!/2! 2! = 6 · 6 = 36 C(6, 2) · 4! = 15 · 24 = 360

5STEP 5

고리 하나짜리 모양 세기

네 명이 도는 큰 고리도 따로 셉니다.

3 · 2 · 4! = 6 · 24 = 144

6STEP 6

경우를 더하고 나누기

모두 더해 나누면 192분의 5입니다.

(36 + 360 + 144)/12⁴ = 540/20736 = 5/192 ⟹ (B)

정답

5/192

세지 않고도 답의 크기를 가늠하는 상한 논증이 있다. 세 라운드가 지나면 동전이 세 번 움직였으므로 더미가 이미 평평할 수는 없다. 그리고 한 번의 이동은 정확히 두 사람을 ± 1만큼 바꾸므로, 네 번째 라운드가 모두를 평평하게 만들 수 있는 유일한 경우는 세 라운드 뒤 정확히 한 사람이 5개, 한 사람이 3개, 두 사람이 4개를 가진 상태이다. 그러면 네 번째 라운드는 5개인 사람에서 3개인 사람으로 가는 그 특정한 화살표여야 하고, 그 확률은 1/12이다. 즉 답은 1/12에 어떤 확률을 곱한 값이므로 절대 1/12을 넘을 수 없고, 이 사실만으로도 (E) 7/48은 배제된다. (E)라면 그 확률이 7/4이어야 하기 때문이다. 같은 등식을 반대로 읽으면 5/192 = 1/12 × 5/16이므로, 세 라운드 뒤 정확히 한 사람이 올라가고 한 사람이 내려간 상태일 확률이 5/16이라는 주장이 된다. 나머지 상태들이 눈에 띄게 더 흩어진 드문 상태임을 생각하면 충분히 납득할 만한 값이다. 마지막으로 계산 점검 하나. 확률은 20736분의 정수 꼴이어야 하는데 5/192 = 540/20736이므로 약분 과정에도 문제가 없다.

💡핵심 정리

동전을 건네는 일을 화살표로 그려 보면, 모두가 처음 자리로 돌아오는 것은 화살표들이 고리로 닫힐 때뿐이고, 그다음에 할 일은 그 고리를 세는 것뿐이다.

한 라운드를 화살표 하나로
원상 복귀는 나감과 들어옴이 같다는 뜻
균형 잡힌 화살표는 고리로 쪼개진다
고리 두 개짜리 모양 세기
고리 하나짜리 모양 세기
경우를 더하고 나누기