AMC 10 · 2012 · #19

학년 7 countinglogic

유형 Casework by Position / Vertex Type └ 세부 유형 Count of Type

systematic-enumerationcombinations-basiccomplementary-counting caseworkcomplementary-counting ↑ 선수 지식: combinations-basic

📏 긴 풀이 💡 4 개 인사이트

문제

여섯 사람이 서로 짝을 맺고 모두가 같은 수의 짝을 갖는다. 가능한 배치의 수를 세어라.

답을 골라 클릭하세요.

(A)

(B)

170

(C)

290

(D)

320

(E)

660

풀이 과정

전략 빠짐없이 나열하기

"몇 가지"를 묻는 세기 문제이므로 도구 #2(빠짐없이 나열하기)가 뼈대다. 공통 친구 수 k로 경우를 나눠 각각을 깔끔히 나열한다. 먼저 도구 #4(변수 도입하기)로 k를 이름 짓고 {1,2,3,4}로 좁힌다. 그다음 도구 #16(관점 바꾸기)이 큰 짐을 덜어 준다. 모든 친구를 비친구로, 비친구를 친구로 뒤집으면 친구 k명짜리 배치가 친구 5-k명짜리 배치로 바뀌므로, k=1의 개수가 k=4의 개수와 같고 k=2의 개수가 k=3의 개수와 같아 일이 절반으로 준다. 도구 #1(그림 그리기)은 k=2의 모양(삼각형들과 육각형)을 눈에 보이게 해 빠뜨리거나 겹쳐 세지 않도록 한다. 도구 #7(작은 문제로 쪼개기)은 마무리를 깔끔히 한다. k=1을 세고, k=2를 세고, 각각 두 배로 만들어 더한다.

1STEP 1

공통 친구 수에 이름 붙이기

공통 개수는 네 값뿐이다.

k ∈ {1, 2, 3, 4}

2STEP 2

친구 관계를 뒤집어 경우를 짝짓기

관계를 뒤집으면 경우가 짝지어진다.

N₁ = N₄, N₂ = N₃ → 합계 = 2N₁ + 2N₂

3STEP 3

k = 1 세기: 세 쌍으로 나누기

짝이 하나씩이면 세 쌍으로 나뉜다.

N₁ = 5 × 3 × 1 = 15

4STEP 4

k = 2, 첫 번째 모양: 삼각형 두 개

짝이 둘씩이면 모양이 두 가지다.

(C(6, 3))/2 = 20/2 = 10

5STEP 5

k = 2, 두 번째 모양: 육각형 하나

고리 모양이 더 큰 개수다.

6!/(6 × 2) = 720/12 = 60, N₂ = 10 + 60 = 70

6STEP 6

각 경우를 두 배로 하고 더하기

두 배 해서 더하면 170, 보기 (B).

2(15) + 2(70) = 30 + 140 = 170 → (B)

정답

170

합계 170은 선택지 60과 290 사이에 있고, 어떤 부분 개수와도 같지 않아 한 경우만 성급히 답하면 여기에 닿지 않는다. 부분 개수를 교차 확인하면, k=1은 완전 짝짓기 15가지이고 이는 이중계승 5!! = 5 · 3 · 1 = 15와 일치한다. k=2의 6-고리 개수는 잘 알려진 ((6-1)!)/2 = 120/2 = 60과 맞고, 삼각형 두 개 나눔은 10이라 N₂ = 70이다. 두 배로 하여 더하면 2(15+70) = 170이다. 여집합 대칭도 자기 정합적이다. 네 경우의 개수는 15, 70, 70, 15로 가운데를 중심으로 대칭이며, 이는 친구와 남남을 뒤집는 논리가 예측하는 그대로다.

💡핵심 정리

모두가 같은 수의 친구를 가져야 할 때는 그 공통 수 k로 경우를 나눠라. 그러면 "친구"와 "남남"을 맞바꾸면 친구 k명이 5-k명으로 바뀌는 것을 알아채, 절반의 경우만 세고 두 배로 하면 된다: 2(15+70)=170.

공통 친구 수에 이름 붙이기
친구 관계를 뒤집어 경우를 짝짓기
k = 1 세기: 세 쌍으로 나누기
k = 2, 첫 번째 모양: 삼각형 두 개
k = 2, 두 번째 모양: 육각형 하나
각 경우를 두 배로 하고 더하기