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 "2003 AMC 10B Problems/Problem 25"

(→‎See also)
(→‎Solution 6 (Even Faster than Even Faster than Extremely Fast))
 
(63 intermediate revisions by 37 users not shown)
Line 1: Line 1:
 
==Problem==
 
==Problem==
  
−
How many distinct four-digit numbers are divisible by <math> 3 </math> and have <math> 23 </math> as their last two digits?
+
How many distinct four-digit numbers are divisible by <math>3</math> and have <math>23</math> as their last two digits?
  
−
<math> \textbf{(A) }27\qquad\textbf{(B) }30\qquad\textbf{(C) }33\qquad\textbf{(D) }81\qquad\textbf{(E) }90 </math>
+
<math>\textbf{(A) } 27 \qquad\textbf{(B) } 30 \qquad\textbf{(C) } 33 \qquad\textbf{(D) } 81 \qquad\textbf{(E) } 90</math>
  
 
==Solution==
 
==Solution==
−
===Solution 1===
+
===Solution 1 (Slow)===
 
To test if a number is divisible by three, you add up the digits of the number. If the sum is divisible by three, then the original number is a multiple of three. If the sum is too large, you can repeat the process until you can tell whether it is a multiple of three. This is the basis for the solution. Since the last two digits are <math> 23 </math>, the sum of the digits is <math> 2+3 = 5 </math> (therefore it is not divisible by three). However certain numbers can be added to make the sum of the digits a multiple of three.
 
To test if a number is divisible by three, you add up the digits of the number. If the sum is divisible by three, then the original number is a multiple of three. If the sum is too large, you can repeat the process until you can tell whether it is a multiple of three. This is the basis for the solution. Since the last two digits are <math> 23 </math>, the sum of the digits is <math> 2+3 = 5 </math> (therefore it is not divisible by three). However certain numbers can be added to make the sum of the digits a multiple of three.
  
Line 33: Line 33:
  
 
<cmath> 1+4+7+9+6+3 = \boxed{\textbf{(B)}\ 30} </cmath>
 
<cmath> 1+4+7+9+6+3 = \boxed{\textbf{(B)}\ 30} </cmath>
−
+
 
−
===Solution 2===
+
===Solution 2 (Medium)===
 
A number divisible by <math>3</math> has all its digits add to a multiple of <math>3.</math> The last two digits are <math>2</math> and <math>3</math> and add up to <math>5 \equiv 2\ (\text{mod}\ 3).</math> Therefore the first two digits must add up to <math>1\ (\text{mod}\ 3).</math> <math>4</math> digits (including <math>0</math>) are <math>0\ (\text{mod}\ 3),</math> <math>3</math> are <math>1\ (\text{mod}\ 3),</math> and <math>3</math> are <math>2\ (\text{mod}\ 3).</math> The following combinations are equivalent to <math>1\ (\text{mod}\ 3)</math>:
 
A number divisible by <math>3</math> has all its digits add to a multiple of <math>3.</math> The last two digits are <math>2</math> and <math>3</math> and add up to <math>5 \equiv 2\ (\text{mod}\ 3).</math> Therefore the first two digits must add up to <math>1\ (\text{mod}\ 3).</math> <math>4</math> digits (including <math>0</math>) are <math>0\ (\text{mod}\ 3),</math> <math>3</math> are <math>1\ (\text{mod}\ 3),</math> and <math>3</math> are <math>2\ (\text{mod}\ 3).</math> The following combinations are equivalent to <math>1\ (\text{mod}\ 3)</math>:
  
Line 42: Line 42:
  
 
<cmath>3\cdot3 + 3\cdot4 + 3\cdot3 = 9 + 12 + 9 = \boxed{\textbf{(B)}\ 30}</cmath>
 
<cmath>3\cdot3 + 3\cdot4 + 3\cdot3 = 9 + 12 + 9 = \boxed{\textbf{(B)}\ 30}</cmath>
 +
 +
