AMC 10 · 2005 · #18
Grade 10 number-theoryPick an answer.
Prime-looking is defined by two negatives at once: not prime, and not divisible by 2, 3, or 5. Hunting for such numbers one at a time is slow, and that is exactly why the problem hands over the count of primes. Instead, sort all 999 numbers into four groups that overlap nowhere and miss nothing, count the three easy groups, and read off the fourth.
Fix the range and the definition
The range holds 999 numbers, and the definition needs both parts.
Getting the size of the whole crowd first is what makes subtracting the rest possible.
4.OA.B.4Change Focus Count The ComplementSplit 1 to 999 into four groups
Sorting into disjoint groups makes the four counts add to the whole.
Once the boxes cover everything without overlapping, the unknown box is whatever the others leave behind.
10.S-CP.A.1Identify SubproblemsCount the multiples of 2, 3, and 5
Dividing and dropping remainders counts each factor's multiples.
How many multiples of d fit below a bound is simply how many times d fits into that bound.
6.NS.B.2Identify SubproblemsTurn the overlaps into single divisors
Overlaps become single divisors through the least common multiple.
Two divisibility conditions at once are one divisibility condition by the least common multiple.
6.NS.B.4Draw A Venn DiagramApply inclusion and exclusion
Inclusion and exclusion gives 733 with a small factor.
Add the circles, take back the overlaps, then restore the middle that got removed one time too many.
Add the three counts, take back every pairwise overlap, then restore the middle that was removed one time too many.
▸ Why?
A count of overlapping groups double-counts whatever they share, so the shared parts have to be added and removed in turn.
▸ Why?
Being divisible by two numbers at once is the same as being divisible by their least common multiple.
Subtract down to the answer
Removing one and the remaining primes leaves 100, choice (A).
The group you cannot list directly is whatever survives after the groups you can count are removed.
4.OA.A.3Change Focus Count The ComplementWhen a group is described by what it is not, count the whole crowd, count everybody else, and subtract.
- Fix the range and the definition
- Split 1 to 999 into four groups
- Count the multiples of 2, 3, and 5
- Turn the overlaps into single divisors
- Apply inclusion and exclusion
- Subtract down to the answer