2016 AMC 10B Problem 18

P16-20~5 minPrint

Divisibility & Factors Sequences & Series Apply an identity: SFFT, sum of squares, difference of cubes, Vieta Organized listing / direct enumeration

In how many ways can $345$ be written as the sum of an increasing sequence of two or more consecutive positive integers?

Show solution without answering

Key insight

A run of k consecutive numbers starting at a adds to k(2a + k - 1)/2. So k(2a + k - 1) = 690: count factor pairs of 690.

Solution

Step 1: a formula for the sum.

1. Suppose the run has $k$ numbers and starts at $a$ : $a + (a + 1) + \cdots + (a + k - 1)$ .
2. The average of evenly spaced numbers is the average of the first and last, $\frac{a + (a + k - 1)}{2}$ . The sum is the count times the average:
$345 = k \cdot \frac{2a + k - 1}{2}, \qquad \text{so} \qquad k(2a + k - 1) = 690.$

Step 2: turn it into factor pairs.

So $690$ is split into two factors: $k$ and $m = 2a + k - 1$ .
Since $a \ge 1$ , the factor $m$ is bigger than $k$ . So $k$ is the smaller factor of the pair.
Once you pick the pair, the start is $a = \frac{m - k + 1}{2}$ . This is a whole number when $m - k$ is odd, that is, when one factor is even and the other odd.
$690 = 2 \cdot 3 \cdot 5 \cdot 23$ has only one factor of $2$ . So in every factor pair, one factor is even and the other odd. Every pair works.

Step 3: list the pairs.

$k$	$1$	$2$	$3$	$5$	$6$	$10$	$15$	$23$
$m$	$690$	$345$	$230$	$138$	$115$	$69$	$46$	$30$
start $a$	$345$	$172$	$114$	$67$	$55$	$30$	$16$	$4$

The pair with $k = 1$ is just " $345$ " by itself, which is not two or more numbers. Throw it out.
The other $7$ pairs each give a run. For example, $k = 2$ gives $172 + 173$ , and $k = 23$ gives $4 + 5 + \cdots + 26$ .

The answer is $\boxed{\textbf{(E)}\ 7}$ .

Why this works

A sum of consecutive whole numbers is "how many numbers" times "the average," which turns the question into a factoring question. Each factor pair of $2 \times 345$ with one even and one odd factor gives one run. A shortcut to remember: this count equals the number of odd divisors of $345$ (here $8$ ), minus $1$ for the one-number run.

Concise solution

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

Suppose $345 = a + (a+1) + \cdots + (a + k - 1)$ with $k \ge 2$ terms and first term $a \ge 1$ . The sum of $k$ terms is $k$ times the average of the first and last, so
$345 = \frac{k\,(2a + k - 1)}{2} \quad\Longrightarrow\quad k\,(2a + k - 1) = 690.$

The second factor $2a + k - 1$ exceeds $k$ (since $2a - 1 \ge 1$ ), so $k$ is the smaller factor in a factor pair of $690 = 2 \cdot 3 \cdot 5 \cdot 23$ . The factor pairs are
$(1, 690),\ (2, 345),\ (3, 230),\ (5, 138),\ (6, 115),\ (10, 69),\ (15, 46),\ (23, 30).$
For each pair, $a = \frac{m - k + 1}{2}$ where $m$ is the larger factor; this is a positive integer exactly when $m - k$ is odd. Since $690$ has a single factor of $2$ , one factor in every pair is even and the other odd, so every pair works.

Discard $(1, 690)$ , which is the trivial one-term sum. The remaining $7$ pairs each give a valid run, for instance $k = 2$ : $172 + 173$ , and $k = 23$ : $4 + 5 + \cdots + 26$ .

The answer is $\boxed{\textbf{(E)}\ 7}$ .

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 Algebra, Chapter 11: Special Factorizations
Prealgebra, Chapter 15: Problem-Solving Strategies (§15.2)