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"

m (→‎Solution 4 (Casework on Deleting the Digits of 12345))
m (→‎Solution 4)
 
(12 intermediate revisions by 4 users not shown)
Line 6: Line 6:
  
 
==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>, or <math>\boxed{\textbf{(C)} ~6}</math> numbers.
 +
 
 +
~ilikemath40
  
 
==Solution 2==
 
==Solution 2==
−
First, note how the number must end in either <math>5</math> or <math>0</math> in order to satisfying being divisible by <math>15</math>. However, the number can't end in <math>0</math> because it's not strictly greater than the previous digits. Thus, our number must end in <math>5</math>. We do casework on the number of digits. <math>\newline</math>
+
First, note how the number must end in either <math>5</math> or <math>0</math> in order to satisfying being divisible by <math>15</math>. However, the number can't end in <math>0</math> because it's not strictly greater than the previous digits. Thus, our number must end in <math>5</math>. We do casework on the number of digits.
  
−
'''Case 1''' = <math>1</math> digit. No numbers work, so <math>0</math> <math>\newline</math>
+
<b>Case 1:</b> <math>1</math> digit. No numbers work, so <math>0</math> numbers.
  
−
'''Case 2''' = <math>2</math> digits. We have the numbers <math>15, 45,</math> and <math>75</math>, but <math>75</math> isn't an uphill number, so <math>2</math> numbers. <math>\newline</math>
+
<b>Case 2:</b> <math>2</math> digits. We have the numbers <math>15, 45,</math> and <math>75</math>, but <math>75</math> isn't an uphill number, so <math>2</math> numbers
  
−
'''Case 3''' = <math>3</math> digits. We have the numbers <math>135, 345</math>. So <math>2</math> numbers.   <math>\newline</math>
+
<b>Case 3:</b> <math>3</math> digits. We have the numbers <math>135, 345</math>, so <math>2</math> numbers.
  
−
'''Case 4''' = <math>4</math> digits. We have the numbers <math>1235, 1245</math> and <math>2345</math>, but only <math>1245</math> satisfies this condition, so <math>1</math> number. <math>\newline</math>
+
<b>Case 4:</b> <math>4</math> digits. We have the numbers <math>1235, 1245</math> and <math>2345</math>, but only <math>1245</math> satisfies this condition, so <math>1</math> number.
  
−
'''Case 5'''= <math>5</math> digits. We have only <math>12345</math>, so <math>1</math> number. <math>\newline</math>
+
<b>Case 5:</b> <math>5</math> digits. We have only <math>12345</math>, so <math>1</math> number.
  
−
Adding these up, we have <math>2+2+1+1 = 6</math>. <math>\boxed {C}</math>
+
Adding these up, we have <math>2+2+1+1=\boxed{\textbf{(C)} ~6}</math>.
  
 
~JustinLee2017
 
~JustinLee2017
Line 44: Line 46:
 
There is only one number, <math>12345.</math>
 
There is only one number, <math>12345.</math>
  
−
We can see that we have exhausted all cases, because in order to have a larger sum of digits, then a number greater than <math>5</math> needs to be used, breaking the conditions of the problem. The answer is <math>\textbf{(C)}.</math>
+
We can see that we have exhausted all cases, because in order to have a larger sum of digits, then a number greater than <math>5</math> needs to be used, breaking the conditions of the problem. The answer is <math>\boxed{\textbf{(C)} ~6}.</math>
  
 
~coolmath34
 
~coolmath34
  
−
==Solution 4 (Casework on Deleting the Digits of 12345)==
+
==Solution 4==
−
For every positive integer:
+
An integer is divisible by <math>15</math> if it is divisible by <math>3</math> and <math>5</math>. Divisibility by <math>5</math> means ending in <math>0</math> or <math>5</math>, but since no digit is less than <math>0</math>, the only uphill integer ending in <math>0</math> could be <math>0</math>, which is not positive. This means the integer must end in <math>5</math>.
−
 
 
−
* 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>
 
