2005 AMC 10A Problem 21

P21-25~3 minPrint

Divisibility & Factors Sequences & Series Set up the equation/formula and compute; no special trick needed

For how many positive integers $n$ does $1+2+\dotsb+n$ evenly divide $6n$ ?

Show solution without answering

Key insight

The sum is n(n+1)/2. Dividing 6n by it leaves 12 over (n+1), so n+1 must be a divisor of 12 bigger than 1.

Solution

Start with a few small cases to see what is being asked.

$n$	$1 + \cdots + n$	$6n$	divides?
$1$	$1$	$6$	yes
$2$	$3$	$12$	yes
$3$	$6$	$18$	yes
$4$	$10$	$24$	no
$5$	$15$	$30$	yes

Checking forever is not possible, so use the formula for the sum.

1. Formula. $1 + 2 + \cdots + n = \frac{n(n + 1)}{2}$ .
2. Divide. We want $6n$ divided by this to be a whole number:
$6n \div \frac{n(n + 1)}{2} = \frac{12n}{n(n + 1)} = \frac{12}{n + 1}.$
The $n$ cancels because $n$ is positive.
3. So $n + 1$ must divide $12$ . The divisors of $12$ are $1, 2, 3, 4, 6, 12$ .
4. Remove the one that is too small. $n$ is positive, so $n + 1$ is at least $2$ . That leaves $n + 1 = 2, 3, 4, 6, 12$ , so $n = 1, 2, 3, 5, 11$ .
5. Check the biggest. $1 + \cdots + 11 = 66$ and $6 \times 11 = 66$ . It divides.

That is $5$ values, which matches the table ( $n = 4$ fails because $5$ does not divide $12$ ).

The answer is $\boxed{\textbf{(B)}\ 5}$ .

Why this works

Replacing a long sum with its formula turns "does this sum divide that number?" into a simple fraction. Once the question becomes "when is $\frac{12}{n + 1}$ a whole number?", the answer is a list of divisors of $12$ , trimmed to the values $n + 1$ can actually take.

Concise solution

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

The sum is $\frac{n(n+1)}{2}$ . The requirement is that
$\frac{6n}{\,n(n+1)/2\,} = \frac{12n}{n(n+1)} = \frac{12}{n+1}$
be an integer, i.e. $n + 1$ divides $12$ .

The divisors of $12$ are $1, 2, 3, 4, 6, 12$ . Since $n \geq 1$ , we need $n + 1 \geq 2$ , leaving $n + 1 \in \{2, 3, 4, 6, 12\}$ and $n \in \{1, 2, 3, 5, 11\}$ .

Quick check of the largest: $1 + \dots + 11 = 66$ and $6 \cdot 11 = 66$ , so it divides. There are $5$ values.

The answer is $\boxed{\textbf{(B)}\ 5}$ .

Review in the AoPS books

Introduction to Number Theory, Chapter 1: Integers: The Basics (§1.4, §1.5)
Introduction to Algebra, Chapter 21: Sequences & Series (§21.1, §21.2, §21.3, §21.4)
Introduction to Number Theory, Chapter 5: Divisor Problems (§5.2, §5.3)
Intermediate Algebra, Chapter 17: More Sequences and Series (§17.1, §17.2)