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 "2021 AMC 10B Problems/Problem 16"

(Removed the extra lines and added in Solution 4. I will come back later.)
(→‎Solution 4: Solution completed.)
Line 49: Line 49:
  
 
==Solution 4==
 
==Solution 4==
−
For every positive integer, it is divisible by <math>3</math> if and only if its digit-sum is divisible by <math>3;</math> it is divisible by <math>5</math> if and only if its units digit is <math>0</math> or <math>5.</math> Since the desired positive integers are going <b>uphill</b>, their units digits must be <math>5</math>s.
+
For every positive integer:
  
−
<b>Case (1): Remove <math>\boldsymbol{0}</math> digits.</b>
+
<math>\quad\bullet</math> It is divisible by <math>3</math> if and only if its digit-sum is divisible by <math>3.</math>
  
−
<b>Case (2): Remove <math>\boldsymbol{1}</math> digit.</b>
+
<math>\quad\bullet</math> It is divisible by <math>5</math> if and only if its units digit is <math>0</math> or <math>5.</math>  
  
−
<b>Case (3): Remove <math>\boldsymbol{2}</math> digits.</b>
+
<math>\quad\bullet</math> It is divisible by <math>15</math> if and only if it is divisible by both <math>3</math> and <math>5.</math>
  
−
<b>Case (4): Remove <math>\boldsymbol{3}</math> digits.</b>
+
Since the desired positive integers are going uphill, their units digits must be <math>5</math>s. We start with <math>12345,</math> the largest of such positive integers, and perform casework on removing the number of its digits. Clearly, we cannot remove the digit <math>5,</math> as that is the only way to satisfy the divisibility of <math>5.</math> Now, we focus on the divisibility of <math>3.</math>
  
−
<b>Case (5): Remove <math>\boldsymbol{4}</math> digits.</b>
+
<b>Case (1): Remove exactly <math>\boldsymbol{0}</math> digits. (<math>\boldsymbol{5}</math>-digit numbers)</b>
 +
 
 +
The number <math>12345</math> has a digit-sum of <math>15.</math> So, it is divisible by <math>3.</math>
 +
 
 +
There is <math>1</math> uphill integer in this case: <math>12345.</math>
 +
 
 +
<b>Case (2): Remove exactly <math>\boldsymbol{1}</math> digit. (<math>\boldsymbol{4}</math>-digit numbers)</b>
 +
 
 +
We can only remove the digit <math>3.</math>
 +
 
 +
There is <math>1</math> uphill integer in this case: <math>1245.</math>
 +
 
 +
<b>Case (3): Remove exactly <math>\boldsymbol{2}</math> digits. (<math>\boldsymbol{3}</math>-digit numbers)</b>
 +
 
 +
We can only remove the digits that sum to a multiple of <math>3.</math> This sum can only be <math>3</math> or <math>6</math> here.
 +
 
 +
There are <math>2</math> uphill integers in this case: <math>345,135.</math>
 +
 
 +
<b>Case (4): Remove exactly <math>\boldsymbol{3}</math> digits. (<math>\boldsymbol{2}</math>-digit numbers)</b>
 +
 
 +
We can only remove the digits that sum to a multiple of <math>3.</math> This sum can only be <math>6</math> or <math>9</math> here.
 +
 
 +
There are <math>2</math> uphill integers in this case: <math>45,15.</math>
 +
 
 +
<b>Case (5): Remove exactly <math>\boldsymbol{4}</math> digits. (<math>\boldsymbol{1}</math>-digit numbers)</b>
 +
 
 +
As discussed above, we must keep the digit <math>5.</math> Since <math>5</math> is not divisible by <math>3,</math> this case is impossible.
 +
 
 +
<b>Total</b>
 +
 
 +
Together, our answer is <math>1+1+2+2=\boxed{\textbf{(C)} ~6}.</math>
  
 
~MRENTHUSIASM
 
~MRENTHUSIASM

Revision as of 15:05, 5 March 2021

Problem

Call a positive integer an uphill integer if every digit is strictly greater than the previous digit. For example, $1357, 89,$ and $5$ are all uphill integers, but $32, 1240,$ and $466$ are not. How many uphill integers are divisible by $15$?

$\textbf{(A)} ~4 \qquad\textbf{(B)} ~5 \qquad\textbf{(C)} ~6 \qquad\textbf{(D)} ~7 \qquad\textbf{(E)} ~8$

Solution 1