−
 
 
−
* 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>
 
−
 
 
−
Note that the sum of the deleted digits must be divisible by <math>3,</math> so that 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>).
 
−
 
 
−
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>
 
−
 
 
−
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> So, 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> So, 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> So, there are <math>2</math> uphill integers in this case: <math>45,15.</math>
 
−
 
 
−
<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>
 
−
 
 
−
There is <math>1</math> uphill integer in this case: <math>12345.</math>
 
−
 
 
−
<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>
+
All uphill integers ending in <math>5</math> are formed by picking any subset of the sequence <math>(1,2,3,4)</math> of digits (keeping their order), then appending a <math>5</math>. Divisibility by <math>3</math> means the sum of the digits is a multiple of <math>3</math>, so our choice of digits must add to <math>0</math> modulo <math>3</math>.
  
−
Note that <math>9=2+3+4.</math> So, there is <math>1</math> uphill integer in this case: <math>15.</math>
+
<math>5 \equiv -1 \pmod{3}</math>, so the other digits we pick must add to <math>1</math> modulo <math>3</math>. Since <math>(1,2,3,4) \equiv (1,-1,0,1) \pmod{3}</math>, we can pick either nothing, or one residue <math>1</math> (from <math>1</math> or <math>4</math>) and one residue <math>-1</math> (from <math>2</math>), and we can then optionally add a residue <math>0</math> (from <math>3</math>). This gives <math>(1+2\cdot1)\cdot2 = \boxed{\textbf{(C)}~6}</math> possibilities.
  
−
<b>Total</b>
+
~[[User:emerald_block|emerald_block]]
  
−
Together, our answer is <math>1+2+2+1=\boxed{\textbf{(C)} ~6}.</math>
+
==Video Solution (🚀Solved in 3 minutes and 2 seconds🚀) ==
 +
https://youtu.be/c54455_3Xcc
  
−
~MRENTHUSIASM
+
<i> Education, the Study of Everything </i>
  
 
== Video Solution by OmegaLearn (Using Divisibility Rules and Casework) ==
 
== Video Solution by OmegaLearn (Using Divisibility Rules and Casework) ==

Latest revision as of 18:07, 11 November 2023

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$, or $\boxed{\textbf{(C)} ~6}$ numbers.

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

Case 1: $1$ digit. No numbers work, so $0$ numbers.

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

Case 3: $3$ digits. We have the numbers $135, 345$, so $2$ numbers.

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

Case 5: $5$ digits. We have only $12345$, so $1$ number.

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

~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 $\boxed{\textbf{(C)} ~6}.$

~coolmath34

Solution 4

An integer is divisible by $15$ if it is divisible by $3$ and $5$. Divisibility by $5$ means ending in $0$ or $5$, but since no digit is less than $0$, the only uphill integer ending in $0$ could be $0$, which is not positive. This means the integer must end in $5$.

All uphill integers ending in $5$ are formed by picking any subset of the sequence $(1,2,3,4)$ of digits (keeping their order), then appending a $5$. Divisibility by $3$ means the sum of the digits is a multiple of $3$, so our choice of digits must add to $0$ modulo $3$.

$5 \equiv -1 \pmod{3}$, so the other digits we pick must add to $1$ modulo $3$. Since $(1,2,3,4) \equiv (1,-1,0,1) \pmod{3}$, we can pick either nothing, or one residue $1$ (from $1$ or $4$) and one residue $-1$ (from $2$), and we can then optionally add a residue $0$ (from $3$). This gives $(1+2\cdot1)\cdot2 = \boxed{\textbf{(C)}~6}$ possibilities.

~emerald_block

Video Solution (🚀Solved in 3 minutes and 2 seconds🚀)

https://youtu.be/c54455_3Xcc

Education, the Study of Everything

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=202443"