===Solution 3 (Fast)===
 +
 +
We have the following: <math> n \equiv 0 \pmod{3}</math> and <math>n \equiv 23\pmod{100}</math>. Then <math>n = 3a = 100b+23</math> for some integers <math>a</math> and <math>b</math>.  Taking mod 3 gives:
 +
<math>0 \equiv b+2 \pmod 3 \implies b\equiv 1\pmod 3</math> so <math>b=3c+1 </math> for some integer <math>c</math>.  But <math>N = 100b+23 = 100(3c+1)+23</math> so <math>n = 300c+123</math>.  Bounding this gives us:
 +
<math>999 < 300c+123 < 10000</math> so <math>876 < 300c < 9877</math>.  Dividing by <math>300</math> gives <math>2.92 < c < 32.9222</math> so <math>3\le c \le 32</math>.  This gives <math>32-3+1 = \boxed{\textbf{(B)} \ 30 }</math>
 +
 +
===Solution 4 (Extremely Fast)===
 +
 +
The number is in the form <math>xy23</math>
 +
 +
Notice that the number is divisible by <math>3</math> if the sum of the digits of <math>xy23</math> is divisible by <math>3</math>
 +
 +
Our first number that is divisible by <math>3</math> is <math>1023</math>, next is <math>1323</math>..
 +
Notice <math>xy</math> goes from <math>10\implies 97</math>
 +
 +
Hence, there are <math>\frac{97-10}{3}+1=30</math> distinct four digit numbers.
 +
 +
=== Solution 5 (Even Faster than Extremely Fast) ===
 +
 +
Following the form <math>xy23</math> in Solution 4, notice that <math>x+y \equiv 1 \pmod 3</math> to satisfy our condition. Choose a value of <math>x</math> from 1 to 9. For <math>x=1, 4, 7</math>, there are exactly 4 values of <math>y: 0, 3, 6, 9</math>. For the remaining 6 digits, there are 3 choices for y. So our answer is <math>(3)(4)+(6)(3)=30</math>.
 +
 +
=== Solution 6 (Even Faster than Even Faster than Extremely Fast)===
 +
There are <math>9 \cdot 10 = 90</math> possible values for the first two digits. <math>\frac{1}{3}</math> of them yield a multiple of <math>3</math>, so the answer is <math>\frac{90}{3} = \boxed{\textbf{(B)}\ 30}</math>
 +
 +