The divisibility rule of $15$ is that the number must be congruent to $0$ mod $3$ and congruent to $0$ mod $5$. Being divisible by $5$ means that it must end with a $5$ or a $0$. We can rule out the case when the number ends with a $0$ immediately because the only integer that is uphill and ends with a $0$ is $0$ which is not positive. So now we know that the number ends with a $5$. Looking at the answer choices, the answer choices are all pretty small, so we can generate all of the numbers that are uphill and are divisible by $3$. These numbers are $15, 45, 135, 345, 1245, 12345$ which are $6$ numbers C.

Solution 2

First, note how the number must end in either $5$ or $0$ in order to satisfying being divisible by $15$. However, the number can't end in $0$ because it's not strictly greater than the previous digits. Thus, our number must end in $5$. We do casework on the number of digits. $\newline$

Case 1 = $1$ digit. No numbers work, so $0$ $\newline$

Case 2 = $2$ digits. We have the numbers $15, 45,$ and $75$, but $75$ isn't an uphill number, so $2$ numbers. $\newline$

Case 3 = $3$ digits. We have the numbers $135, 345$. So $2$ numbers. $\newline$

Case 4 = $4$ digits. We have the numbers $1235, 1245$ and $2345$, but only $1245$ satisfies this condition, so $1$ number. $\newline$

Case 5= $5$ digits. We have only $12345$, so $1$ number. $\newline$

Adding these up, we have $2+2+1+1 = 6$. $\boxed {C}$

~JustinLee2017

Solution 3

Like solution 2, we can proceed by using casework. A number is divisible by $15$ if is divisible by $3$ and $5.$ In this case, the units digit must be $5,$ otherwise no number can be formed.

Case 1: sum of digits = 6

There is only one number, $15.$

Case 2: sum of digits = 9

There are two numbers: $45$ and $135.$

Case 3: sum of digits = 12

There are two numbers: $345$ and $1245.$

Case 4: sum of digits = 15

There is only one number, $12345.$

We can see that we have exhausted all cases, because in order to have a larger sum of digits, then a number greater than $5$ needs to be used, breaking the conditions of the problem. The answer is $\textbf{(C)}.$

~coolmath34

Solution 4

For every positive integer:

$\quad\bullet$ It is divisible by $3$ if and only if its digit-sum is divisible by $3.$

$\quad\bullet$ It is divisible by $5$ if and only if its units digit is $0$ or $5.$

$\quad\bullet$ It is divisible by $15$ if and only if it is divisible by both $3$ and $5.$

Since the desired positive integers are going uphill, their units digits must be $5$s. We start with $12345,$ the largest of such positive integers, and perform casework on removing the number of its digits. Clearly, we cannot remove the digit $5,$ as that is the only way to satisfy the divisibility of $5.$ Now, we focus on the divisibility of $3.$

Case (1): Remove exactly $\boldsymbol{0}$ digits. ($\boldsymbol{5}$-digit numbers)

The number $12345$ has a digit-sum of $15.$ So, it is divisible by $3.$

There is $1$ uphill integer in this case: $12345.$

Case (2): Remove exactly $\boldsymbol{1}$ digit. ($\boldsymbol{4}$-digit numbers)

We can only remove the digit $3.$

There is $1$ uphill integer in this case: $1245.$

Case (3): Remove exactly $\boldsymbol{2}$ digits. ($\boldsymbol{3}$-digit numbers)

We can only remove the digits that sum to a multiple of $3.$ This sum can only be $3$ or $6$ here.

There are $2$ uphill integers in this case: $345,135.$

Case (4): Remove exactly $\boldsymbol{3}$ digits. ($\boldsymbol{2}$-digit numbers)

We can only remove the digits that sum to a multiple of $3.$ This sum can only be $6$ or $9$ here.

There are $2$ uphill integers in this case: $45,15.$

Case (5): Remove exactly $\boldsymbol{4}$ digits. ($\boldsymbol{1}$-digit numbers)

As discussed above, we must keep the digit $5.$ Since $5$ is not divisible by $3,$ this case is impossible.

Total

Together, our answer is $1+1+2+2=\boxed{\textbf{(C)} ~6}.$

~MRENTHUSIASM

Video Solution by OmegaLearn (Using Divisibility Rules and Casework)

https://youtu.be/n2FnKxFSW94

~ pi_is_3.14

Video Solution by TheBeautyofMath

https://youtu.be/FV9AnyERgJQ

~IceMatrix

Video Solution by Interstigation

https://youtu.be/9ZlJTVhtu_s

~Interstigation

See Also

2021 AMC 10B (Problems • Answer Key • Resources)
Preceded by
Problem 15 		Followed by
Problem 17
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=2021_AMC_10B_Problems/Problem_16&oldid=148630"