Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1992 AIME Problems/Problem 6"

m
 
(10 intermediate revisions by 7 users not shown)
Line 2: Line 2:
 
For how many pairs of consecutive integers in <math>\{1000,1001,1002,\ldots,2000\}</math> is no carrying required when the two integers are added?
 
For how many pairs of consecutive integers in <math>\{1000,1001,1002,\ldots,2000\}</math> is no carrying required when the two integers are added?
  
−
== Solution ==
+
== Solution 1 ==
−
Consider what carrying means: If carrying is needed to add two numbers with digits <math>abcd</math> and <math>efgh</math>, then <math>h+d\ge 10</math> or <math>c+g\ge 10</math> or <math>b+f\ge 10</math>. 6.  Consider <math>c \in \{0, 1, 2, 3, 4\}</math>. <math>1abc + 1abc+1</math> has no carry if <math>a, b \in \{0, 1, 2, 3, 4\}</math>. This gives <math>5^3=125</math> possible solutions.  
+
For one such pair of consecutive integers, let the smaller integer be <math>\underline{1ABC},</math> where <math>A,B,</math> and <math>C</math> are digits from <math>0</math> through <math>9.</math>
 +
 
 +
We wish to count the ordered triples <math>(A,B,C).</math> By casework, we consider all possible forms of the larger integer, as shown below.
 +
<cmath>\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}</cmath>
 +
Together, the answer is <math>5^3+5^2+5+1=\boxed{156}.</math>
 +
 
 +
~MRENTHUSIASM
 +
 
 +
== Solution 2 ==
 +
Consider what carrying means: If carrying is needed to add two numbers with digits <math>abcd</math> and <math>efgh</math>, then <math>h+d\ge 10</math> or <math>c+g\ge 10</math> or <math>b+f\ge 10</math>. 6.  Consider <math>c \in \{0, 1, 2, 3, 4\}</math>. <math>1abc + 1ab(c+1)</math> has no carry if <math>a, b \in \{0, 1, 2, 3, 4\}</math>. This gives <math>5^3=125</math> possible solutions.  
  
 
With <math>c \in \{5, 6, 7, 8\}</math>, there obviously must be a carry. Consider <math>c = 9</math>. <math>a, b \in \{0, 1, 2, 3, 4\}</math> have no carry. This gives <math>5^2=25</math> possible solutions. Considering <math>b = 9</math>,  <math>a \in \{0, 1, 2, 3, 4, 9\}</math> have no carry. Thus, the solution is <math>125 + 25 + 6=\boxed{156}</math>.  
 
With <math>c \in \{5, 6, 7, 8\}</math>, there obviously must be a carry. Consider <math>c = 9</math>. <math>a, b \in \{0, 1, 2, 3, 4\}</math> have no carry. This gives <math>5^2=25</math> possible solutions. Considering <math>b = 9</math>,  <math>a \in \{0, 1, 2, 3, 4, 9\}</math> have no carry. Thus, the solution is <math>125 + 25 + 6=\boxed{156}</math>.  
  
 +
== Solution 3 ==
 +
Consider the ordered pair <math>(1abc , 1abc - 1)</math> where <math>a,b</math> and <math>c</math> are digits. We are trying to find all ordered pairs where <math>(1abc) + (1abc - 1)</math> does not require carrying. For the addition to require no carrying, <math>2a,2b < 10</math>, so <math>a,b < 5</math> unless <math>1abc</math> ends in <math>00</math>, which we will address later.  Clearly, if <math>c \in \{0, 1, 2, 3, 4 ,5\}</math>, then adding <math>(1abc) + (1abc - 1)</math> will require no carrying. We have <math>5</math> possibilities for the value of <math>a</math>, <math>5</math> for <math>b</math>, and <math>6</math> for <math>c</math>, giving a total of <math>(5)(5)(6) = 150</math>, but we are not done yet.
 +
 +
We now have to consider the cases where <math>b,c = 0</math>, specifically when <math>1abc \in \{1100, 1200, 1300, 1400, 1500, 1600, 1700, 1800, 1900, 2000\}</math>. We can see that <math>1100, 1200, 1300, 1400, 1500</math>, and <math>2000</math> all work, giving a grand total of <math>150 + 6 = \boxed{156}</math> ordered pairs.
 +
 +
== Solution 4 (Complementary Counting) ==
 +
Since there are <math>2000-1000+1 = 1001</math> numbers in the set, this means that there are <math>1000</math> consecutive pairs of integers <math>(a, b)</math> 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 <math>\{1500, 1501, ..., 2000\}</math> will have to carry over, except for the pair <math>\{1999, 2000\}</math> when no carrying occurs, removing <math>500-1 = 499</math> pairs.
 +
 +
Now, consider the case when the tens digit is more than 5. Every pair of consecutive integers from  <math>\{1050,1051, ..., 1100\}</math> will have to carry over except for the pair <math>\{1099, 1100\}</math>, and since there are 5 of these cases less than <math>1500</math> (namely the integers from <math>1050-1100</math>, <math>1150-1200</math>, <math>1250-1300</math>,  <math>1350-1400</math>, and <math>1450-1500</math>) this removes <math>49 \cdot 5 = 245</math> pairs from the list.
 +
 +
Now, consider the case where the ones digits carry over. In this case, every pair of consecutive integers from <math>\{1005, 1006, 1007, 1008, 1009\}</math> carries over, removing 4 pairs. Since there are 5 possible cases for the tens digit (<math>0-4</math>) and 5 possible cases for the hundreds digit, there are <math>4 \cdot 5 \cdot 5 = 100</math> more cases to be excluded. 
 +
 +
In total, there are <math>1000 - 499 - 245 - 100 = \boxed{156}</math> consecutive pairs.
 +
 +
~Soupboy0
 +
 +
==See also==
 
{{AIME box|year=1992|num-b=5|num-a=7}}
 
{{AIME box|year=1992|num-b=5|num-a=7}}
  
 
[[Category:Intermediate Number Theory Problems]]
 
[[Category:Intermediate Number Theory Problems]]
 +
{{MAA Notice}}

Latest revision as of 12:27, 16 January 2025

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}$ consecutive pairs.

~Soupboy0

See also

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

These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions. AMC Logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1992_AIME_Problems/Problem_6&oldid=240252"