AMC 10 · 2008 · #22

학년 11 probability

유형 Overlap / Complement Counting └ 세부 유형 Complement by Subtracting Forbidden Arrangements

complementary-countingcombinations-basicstars-and-barsprobability-basic complementary-countingeasier-related-problem ↑ 선수 지식: combinations-basicprobability-basic

📏 긴 풀이 💡 3 개 인사이트

문제

차들이 한 줄의 주차 칸을 하나씩 채우며, 매번 남은 칸 중에서 균등하게 고른다. 늦게 온 사람은 이웃한 빈 칸 둘이 필요하다. 그런 쌍이 있을 확률을 구하여라.

답을 골라 클릭하세요.

(A)

$\frac {11}{20}$

(B)

$\frac {4}{7}$

(C)

$\frac {81}{140}$

(D)

$\frac {3}{5}$

(E)

$\frac {17}{28}$

풀이 과정

전략 관점 바꾸기

도구 #15(다르게 정리하기)가 모두가 건너뛰는 일을 맡는다. 문제가 말하는 것은 과정이다. 운전자 열두 명이 점점 줄어드는 선택지에서 한 명씩 고른다. 그런데 깔끔한 풀이들은 하나같이 남은 빈 칸 4개를 균등하게 무작위로 뽑은 4원소 부분집합인 것처럼 조용히 취급한다. 이 둘은 서로 다른 진술이고, 두 번째 것은 증명해서 얻어내야 한다. 과정을 선택의 순서 목록으로 다시 적은 뒤, 목록을 집합으로 뭉개면서 같은 집합을 주는 목록이 몇 개인지 세면 된다. 그다음 도구 #16(관점 바꾸기)으로 사건을 뒤집는다. "빈 칸 중 적어도 두 개가 붙어 있다"는 겹치는 경우들의 뒤엉킴이지만 "어느 두 빈 칸도 붙어 있지 않다"는 하나의 깔끔한 모양이기 때문이다. 도구 #4(변수 도입하기)로 빈 칸 네 곳을 a₁ ＜ a₂ ＜ a₃ ＜ a₄로 이름 붙이면 "붙어 있지 않다"가 부등식 a_i+1 ≥ a_i + 2가 되고, 밀기 대응이 이것을 13개 중 4개를 고르는 평범한 문제로 바꾼다. 그리고 이 밀기 대응은 역대응까지 함께 제시하므로 그럴듯한 짝짓기가 아니라 진짜 일대일 대응이다. 도구 #3(가능성 지우기)으로 마무리한다. 다섯 선택지가 0.06 안에 몰려 있어서 정확한 분수만이 답을 가른다.

1STEP 1

균등 모형을 증명해서 얻기

빈 칸의 모든 집합이 똑같이 나올 확률이고 이는 증명해야 한다.

Pr(목록) = 1/(16 · 15 … 5) (모든 목록 공통); #{T 를 주는 목록} = 12! (모든 T 공통) ⟹ Pr(T) = 12!/(16 · 15 … 5) = 1/(C(16, 4))

2STEP 2

주차 가능 조건을 인접 조건으로

주차 가능은 빈 칸 집합이 이웃한 둘을 포함한다는 뜻이다.

주차 가능 ⇔ ∃ i ∈ {1,…,15}: i 번과 i+1 번이 모두 빈칸; Pr(주차) = 1 - Pr(어느 두 빈 칸도 안 붙음)

3STEP 3

빈 칸 네 개를 밀어 붙이기

밀어 옮기면 이웃하지 않는 집합 세기가 쉬워진다.

b_i = a_i - (i-1) ⟷ a_i = b_i + (i-1); #{[16] 안의 안 붙은 4 원소 집합} = C(13, 4)

4STEP 4

실패 확률 계산하기

그것이 실패 확률을 11/28로 준다.

Pr(어느 두 빈 칸도 안 붙음) = (C(13, 4))/(C(16, 4)) = 715/1820 = 11/28

5STEP 5

빼서 주차 확률 구하기

빼면 17/28이다.

Pr(주차) = 1 - 11/28 = 17/28 = 1105/1820

6STEP 6

다섯 선택지 갈라내기

소수로 보면 다섯 보기가 깔끔히 갈려 17/28이 확인된다, 보기 (E).

0.550, 0.5714, 0.5786, 0.600, 0.6071 → 17/28 = (E)

정답

17/28

서로 독립적인 확인 세 가지. (1) 크기 감각: 16칸 중 빈 칸이 4개일 때 인접 쌍은 15개이고, 특정 쌍이 통째로 비어 있을 확률은 4/16 · 3/15 = 1/20이므로 비어 있는 인접 쌍의 기댓값은 15 · 1/20 = 0.75다. "적어도 하나"의 확률이 약 0.61인 것은 이 기댓값보다 낮으면서 1/2보다는 넉넉히 큰 자리로, 17/28 ≈ 0.607이 정확히 그렇다. (2) 손으로 나열할 만큼 작은 경우로 공식 확인: 4칸짜리 줄에서 붙어 있지 않은 2원소 집합은 {1,3}, {1,4}, {2,4}의 세 개이고, 밀기 공식은 C(4-2+1, 2) = C(3, 2) = 3을 준다. 일치한다. 다만 일반 개수 C(n-k+1, k)은 이 작은 경우에서 읽어낸 것이 아니라 역대응으로 증명한 것이다. (3) 경계 감각: 자동차가 13대 왔다면 빈 칸은 3개뿐이고 실패 확률은 (C(14, 3))/(C(16, 3)) = 364/560 = 13/20이 되어 주차 확률은 7/20 = 0.35로 떨어진다. 빈 칸이 줄면 주차가 어려워져야 하고 실제로 그렇다. 함정 선택지는 (D) 3/5 = 0.600으로 참값보다 0.007 아래에 있어, 계산하지 않고 어림한 사람을 정확히 노린다.

💡핵심 정리

차들이 한 대씩 주차하면 빈 칸 네 개의 모든 조합이 똑같이 나올 법해지므로, 문제는 결국 "열여섯 칸에서 고른 네 칸이 서로 안 닿을 확률은?"이 된다. 그 네 칸을 왼쪽으로 0, 1, 2, 3칸씩 밀면 강제된 간격이 사라져서 열세 칸에서 네 칸을 고르는 평범한 문제가 된다.

균등 모형을 증명해서 얻기
주차 가능 조건을 인접 조건으로
빈 칸 네 개를 밀어 붙이기
실패 확률 계산하기
빼서 주차 확률 구하기
다섯 선택지 갈라내기