AMC 10 · 2012 · #23

학년 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

AMC 10 2012 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

풀이 과정

전략 빠짐없이 나열하기

"몇 가지"를 묻는 세기 문제이므로 도구 #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라 하자. 0도 5도 아니니 k는 1, 2, 3, 4다.

k ∈ {1, 2, 3, 4}

2STEP 2

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

친구와 남남을 맞바꾸면 친구 k명이 5-k명이 되니, k=1은 k=4와, k=2는 k=3과 짝이다.

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

3STEP 3

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

각자 친구 1명이면 세 쌍으로 갈린다. 애덤은 5가지, 다음 사람은 3가지, 마지막 둘은 자동 — 15가지.

N₁ = 5 × 3 × 1 = 15

4STEP 4

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

친구 2명이면 선이 고리를 이룬다. 삼각형 둘 아니면 육각형 하나. 삼각형 둘은 6명 중 3명 고르기를 반으로 — 10가지.

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

5STEP 5

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

육각형은 여섯을 원에 앉히는 720가지에서 회전 6과 방향 2를 나눠 60가지. k=2는 모두 70가지.

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

6STEP 6

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

k=4는 k=1과, k=3은 k=2와 같으니 합은 2(15) + 2(70) = 170.

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, 두 번째 모양: 육각형 하나
각 경우를 두 배로 하고 더하기