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)
(6 intermediate revisions by the same user not shown)
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 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>
  
<b>Case (5): Remove <math>\boldsymbol{4}</math> digits.</b>
+
Note that the sum of the deleted digits must be a multiple of <math>3,</math> so that the difference between <math>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> is also divisible by <math>3.</math>). Two solutions follow from here:
 +
 
 +
===Solution 4.1 (Casework on the Number of Digits Deleted)===
 +
<b>Case (1): Delete exactly <math>\boldsymbol{0}</math> digits. (<math>\boldsymbol{5}</math>-digit uphill integers)</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): Delete exactly <math>\boldsymbol{1}</math> digit. (<math>\boldsymbol{4}</math>-digit uphill integers)</b>
 +
 
 +
We can only delete the digit <math>3.</math>
 +
 
 +
There is <math>1</math> uphill integer in this case: <math>1245.</math>
 +
 
 +
<b>Case (3): Delete exactly <math>\boldsymbol{2}</math> digits. (<math>\boldsymbol{3}</math>-digit uphill integers)</b>
 +
 
 +
We can only delete the digits that sum to either <math>3</math> or <math>6.</math>
 +
 
 +
There are <math>2</math> uphill integers in this case: <math>345,135.</math>
 +
 
 +
<b>Case (4): Delete exactly <math>\boldsymbol{3}</math> digits. (<math>\boldsymbol{2}</math>-digit uphill integers)</b>
 +
 
 +
We can only delete the digits that sum to either <math>6</math> or <math>9.</math>
 +
 
 +
There are <math>2</math> uphill integers in this case: <math>45,15.</math>
 +
 
 +
<b>Case (5): Delete exactly <math>\boldsymbol{4}</math> digits. (<math>\boldsymbol{1}</math>-digit uphill integers)</b>
 +
 
 +
As discussed above, we must keep the digit <math>5.</math> However, 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
 +
 
 +
===Solution 4.2 (Casework on the Sum of Digits Deleted)===
 +
<b>Case (1): The deleted digits' sum is <math>\boldsymbol{0.}</math> (The remaining digits' sum is <math>\boldsymbol{15.}</math>)</b>
 +
 
 +
Note that .... So, there are ... uphill integers in this case: ...
 +
 
 +
<b>Case (2): The deleted digits' sum is <math>\boldsymbol{3.}</math> (The remaining digits' sum is <math>\boldsymbol{12.}</math>)</b>
 +
 
 +
Note that <math>3=1+2.</math> So, there are <math>2</math> uphill integers in this case: <math>1245,345.</math>
 +
 
 +
<b>Case (3): The deleted digits' sum is <math>\boldsymbol{6.}</math> (The remaining digits' sum is <math>\boldsymbol{9.}</math>)</b>
 +
 
 +
Note that <math>6=2+4=1+2+3.</math> So, there are <math>2</math> uphill integers in this case: <math>135,45.</math>
 +
 
 +
<b>Case (4): The deleted digits' sum is <math>\boldsymbol{9.}</math> (The remaining digits' sum is <math>\boldsymbol{6.}</math>)</b>
 +
 
 +
Note that <math>9=2+3+4.</math> So, there is <math>1</math> uphill integer in this case: <math>15.</math>
  
 
~MRENTHUSIASM
 
~MRENTHUSIASM

Revision as of 00:27, 6 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 deleting its digits. Clearly, we cannot delete the digit 5, as that is the only way to satisfy the divisibility rule of 5. Now, we focus on the divisibility rule of $3.$

Note that the sum of the deleted digits must be a multiple of $3,$ so that the difference between $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)$ is also 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)

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): Delete exactly $\boldsymbol{1}$ digit. ($\boldsymbol{4}$-digit uphill integers)

We can only delete the digit $3.$

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.$

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.$

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

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

As discussed above, we must keep the digit $5.$ However, 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

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.}$)

Note that .... So, there are ... uphill integers in this case: ...

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.$

~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