2023 AMC 12B Problems/Problem 16
Contents
Problem
In the state of Coinland, coins have values 
and 
cents. Suppose 
is the value in cents of the most expensive item in Coinland that cannot be purchased using these coins with exact change. What is the sum of the digits of 
Solution 1
This problem asks to find largest that cannot be written as
![\[ 6 a + 10 b + 15 c = x, \hspace{1cm} (1) \]](http://latex.artofproblemsolving.com/4/5/9/4599a23c5484a8b1490fa8d5b7849f3f2c7a44ef.png)
where 
.
Denote by 
the remainder of divided by 2.
Modulo 2 on Equation (1), we get
By using modulus 
on the equation above, we get
.
Following from Chicken McNugget's theorem, we have that any number that is no less than 
can be expressed in the form of 
with 
.
Therefore, all even numbers that are at least equal to 
can be written in the form of Equation (1) with .
All odd numbers that are at least equal to 
can be written in the form of Equation (1) with .
The above two cases jointly imply that all numbers that are at least 30 can be written in the form of Equation (1) with .
Next, we need to prove that 29 cannot be written in the form of Equation (1) with .
Because 29 is odd, we must have 
.
Because , we must have 
.
Plugging this into Equation (1), we get 
.
However, this equation does not have non-negative integer solutions.
All analysis above jointly imply that the largest that has no non-negative integer solution to Equation (1) is 29.
Therefore, the answer is 
.
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
Solution 2
Arrange the positive integers into rows of 6, like this:
Observe that if any number can be made from a combination of 
s, 
s, and s, then every number below it in the same column must also be possible to make, by simply adding 6s.
Thus, we will cross out any numbers that CAN be made as well as all numbers below it.
In column 1, 25 is possible (10+15) and so is everything below 25.
Column 2 - cross out 20 (10+10) and everything below it
Column 3 - cross out 15 and everything below it
Column 4 - cross out 10 and everything below it
Column 5 - cross out 35 (15+10+10) and everything below it
Column 6 - all numbers here are possible, so cross all out.
The maximum number that remains is 29. Answer is 2+9=11.
(sorry for the bad formatting - feel free to edit)
~JN
Solution 3 (mod 6)
![\[\begin{array}{c|ccc} & & & \\ number of coins & 6 & 10 & 15 \\ \hline & & & \\ 1 & 0 & 4 & 3\\ & & & \\ 2 & 0 & 2 & 0 \\ \end{array}\]](http://latex.artofproblemsolving.com/1/3/d/13d09879f7f0a296c623e401016d9a785f2cf061.png)
There are only possible residues for , they are: 
, 
, 
, 
, 
, and 
.
We can obtain any integer that is
cent coins.
We can obtain any integer that is We can obtain integers that equal
cent coin, one
cent coin, and as many
. Therefore, the largest integer that equals
We can obtain integers that equal 
. Therefore, the largest integer that equals 
We can obtain integers that equal
. Therefore, the largest integer that equals
We can obtain integers that equal 
. Therefore, the largest integer that equals 
We can obtain integers that equal
We can obtain integers that equal 
We can obtain integers that equal
We can obtain integers that equal 
We can obtain integers that equal
. Therefore, the largest integer that equals
We can obtain integers that equal 
. Therefore, the largest integer that equals 
Hence, the largest integer we cannot obtain is 
, .
Video Solution 1 by OmegaLearn
See Also
| 2023 AMC 12B (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 12 Problems and Solutions | |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 
