AMC 10 · 2011 · #9

학년 5 counting
combinations-basicpair-countingdouble-counting identify-subproblemscomplementary-counting ↑ 선수 지식: combinations-basic
📏 긴 풀이 💡 2 개 인사이트
📘 쉬운 버전 보기 →
문제
모두가 같은 부류의 친척이 아닌 사람 전부와, 다른 부류의 절반과 인사한다. 인사의 수를 세어라.

답을 골라 클릭하세요.

(A)
324
(B)
441
(C)
630
(D)
648
(E)
882
풀이 과정
전략 작은 문제로 쪼개기

악수에는 두 사람이 들어 있으므로, 모든 악수는 쌍둥이끼리, 세쌍둥이끼리, 또는 쌍둥이와 세쌍둥이 사이 중 하나이고 두 종류에 동시에 속하는 일은 없다. 이렇게 하면 엉킨 하나의 세기가 깔끔한 세 개로 나뉜다. 한 무리 안에서는 형제자매 짝을 빼는 편이 누가 누구와 악수하는지 직접 따라가는 것보다 쉽다. 쌍둥이-세쌍둥이 부분은 더 조심해야 한다. 문제가 이 부분을 양쪽에서 두 번 설명하므로, 양쪽으로 각각 세어 두 결과가 같은지 확인하고, 두 규칙을 실제로 만족하는 악수 방식을 하나 만들어 본다.

1STEP 1

각 무리의 인원 세기

두 무리 모두 18명으로 밝혀진다.

9 × 2 = 18 twins, 6 × 3 = 18 triplets
2STEP 2

악수를 세 종류로 나누기

인사가 종류로 나뉜다.

total = (twin--twin) + (triplet--triplet) + (twin--triplet)
3STEP 3

쌍둥이끼리: 모든 짝에서 형제자매 빼기

첫 종류는 모든 짝에서 친척을 뺀 것이다.

(18 × 17)/2 - 9 = 153 - 9 = 144
4STEP 4

세쌍둥이끼리: 형제자매 짝을 더 많이 빼기

둘째는 친척 짝을 뺀다.

(18 × 17)/2 - 6 × (3 × 2)/2 = 153 - 18 = 135
5STEP 5

양쪽에서 읽는 쌍둥이-세쌍둥이 악수

교차 인사는 양쪽에서 같게 읽힌다.

18 × 9 = 162 (twin side), 18 × 9 = 162 (triplet side)
6STEP 6

그런 모임이 가능한지 확인하기

그런 배치가 실제로 존재한다.

twin k ⟷ triplets k, k+1, …, k+8 (mod 18)
7STEP 7

세 종류를 더하기

종류를 더하면 441, 보기 (A).

144 + 135 + 162 = 441
정답
441
위쪽 한계를 잡아 보자. 36명이면 가능한 악수는 최대 (36 × 35)/2 = 630번인데, 이는 정확히 보기 (C)이고 아무도 악수를 거르지 않는 경우다. 형제자매 짝 9 + 18 = 27개가 악수하지 않고, 쌍둥이-세쌍둥이 짝 18 × 18 = 324개 중 절반은 만나지 않으므로 답은 630 - 27 - 162 = 441이어야 하고, 앞의 계산과 맞는다. 이 위쪽 한계 630은 두 보기를 바로 지운다. 648과 882는 존재하는 짝의 개수보다 크기 때문이다. 그리고 324는 쌍둥이-세쌍둥이 짝 전체의 개수로, 교차 악수만 보고 답한 값이다.
💡핵심 정리

악수를 누가 들어 있는지에 따라 나누고, 모든 짝을 센 뒤 일어나지 않는 짝을 빼고, 악수는 두 사람의 것이지만 한 번만 일어난다는 것을 기억하자.

  • 각 무리의 인원 세기
  • 악수를 세 종류로 나누기
  • 쌍둥이끼리: 모든 짝에서 형제자매 빼기
  • 세쌍둥이끼리: 형제자매 짝을 더 많이 빼기
  • 양쪽에서 읽는 쌍둥이-세쌍둥이 악수
  • 그런 모임이 가능한지 확인하기
  • 세 종류를 더하기