2021 AMC 10B Problems/Problem 16
Contents
Problem
Call a positive integer an uphill integer if every digit is strictly greater than the previous digit. For example, 
and 
are all uphill integers, but 
and 
are not. How many uphill integers are divisible by 
?
Solution 1
The divisibility rule of is that the number must be congruent to 
mod 
and congruent to mod . Being divisible by means that it must end with a or a . We can rule out the case when the number ends with a immediately because the only integer that is uphill and ends with a is which is not positive. So now we know that the number ends with a . 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 . These numbers are 
which are 
numbers C.
Solution 2
First, note how the number must end in either or in order to satisfying being divisible by . However, the number can't end in because it's not strictly greater than the previous digits. Thus, our number must end in . We do casework on the number of digits. 
Case 1 = 
digit. No numbers work, so
Case 2 = 
digits. We have the numbers 
and 
, but isn't an uphill number, so numbers.
Case 3 = digits. We have the numbers 
. So numbers.
Case 4 = 
digits. We have the numbers 
and 
, but only 
satisfies this condition, so number.
Case 5= digits. We have only 
, so number.
Adding these up, we have 
. 
~JustinLee2017
Solution 3
Like solution 2, we can proceed by using casework. A number is divisible by if is divisible by and 
In this case, the units digit must be 
otherwise no number can be formed.
Case 1: sum of digits = 6
There is only one number, 
Case 2: sum of digits = 9
There are two numbers: 
and 
Case 3: sum of digits = 12
There are two numbers: 
and 
Case 4: sum of digits = 15
There is only one number, 
We can see that we have exhausted all cases, because in order to have a larger sum of digits, then a number greater than needs to be used, breaking the conditions of the problem. The answer is 
~coolmath34
Solution 4 (Casework on Deleting the Digits of 12345)
For every positive integer:
It is divisible by if and only if its digit-sum is divisible by 
It is divisible by if and only if its units digit is or
It is divisible by if and only if it is divisible by both and
Since the desired positive integers are uphill, their units digits must be s. We start with 
the largest uphill integer by inspection, 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
Note that the sum of the deleted digits must be a multiple of 
so that the difference between 
and this sum is also divisible by (Quick Proof: Suppose the sum of the deleted digits is 
It follows that 
is also divisible by ). Two solutions follow from here:
Solution 4.1 (Casework on the Number of Digits Deleted)
Case (1): Delete exactly 
digits. (
-digit uphill integers)
There is uphill integer in this case:
Case (2): Delete exactly 
digit. (
-digit uphill integers)
We can only delete the digit So, there is uphill integer in this case:
Case (3): Delete exactly 
digits. (
-digit uphill integers)
We can only delete the digits that sum to either or 
So, there are uphill integers in this case: 
Case (4): Delete exactly digits. (-digit uphill integers)
We can only delete the digits that sum to either or 
So, there are uphill integers in this case: 
Case (5): Delete exactly digits. (-digit uphill integers)
As discussed above, we must keep the digit However, since is not divisible by this case is impossible.
Total
Together, our answer is 
~MRENTHUSIASM
Solution 4.2 (Casework on the Sum of Digits Deleted)
Case (1): The deleted digits' sum is 
(The remaining digits' sum is 
)
There is uphill integer in this case:
Case (2): The deleted digits' sum is 
(The remaining digits' sum is 
)
Note that 
So, there are uphill integers in this case: 
Case (3): The deleted digits' sum is 
(The remaining digits' sum is 
)
Note that 
So, there are uphill integers in this case: 
Case (4): The deleted digits' sum is (The remaining digits' sum is )
Note that 
So, there is uphill integer in this case:
Total
Together, our answer is 
~MRENTHUSIASM
Video Solution by OmegaLearn (Using Divisibility Rules and Casework)
~ pi_is_3.14
Video Solution by TheBeautyofMath
~IceMatrix
Video Solution by Interstigation
~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. 
