AMC 10 · 2014 · #13

Grade 7 counting
Archetype Casework by Position / Vertex Type └ Sub-archetype Count of Type
combinations-basicfundamental-counting-principleset-partitioncomplementary-counting identify-subproblemscaseworkcomplementary-counting ↑ Prerequisites: combinations-basicfundamental-counting-principle
📏 Medium solution 💡 3 insights
Problem
Each of five people goes to one of five distinct rooms, and no room may hold three. Count the assignments.

Pick an answer.

(A)
2100
(B)
2220
(C)
3000
(D)
3120
(E)
3125
How to solve
Strategy Identify Subproblems

Dropping the cap gives 5⁵ = 3125 assignments, far too many to list, so I need structure. Every legal assignment has a shape: how many rooms hold 2 friends, how many hold 1, how many are empty. Sorting by shape splits the count into a few subproblems that cannot overlap, since an assignment has only one shape. The risky part of any casework is a missing case, so before counting anything I name the number of double rooms as a variable and solve a small equation to prove the shape list is complete and that each shape actually fits in 5 rooms. Inside each shape I separate two different kinds of choice, which rooms play which role and which friends go where, and multiply. At the end I redo the whole count by the complement, subtracting the overloaded assignments from 3125, as an independent check.

1STEP 1

Count with the cap switched off

Without the cap the count is 3125.

5 · 5 · 5 · 5 · 5 = 5⁵ = 3125
2STEP 2

Prove there are exactly three shapes

The cap leaves exactly three shapes.

2k + s = 5, s ≥ 0 → k ≤ 5/2 → k ∈ {0, 1, 2}, s = 5 - 2k
3STEP 3

Shape (1,1,1,1,1): one friend per room

One person per room gives 120.

5 · 4 · 3 · 2 · 1 = 5! = 120
4STEP 4

Shape (2,1,1,1): one double, one empty

One doubled room gives 1200.

5 · 4 · C(5, 2) · 3! = 5 · 4 · 10 · 6 = 1200
5STEP 5

Shape (2,2,1): two doubles, two empty

Two doubled rooms give 900.

C(5, 2) · 3 · 5 · C(4, 2) = 10 · 3 · 5 · 6 = 900
6STEP 6

Add the three shapes

Adding gives 2220, choice (B).

120 + 1200 + 900 = 2220
Answer
2220
The total must sit below the no-cap count 3125, and 2220 does, using about 71% of all assignments, which fits: piling 3 friends into one room is possible but not the usual outcome when 5 people spread over 5 rooms. The wrong choices are also readable as specific slips. Choice (E) 3125 is the count with the cap ignored. Choice (D) 3120 = 3125 - 5 subtracts only the 5 assignments that put everyone in one room and forgets rooms holding exactly 3 or exactly 4. Choice (A) 2100 = 1200 + 900 is exactly what comes out if the all-singles shape is dropped from the case list, which is why proving in step 2 that the shape list is complete is the part that carries the problem. One more sanity check on the setup: if the inn had instead required every room to be used, only the shape (1,1,1,1,1) would survive and the count would drop to 120, so allowing empty rooms is doing real work here.
💡Key takeaway

Sort the possibilities by shape, prove the list of shapes leaves nothing out, then count each shape by deciding what every room's job is before deciding who goes in it.

  • Count with the cap switched off
  • Prove there are exactly three shapes
  • Shape (1,1,1,1,1): one friend per room
  • Shape (2,1,1,1): one double, one empty
  • Shape (2,2,1): two doubles, two empty
  • Add the three shapes

More like this

Same archetype — closest grade level first.