2005 AMC 10B Problem 13

P11-15~3 minPrint

Inclusion-Exclusion Divisibility & Factors Set up the equation/formula and compute; no special trick needed

How many numbers between $1$ and $2005$ are integer multiples of $3$ or $4$ but not $12$ ?

Show solution without answering

Key insight

Multiples of 12 appear in both the list of multiples of 3 and the list of multiples of 4. To remove them completely, subtract their count twice.

Solution

1. Count each kind of multiple from $1$ to $2005$ .
- Multiples of $3$ : $2005 \div 3 = 668$ remainder $1$ , so there are $668$ .
- Multiples of $4$ : $2005 \div 4 = 501$ remainder $1$ , so there are $501$ .
- Multiples of $12$ : $2005 \div 12 = 167$ remainder $1$ , so there are $167$ .
2. Where are the multiples of $12$ ? A multiple of $12$ , like $24$ , is a multiple of $3$ and a multiple of $4$ . So it was counted once in the $668$ and once more in the $501$ .
3. Remove them. We want no multiples of $12$ at all. Each one was counted twice, so subtract $167$ twice:
$668 + 501 - 167 - 167 = 1169 - 334 = 835.$

The answer is $\boxed{\textbf{(C)}\ 835}$ .

Why this works

Picture two overlapping circles: multiples of $3$ and multiples of $4$ . The overlap is the multiples of $12$ . Adding the two circles counts the overlap twice. For " $3$ or $4$ " you subtract it once, but for " $3$ or $4$ but not $12$ " you want the overlap gone completely, so you subtract it twice.

Alternative approach

Look at blocks of $12$ . From $1$ to $12$ , the good numbers are $3, 4, 6, 8, 9$ : five of them ( $12$ itself is left out). Every block of $12$ numbers repeats this pattern. There are $167$ full blocks up to $2004$ , giving $167 \cdot 5 = 835$ . The last number, $2005$ , is not a multiple of $3$ or $4$ , so it adds nothing.

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

Count each kind of multiple up to $2005$ :
$\left\lfloor \frac{2005}{3} \right\rfloor = 668, \qquad \left\lfloor \frac{2005}{4} \right\rfloor = 501, \qquad \left\lfloor \frac{2005}{12} \right\rfloor = 167.$

A multiple of $12$ is a multiple of both $3$ and $4$ , so it appears in both of the first two counts. We want such numbers removed completely, so we must take them out twice:
$668 + 501 - 2 \cdot 167 = 1169 - 334 = 835.$

The answer is $\boxed{\textbf{(C)}\ 835}$ .

Review in the AoPS books

Introduction to Counting & Probability, Chapter 1: Counting Is Arithmetic (§1.3)
Introduction to Number Theory, Chapter 1: Integers: The Basics (§1.4, §1.5)
Intermediate Counting & Probability, Chapter 3: A Piece of PIE (§3.2, §3.3)
Introduction to Number Theory, Chapter 5: Divisor Problems (§5.2, §5.3)