1992 AIME Problems/Problem 6

Problem

For how many pairs of consecutive integers in $\{1000,1001,1002,\ldots,2000\}$ is no carrying required when the two integers are added?

Solution 1

For one such pair of consecutive integers, let the smaller integer be $\underline{1ABC},$ where $A,B,$ and $C$ are digits from $0$ through $9.$

We wish to count the ordered triples $(A,B,C).$ By casework, we consider all possible forms of the larger integer, as shown below. $\begin{array}{c|c|c|c|c|c|c} & & & & & & \\ [-2.5ex] \textbf{Case} & \textbf{Thousands} & \textbf{Hundreds} & \textbf{Tens} & \textbf{Ones} & \textbf{Conditions for No Carrying} & \boldsymbol{\#}\textbf{ of Ordered Triples} \\ [0.5ex] \hline & & & & & & \\ [-2ex] 0\leq C\leq 8 & 1 & A & B & C+1 & 0\leq A,B,C\leq 4 & 5^3 \\ 0\leq B\leq 8; \ C=9 & 1 & A & B+1 & 0 & 0\leq A,B\leq 4; \ C=9 & 5^2 \\ 0\leq A\leq 8; \ B=C=9 & 1 & A+1 & 0 & 0 & 0\leq A\leq 4; \ B=C=9 & 5 \\ A=B=C=9 & 2 & 0 & 0 & 0 & A=B=C=9 & 1 \end{array}$ Together, the answer is $5^3+5^2+5+1=\boxed{156}.$

~MRENTHUSIASM

Solution 2

Consider what carrying means: If carrying is needed to add two numbers with digits $abcd$ and $efgh$ , then $h+d\ge 10$ or $c+g\ge 10$ or $b+f\ge 10$ . 6. Consider $c \in \{0, 1, 2, 3, 4\}$ . $1abc + 1ab(c+1)$ has no carry if $a, b \in \{0, 1, 2, 3, 4\}$ . This gives $5^3=125$ possible solutions.

With $c \in \{5, 6, 7, 8\}$ , there obviously must be a carry. Consider $c = 9$ . $a, b \in \{0, 1, 2, 3, 4\}$ have no carry. This gives $5^2=25$ possible solutions. Considering $b = 9$ , $a \in \{0, 1, 2, 3, 4, 9\}$ have no carry. Thus, the solution is $125 + 25 + 6=\boxed{156}$ .

Solution 3

Consider the ordered pair $(1abc , 1abc - 1)$ where $a,b$ and $c$ are digits. We are trying to find all ordered pairs where $(1abc) + (1abc - 1)$ does not require carrying. For the addition to require no carrying, $2a,2b < 10$ , so $a,b < 5$ unless $1abc$ ends in $00$ , which we will address later. Clearly, if $c \in \{0, 1, 2, 3, 4 ,5\}$ , then adding $(1abc) + (1abc - 1)$ will require no carrying. We have $5$ possibilities for the value of $a$ , $5$ for $b$ , and $6$ for $c$ , giving a total of $(5)(5)(6) = 150$ , but we are not done yet.

We now have to consider the cases where $b,c = 0$ , specifically when $1abc \in \{1100, 1200, 1300, 1400, 1500, 1600, 1700, 1800, 1900, 2000\}$ . We can see that $1100, 1200, 1300, 1400, 1500$ , and $2000$ all work, giving a grand total of $150 + 6 = \boxed{156}$ ordered pairs.

Solution 4 (Complementary Counting)

Since there are $2000-1000+1 = 1001$ numbers in the set, this means that there are $1000$ consecutive pairs of integers $(a, b)$ in the set. For a pair to carry over, either the hundreds digits will carry over, the tens digits will carry over, or the ones digits will carry over.

For the hundreds digits, every consecutive pair in $\{1500, 1501, ..., 2000\}$ will have to carry over, except for the pair $\{1999, 2000\}$ when no carrying occurs, removing $500-1 = 499$ pairs.

Now, consider the case when the tens digit is more than 5. Every pair of consecutive integers from $\{1050,1051, ..., 1100\}$ will have to carry over except for the pair $\{1099, 1100\}$ , and since there are 5 of these cases less than $1500$ (namely the integers from $1050-1100$ , $1150-1200$ , $1250-1300$ , $1350-1400$ , and $1450-1500$ ) this removes $49 \cdot 5 = 245$ pairs from the list.

Now, consider the case where the ones digits carry over. In this case, every pair of consecutive integers from $\{1005, 1006, 1007, 1008, 1009\}$ carries over, removing 4 pairs. Since there are 5 possible cases for the tens digit ( $0-4$ ) and 5 possible cases for the hundreds digit, there are $4 \cdot 5 \cdot 5 = 100$ more cases to be excluded.

In total, there are $1000 - 499 - 245 - 100 = \boxed{156}$ ordered pairs.

~Soupboy0

1992 AIME (Problems • Answer Key • Resources)
Preceded by Problem 5	Followed by Problem 7
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

Page

Toolbox

Search