(In more detail: There are 90 possible values for the first two digits. All numbers can be written as 0, 1, or 2 mod(3). 2+3= 5 = -1 mod(3), so the first two digits need to add to 1 mod(3) for all the digits to equal 0 mod(3) (a multiple of 3). Out of the 3 ways to pick 2 numbers in mod(3) (0+1, 0+2, and 1+2), only <math>\frac{1}{3}</math> of the ways (only 0+1) equals 1 mod(3). Thus, the answer is <math>\frac{90}{3} = \boxed{\textbf{(B)}\ 30}</math>.
 +
 +
=== Solution 7 (Easy to understand) ===
 +
Denote the four digit number by <math>ab23_{10}</math>. Then it is well known the sum of the digits of an integer <math>N</math> determine whether or not they are divisible by <math>3</math>. Thus we want <math>a + b + 2 + 3 \equiv 0 \pmod 3</math>.
 +
 +
<math>\underline{a = 1}: \implies</math> <math>b \equiv 0 \pmod 3 \implies b = 0, 3, 6, 9</math>.
 +
 +
<math>\underline{a = 2}: \implies</math> <math>b \equiv 2 \pmod 3 \implies b = 2, 5, 8</math>.
 +
 +
<math>\underline{a = 3}: \implies</math> <math>b \equiv 1 \pmod 3 \implies b = 1, 4, 7</math>.
 +
 +
 +
Now we have that when <math>a = 4</math> this is the same case as <math>a = 1</math> as <math>4 \equiv 1 \pmod 3</math>. Hence if we count the above number of solutions and multiply by <math>3</math> (as <math>1 \leq a \leq 9</math>), we are home free. There are <math>4 + 3 + 3 = 10</math> solutions. Multiplying this by <math>3</math> yields <math>\boxed{30}</math>. <math>\blacksquare</math>
 +
 +
=== Solution 8 (Very very inefficient and slow) ===
 +
Don't do this on a test unless you have lots of time left.
 +
 +
Pounding out all of the possible numbers and counting them, we get <math>\boxed{\textbf{(B)}\ 30}.</math>
  
 
== See also ==
 
== See also ==
−
{{AMC10 box|year=2003|num-b=24|after=Last problem|ab=A}}
+
{{AMC10 box|year=2003|num-b=24|after=Last problem|ab=B}}
 +
 
 +
 
  
−
[[Category:Counting and Probability]]
+
{{MAA Notice}}

Latest revision as of 14:56, 17 August 2024

Problem

How many distinct four-digit numbers are divisible by $3$ and have $23$ as their last two digits?

$\textbf{(A) } 27 \qquad\textbf{(B) } 30 \qquad\textbf{(C) } 33 \qquad\textbf{(D) } 81 \qquad\textbf{(E) } 90$

Solution

Solution 1 (Slow)

To test if a number is divisible by three, you add up the digits of the number. If the sum is divisible by three, then the original number is a multiple of three. If the sum is too large, you can repeat the process until you can tell whether it is a multiple of three. This is the basis for the solution. Since the last two digits are $23$, the sum of the digits is $2+3 = 5$ (therefore it is not divisible by three). However certain numbers can be added to make the sum of the digits a multiple of three.

$5+1 = 6$,

$5+4 = 9$, and so on.

However since the largest four-digit number ending with $23$ is $9923$, the maximum sum is

$5+18 = 23$.

Using that process we can fairly quickly compile a list of the sum of the first two digits of the number.

\[\{1, 4, 7, 10, 13, 16\}\]

Now we find all the two-digit numbers that have any of the sums shown above. We can do this by listing all the two digit numbers $xy$ in separate cases.

\[I. x+y = 1, \{10\} = 1\] \[II. x+y = 4, \{13, 22, 31, 40\} = 4\] \[III. x+y = 7, \{16, 25, 34, 43, 52, 61, 70\} = 7\] \[IV. x+y = 10, \{19, 28, 37, 46, 55, 64, 73, 82, 91\} = 9\] \[V. x+y = 13, \{49, 58, 67, 76, 85, 94\} = 6\] \[VI. x+y = 16, \{79, 88, 97\} = 3\]

And finally, we add the number of elements in each set.

\[1+4+7+9+6+3 = \boxed{\textbf{(B)}\ 30}\]

Solution 2 (Medium)

A number divisible by $3$ has all its digits add to a multiple of $3.$ The last two digits are $2$ and $3$ and add up to $5 \equiv 2\ (\text{mod}\ 3).$ Therefore the first two digits must add up to $1\ (\text{mod}\ 3).$ $4$ digits (including $0$) are $0\ (\text{mod}\ 3),$ $3$ are $1\ (\text{mod}\ 3),$ and $3$ are $2\ (\text{mod}\ 3).$ The following combinations are equivalent to $1\ (\text{mod}\ 3)$:

\[0\ (\text{mod}\ 3)+1\ (\text{mod}\ 3) \equiv 1\ (\text{mod}\ 3)+0\ (\text{mod}\ 3) \equiv 2\ (\text{mod}\ 3) +2\ (\text{mod}\ 3)\]

Let the first term in each combination represent the thousands digit and the second term represent the hundreds digit. We can use this to find the total amount of four-digit numbers.

\[3\cdot3 + 3\cdot4 + 3\cdot3 = 9 + 12 + 9 = \boxed{\textbf{(B)}\ 30}\]

Solution 3 (Fast)

We have the following: $n \equiv 0 \pmod{3}$ and $n \equiv 23\pmod{100}$. Then $n = 3a = 100b+23$ for some integers $a$ and $b$. Taking mod 3 gives: $0 \equiv b+2 \pmod 3 \implies b\equiv 1\pmod 3$ so $b=3c+1$ for some integer $c$. But $N = 100b+23 = 100(3c+1)+23$ so $n = 300c+123$. Bounding this gives us: $999 < 300c+123 < 10000$ so $876 < 300c < 9877$. Dividing by $300$ gives $2.92 < c < 32.9222$ so $3\le c \le 32$. This gives $32-3+1 = \boxed{\textbf{(B)} \ 30 }$

Solution 4 (Extremely Fast)

The number is in the form $xy23$

Notice that the number is divisible by $3$ if the sum of the digits of $xy23$ is divisible by $3$

Our first number that is divisible by $3$ is $1023$, next is $1323$.. Notice $xy$ goes from $10\implies 97$

Hence, there are $\frac{97-10}{3}+1=30$ distinct four digit numbers.

Solution 5 (Even Faster than Extremely Fast)

Following the form $xy23$ in Solution 4, notice that $x+y \equiv 1 \pmod 3$ to satisfy our condition. Choose a value of $x$ from 1 to 9. For $x=1, 4, 7$, there are exactly 4 values of $y: 0, 3, 6, 9$. For the remaining 6 digits, there are 3 choices for y. So our answer is $(3)(4)+(6)(3)=30$.

Solution 6 (Even Faster than Even Faster than Extremely Fast)

There are $9 \cdot 10 = 90$ possible values for the first two digits. $\frac{1}{3}$ of them yield a multiple of $3$, so the answer is $\frac{90}{3} = \boxed{\textbf{(B)}\ 30}$

(In more detail: There are 90 possible values for the first two digits. All numbers can be written as 0, 1, or 2 mod(3). 2+3= 5 = -1 mod(3), so the first two digits need to add to 1 mod(3) for all the digits to equal 0 mod(3) (a multiple of 3). Out of the 3 ways to pick 2 numbers in mod(3) (0+1, 0+2, and 1+2), only $\frac{1}{3}$ of the ways (only 0+1) equals 1 mod(3). Thus, the answer is $\frac{90}{3} = \boxed{\textbf{(B)}\ 30}$.

Solution 7 (Easy to understand)

Denote the four digit number by $ab23_{10}$. Then it is well known the sum of the digits of an integer $N$ determine whether or not they are divisible by $3$. Thus we want $a + b + 2 + 3 \equiv 0 \pmod 3$.

$\underline{a = 1}: \implies$ $b \equiv 0 \pmod 3 \implies b = 0, 3, 6, 9$.

$\underline{a = 2}: \implies$ $b \equiv 2 \pmod 3 \implies b = 2, 5, 8$.

$\underline{a = 3}: \implies$ $b \equiv 1 \pmod 3 \implies b = 1, 4, 7$.


Now we have that when $a = 4$ this is the same case as $a = 1$ as $4 \equiv 1 \pmod 3$. Hence if we count the above number of solutions and multiply by $3$ (as $1 \leq a \leq 9$), we are home free. There are $4 + 3 + 3 = 10$ solutions. Multiplying this by $3$ yields $\boxed{30}$. $\blacksquare$

Solution 8 (Very very inefficient and slow)

Don't do this on a test unless you have lots of time left.

Pounding out all of the possible numbers and counting them, we get $\boxed{\textbf{(B)}\ 30}.$

See also

2003 AMC 10B (Problems • Answer Key • Resources)
Preceded by
Problem 24 		Followed by
Last problem
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 10 Problems and Solutions


The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2003_AMC_10B_Problems/Problem_25&oldid=225213"