2016 AMC 10B Problem 24

P21-25~10 minPrint

Bases & Digits Basic Counting Sequences & Series Split into exhaustive cases and handle each Use an invariant, parity, or coloring argument

How many four-digit integers $abcd$ , with $a \neq 0$ , have the property that the three two-digit integers $ab<bc<cd$ form an increasing arithmetic sequence? One such number is $4692$ , where $a=4$ , $b=6$ , $c=9$ , and $d=2$ .

Show solution without answering

Key insight

The digit b is the ones digit of ab and the tens digit of bc. Adding column by column shows the common difference is 11p or 11p + 1.

Solution

Let $D$ be the common difference, so $ab + D = bc$ and $bc + D = cd$ . Write $D$ with tens digit $p$ and ones digit $q$ (so $D = 10p + q$ ). Now do the two additions column by column, the way you would on paper.

Step 1: the first addition, $ab + D = bc$ , never carries.

Ones column: $b + q$ must end in $c$ . Either $c = b + q$ (no carry), or $c = b + q - 10$ (carry $1$ ).
Tens column of the second addition, $bc + D = cd$ : $b + p$ , plus a possible carry, gives $c$ . So $c$ is at least $b$ .
If the first ones column carried, then $c = b + q - 10$ would be less than $b$ . That contradicts step 2. So there is no carry: $c = b + q$ , and the tens column gives $b = a + p$ .

Step 2: compare the two ways of getting from $b$ to $c$ .

From the first addition: $c = b + q$ .
From the tens column of the second addition: $c = b + p$ , or $c = b + p + 1$ if the second ones column carries.
So either $q = p$ (no second carry) or $q = p + 1$ (second carry).

Step 3, case A: no carry anywhere ( $q = p$ , so $D = 11p$ ). Every digit is $p$ more than the one before: $a,\ a + p,\ a + 2p,\ a + 3p$ . We need $p \ge 1$ (the sequence increases), $a \ge 1$ , and $a + 3p \le 9$ .

$p = 1$ : $a = 1$ to $6$ , giving $1234, 2345, \ldots, 6789$ . That is $6$ numbers.
$p = 2$ : $a = 1$ to $3$ , giving $1357, 2468, 3579$ . That is $3$ numbers.
$p = 3$ would need $a + 9 \le 9$ , impossible.

Case A gives $9$ numbers.

Step 4, case B: the second ones column carries ( $q = p + 1$ , so $D = 11p + 1$ ). Then $b = a + p$ and $c = b + p + 1 = a + 2p + 1$ , and the carry means $c + q = d + 10$ , so $d = a + 3p + 2 - 10$ . We need:

$c \le 9$ : $a \le 8 - 2p$ .
$d \ge 0$ : $a \ge 8 - 3p$ .

$p$	allowed $a$	numbers
$0$	$8$	$8890$
$1$	$5, 6$	$5680, 6791$
$2$	$2, 3, 4$	$2470, 3581, 4692$
$3$	$1, 2$	$1482, 2593$
$4$	none ( $a \le 0$ )

Case B gives $1 + 2 + 3 + 2 = 8$ numbers. (The example $4692$ from the problem is here.)

Total: $9 + 8 = 17$ .

The answer is $\boxed{\textbf{(D)}\ 17}$ .

Why this works

The digits overlap: $b$ is a ones digit in $ab$ and a tens digit in $bc$ . Writing each addition column by column, with the carries shown, lets you compare two descriptions of the same step, and that pins the difference down to just two families. In digit problems, work column by column with explicit carries instead of treating the numbers as wholes.

Alternative approach

Bound and check. Twice the difference is $cd - ab$ , which is at most $98 - 10 = 88$ , so $D \le 44$ . From the column argument, $D$ is a multiple of $11$ or one more than a multiple of $11$ , so $D$ is one of $1, 11, 12, 22, 23, 33, 34, 44$ . Trying each one by hand (for example, $D = 33$ and $D = 44$ give nothing) finds the same $17$ numbers.

Concise solution

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

Let the common difference be $D = 10p + q$ with $0 \le q \le 9$ . Adding $D$ to $\overline{ab}$ must produce $\overline{bc}$ , and adding it to $\overline{bc}$ must produce $\overline{cd}$ .

Track the digits. In the first addition, the units digits satisfy $c \equiv b + q \pmod{10}$ with a carry $k_1 \in \{0, 1\}$ , and the tens digits satisfy $b = a + p + k_1$ . In the second addition, $d \equiv c + q \pmod{10}$ with carry $k_2$ , and $c = b + p + k_2$ .

The step from $b$ to $c$ appears twice: as units digits, $c = b + q - 10k_1$ ; as tens digits, $c = b + p + k_2$ . Hence $q - 10k_1 = p + k_2 \ge 0$ , which forces $k_1 = 0$ and $q = p + k_2$ . So $D = 11p + k_2$ .

Case $k_2 = 0$ : $D = 11p$ , no carries, and $a, b, c, d$ increase by $p \ge 1$ each step. Need $d = a + 3p \le 9$ with $a \ge 1$ : $p = 1$ gives $a = 1, \ldots, 6$ ( $6$ numbers such as $1234$ ), $p = 2$ gives $a = 1, 2, 3$ ( $3$ numbers such as $2468$ ). That is $9$ .

Case $k_2 = 1$ : $D = 11p + 1$ , so $b = a + p$ , $c = b + p + 1$ , and $d = c + p + 1 - 10$ . Constraints: $c = a + 2p + 1 \le 9$ and $d \ge 0$ , i.e. $a + 3p + 2 \ge 10$ . So $8 - 3p \le a \le 8 - 2p$ with $a \ge 1$ :
- $p = 0$ : $a = 8$ , giving $8890$ ( $88, 89, 90$ ).
- $p = 1$ : $a = 5, 6$ , giving $5680, 6791$ .
- $p = 2$ : $a = 2, 3, 4$ , giving $2470, 3581, 4692$ .
- $p = 3$ : $a = 1, 2$ , giving $1482, 2593$ .
That is $1 + 2 + 3 + 2 = 8$ .

Total: $9 + 8 = 17$ .

The answer is $\boxed{\textbf{(D)}\ 17}$ .

Review in the AoPS books

Introduction to Number Theory, Chapter 8: Base Numbers
Introduction to Algebra, Chapter 21: Sequences & Series (§21.1, §21.2, §21.3, §21.4)
Introduction to Counting & Probability, Chapter 1: Counting Is Arithmetic
Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques (§2.2)