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"

(→‎Solution)
(new solution)
(42 intermediate revisions by 10 users not shown)
Line 1: Line 1:
−
==Problem==Call a positive integer an uphill integer if every digit is strictly greater than the previous digit. For example, <math>1357, 89,</math> and <math>5</math> are all uphill integers, but <math>32, 1240,</math> and <math>466</math> are not. How many uphill integers are divisible by <math>15</math>?
+
==Problem==
 +
 
 +
Call a positive integer an uphill integer if every digit is strictly greater than the previous digit. For example, <math>1357, 89,</math> and <math>5</math> are all uphill integers, but <math>32, 1240,</math> and <math>466</math> are not. How many uphill integers are divisible by <math>15</math>?
  
 
<math>\textbf{(A)} ~4 \qquad\textbf{(B)} ~5 \qquad\textbf{(C)} ~6 \qquad\textbf{(D)} ~7 \qquad\textbf{(E)} ~8</math>
 
<math>\textbf{(A)} ~4 \qquad\textbf{(B)} ~5 \qquad\textbf{(C)} ~6 \qquad\textbf{(D)} ~7 \qquad\textbf{(E)} ~8</math>
−
==Solution==
 
  
−
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 <math>15, 45, 135, 345, 1245, 12345</math> which is 6 numbers C.
+
==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>, or <math>\boxed{\textbf{(C)} ~6}</math> numbers.
 +
 
 +
~ilikemath40
 +
 
 +
==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.
 +
 
 +
<b>Case 1:</b> <math>1</math> digit. No numbers work, so <math>0</math> numbers.
 +
 
 +
<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
 +
 
 +
<b>Case 3:</b> <math>3</math> digits. We have the numbers <math>135, 345</math>, so <math>2</math> numbers.
 +
 
 +
<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.
 +
 
 +
<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=\boxed{\textbf{(C)} ~6}</math>.
 +
 
 +
~JustinLee2017
 +
 
 +
==Solution 3==
 +
Like solution 2, we can proceed by using casework. A number is divisible by <math>15</math> if is divisible by <math>3</math> and <math>5.</math> In this case, the units digit must be <math>5,</math> otherwise no number can be formed.
 +
 
 +
'''Case 1: sum of digits = 6'''
 +
 
 +
There is only one number, <math>15.</math>
 +
 
 +
'''Case 2: sum of digits = 9'''
 +
 
 +
There are two numbers: <math>45</math> and <math>135.</math>
 +
 
 +
'''Case 3: sum of digits = 12'''
 +
 
 +
There are two numbers: <math>345</math> and <math>1245.</math>
 +
 
 +
'''Case 4: sum of digits = 15'''
 +
 
 +
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>\boxed{\textbf{(C)} ~6}.</math>
 +
 
 +
~coolmath34
 +
 
 +
==Solution 4==
 +
An integer is divisible by <math>15</math> iff 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>.
 +
 
 +
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>.
 +
 
 +
<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.
 +
 
 +
~[[User:emerald_block|emerald_block]]
 +
 
 +
== 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==
 +
{{AMC10 box|year=2021|ab=B|num-b=15|num-a=17}}
 +
{{MAA Notice}}

Revision as of 16:43, 7 November 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$, 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$ iff 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 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=164825"