Difference between revisions of "2021 AMC 10B Problems/Problem 16"

m (Solution 4 (Casework on Deleting the Digits of 12345))
m (Solution 4 (Casework on Deleting the Digits of 12345))
(2 intermediate revisions by 2 users not shown)
Line 7: Line 7:
 
==Solution 1==
 
==Solution 1==
 
The divisibility rule of <math>15</math> is that the number must be congruent to <math>0</math> mod <math>3</math> and congruent to <math>0</math> mod <math>5</math>. Being divisible by <math>5</math> means that it must end with a <math>5</math> or a <math>0</math>. We can rule out the case when the number ends with a <math>0</math> immediately because the only integer that is uphill and ends with a <math>0</math> is <math>0</math> which is not positive. So now we know that the number ends with a <math>5</math>. 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 <math>3</math>. These numbers are <math>15, 45, 135, 345, 1245, 12345</math> which are <math>6</math> numbers C.
 
The divisibility rule of <math>15</math> is that the number must be congruent to <math>0</math> mod <math>3</math> and congruent to <math>0</math> mod <math>5</math>. Being divisible by <math>5</math> means that it must end with a <math>5</math> or a <math>0</math>. We can rule out the case when the number ends with a <math>0</math> immediately because the only integer that is uphill and ends with a <math>0</math> is <math>0</math> which is not positive. So now we know that the number ends with a <math>5</math>. 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 <math>3</math>. These numbers are <math>15, 45, 135, 345, 1245, 12345</math> which are <math>6</math> numbers C.
 +
 +
~ilikemath40
  
 
==Solution 2==
 
==Solution 2==
Line 57: Line 59:
 
* It is divisible by <math>15</math> if and only if it is divisible by both <math>3</math> and <math>5.</math>
 
* It is divisible by <math>15</math> if and only if it is divisible by both <math>3</math> and <math>5.</math>
  
Since the desired positive integers are uphill, their units digits must be <math>5</math>s. We start with the largest such uphill integer (<math>12345,</math> by inspection), then perform casework on deleting its digits. <u>Clearly, we cannot delete the digit 5, as that is the only way to satisfy the divisibility rule of 5.</u> Now, we focus on the divisibility rule of <math>3.</math>
+
Since the desired positive integers are uphill, their units digits must be <math>5</math>s. We start with the largest such uphill integer (<math>12345,</math> by inspection), then perform casework on deleting its digits. <i><b>Clearly, we cannot delete the digit <math>\boldsymbol{\mathit{5,}}</math> as that is the only way to satisfy the divisibility rule of <math>\boldsymbol{\mathit{5.}}</math></b></i> Now, we focus on the divisibility rule of <math>3.</math>
  
 
Note that the sum of the deleted digits must be divisible by <math>3,</math> so the difference between <math>1+2+3+4+5=15</math> and this sum is also divisible by <math>3</math> (Quick Proof: Suppose the sum of the deleted digits is <math>3k.</math> It follows that <math>15-3k=3(5-k)</math> must be divisible by <math>3.</math>).  
 
Note that the sum of the deleted digits must be divisible by <math>3,</math> so the difference between <math>1+2+3+4+5=15</math> and this sum is also divisible by <math>3</math> (Quick Proof: Suppose the sum of the deleted digits is <math>3k.</math> It follows that <math>15-3k=3(5-k)</math> must be divisible by <math>3.</math>).  

Revision as of 11:04, 7 April 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.

~ilikemath40

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 (Casework on Deleting the Digits of 12345)

For every positive integer:

  • It is divisible by $3$ if and only if its digit-sum is divisible by $3.$
  • It is divisible by $5$ if and only if its units digit is $0$ or $5.$
  • It is divisible by $15$ if and only if it is divisible by both $3$ and $5.$

Since the desired positive integers are uphill, their units digits must be $5$s. We start with the largest such uphill integer ($12345,$ by inspection), then perform casework on deleting its digits. Clearly, we cannot delete the digit $\boldsymbol{\mathit{5,}}$ as that is the only way to satisfy the divisibility rule of $\boldsymbol{\mathit{5.}}$ Now, we focus on the divisibility rule of $3.$

Note that the sum of the deleted digits must be divisible by $3,$ so the difference between $1+2+3+4+5=15$ and this sum is also divisible by $3$ (Quick Proof: Suppose the sum of the deleted digits is $3k.$ It follows that $15-3k=3(5-k)$ must be divisible by $3.$).

Two solutions follow from here:

Solution 4.1 (Casework on the Number of Digits Deleted)

Case (1): Delete exactly $\boldsymbol{0}$ digits. ($\boldsymbol{5}$-digit uphill integers)

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

Case (2): Delete exactly $\boldsymbol{1}$ digit. ($\boldsymbol{4}$-digit uphill integers)

We can only delete the digit $3.$ So, there is $1$ uphill integer in this case: $1245.$

Case (3): Delete exactly $\boldsymbol{2}$ digits. ($\boldsymbol{3}$-digit uphill integers)

We can only delete the digits that sum to either $3$ or $6.$ So, there are $2$ uphill integers in this case: $345,135.$

Case (4): Delete exactly $\boldsymbol{3}$ digits. ($\boldsymbol{2}$-digit uphill integers)

We can only delete the digits that sum to either $6$ or $9.$ So, there are $2$ uphill integers in this case: $45,15.$

Total

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

~MRENTHUSIASM

Solution 4.2 (Casework on the Sum of Digits Deleted)

Case (1): The deleted digits' sum is $\boldsymbol{0.}$ (The remaining digits' sum is $\boldsymbol{15.}$)

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

Case (2): The deleted digits' sum is $\boldsymbol{3.}$ (The remaining digits' sum is $\boldsymbol{12.}$)

Note that $3=1+2.$ So, there are $2$ uphill integers in this case: $1245,345.$

Case (3): The deleted digits' sum is $\boldsymbol{6.}$ (The remaining digits' sum is $\boldsymbol{9.}$)

Note that $6=2+4=1+2+3.$ So, there are $2$ uphill integers in this case: $135,45.$

Case (4): The deleted digits' sum is $\boldsymbol{9.}$ (The remaining digits' sum is $\boldsymbol{6.}$)

Note that $9=2+3+4.$ So, there is $1$ uphill integer in this case: $15.$

Total

Together, our answer is $1+2+2+1=\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 (ProblemsAnswer KeyResources)
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