AMC 10 · 2011 · #9

Grade 5 counting
combinations-basicpair-countingdouble-counting identify-subproblemscomplementary-counting ↑ Prerequisites: combinations-basic
📏 Long solution 💡 2 insights
📘 View easy version →
Problem
Everyone greets all non-relatives of their own kind and exactly half of the other kind. Count the greetings.

Pick an answer.

(A)
324
(B)
441
(C)
630
(D)
648
(E)
882
How to solve
Strategy Identify Subproblems

Every handshake has two people in it, so it is twin-with-twin, triplet-with-triplet, or twin-with-triplet, and never two of those at once. That splits one tangled count into three clean ones. Inside each single group it is easier to count all pairs and subtract the sibling pairs than to count directly. The twin-with-triplet group needs more care: the problem describes it twice, once from each side, so I read it both ways and check the two readings give the same number, then build one pattern that actually obeys both rules.

1STEP 1

Count the people in each group

Both groups turn out to hold 18 people.

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

Sort handshakes into three kinds

The greetings sort into three kinds.

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

Twin-twin: all pairs minus siblings

The first kind is all pairs minus the relatives.

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

Triplet-triplet: subtract more sibling pairs

The second removes more relative pairs.

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

Cross handshakes, read from both sides

The cross greetings read the same from both sides.

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

Check such a convention can exist

Such an arrangement really exists.

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

Add the three kinds

Adding the kinds gives 441, choice (A).

144 + 135 + 162 = 441
Answer
441
Bound the answer from above. With 36 people, the most handshakes possible is (36 × 35)/2 = 630, which is exactly choice (C) and would mean nobody sits any handshake out. Since 9 + 18 = 27 sibling pairs never shake and half of the 18 × 18 = 324 twin-triplet pairs never meet, the answer has to be 630 - 27 - 162 = 441, matching the main count. That upper bound of 630 also kills two options outright: 648 and 882 are both larger than the number of pairs that exist. And 324 is just the count of all twin-triplet pairs, the number you get by looking only at the cross handshakes.
💡Key takeaway

Sort the handshakes by who is in them, count all pairs and subtract the ones that never happen, and remember each handshake belongs to two people but happens only once.

  • Count the people in each group
  • Sort handshakes into three kinds
  • Twin-twin: all pairs minus siblings
  • Triplet-triplet: subtract more sibling pairs
  • Cross handshakes, read from both sides
  • Check such a convention can exist
  • Add the three kinds