AMC 10 · 2021 · #16

Grade 7 counting

Archetype Overlap / Complement Counting └ Sub-archetype Complement by Subtracting Forbidden Arrangements

graph-connectivityextremal-constructionpigeonhole-principlefundamental-counting-principle extreme-principlecomplementary-counting ↑ Prerequisites: fundamental-counting-principle

📏 Long solution 💡 3 insights

Problem

An office has 30 computers, 20 of one brand and 10 of another. A cable may only join computers of different brands, and no pair may be cabled twice. Two people can communicate if their computers are joined directly or through a chain. Starting with no cables, a technician repeatedly picks one computer of each brand and installs a cable, stopping the instant everyone can reach everyone. Find the largest number of cables that could have been installed when the technician stops.

Pick an answer.

(A)

190

(B)

191

(C)

192

(D)

195

(E)

196

How to solve

Strategy Extreme Principle

The stopping rule is the whole problem. Because the technician quits the instant the network becomes one piece, the final cable is always the one that finishes the job, so the largest possible total is one more than the largest number of cables a still-broken network can hold. That converts a question about a random process into a clean extreme-value question: push the broken state as far as it will go (Extreme Principle). Drawing the setup as 20 dots facing 10 dots (Draw a Diagram) makes a broken network mean a split into two groups with no cable crossing, and naming the group sizes with letters (Introduce a Variable) turns that into an expression to maximize. Counting the cables that are missing rather than the ones that are present (Count the Complement) makes the maximum obvious in one line.

1STEP 1

Count every cable that could ever exist

Count every possible cable.

20 × 10 = 200 possible cables

2STEP 2

One cable past broken

The answer is one past the largest disconnected layout.

N = M + 1, M = max{cables in a layout that is still not all one piece}

3STEP 3

Describe a broken layout with letters

Describe a broken layout with two letters.

cables ≤ ab + (20-a)(10-b), 0 ≤ a ≤ 20, 0 ≤ b ≤ 10

4STEP 4

Count the missing cables instead

Count the missing cables instead.

cables ≤ 200 - [ a(10-b) + (20-a)b ]

5STEP 5

Push the split to its extreme

Push the split to its extreme.

loss ≥ 10, M = 200 - 10 = 190

6STEP 6

Confirm 191 always finishes the job

One more gives 191.

200 - 191 = 9 ＜ 10 → some brand-B computer keeps all 20 cables → connected

Answer

191

The count reads as 200 minus 10 plus 1. The 200 is every legal cable, the 10 is the price of keeping one brand-A computer isolated for as long as possible, and the 1 is the cable that finally connects it, which matches 191. The answer must sit below 200 and it does, and it must beat 190, since 190 cables can still leave someone cut off. The larger choices fail the gap count: 192 cables leave only 8 gaps, far too few to isolate anything, since isolating even the cheapest computer needs all 10 of its cables missing. The answer 190 is the classic trap of reporting the longest broken layout and forgetting that the technician still installs one more cable before stopping.

💡Key takeaway

When a job stops the instant everything is linked, the longest it can run is one step past the most stubborn broken state, and the cheapest way to stay broken is to leave out the single computer with the fewest possible cables.

Count every cable that could ever exist
One cable past broken
Describe a broken layout with letters
Count the missing cables instead
Push the split to its extreme
Confirm 191 always finishes the job