2023 AMC 12B Problems/Problem 16
Contents
[hide]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
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, www.professorchenedu.com
Solution 2
Arrange the positive integers into rows of , 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, is possible
and so is everything below
.
Column 2 - cross out
Column 3 - cross out
Column 4 - cross out
Column 5 - cross out
Column 6 - cross all out.
The maximum number that remains is .
Answer is
.
(sorry for the bad formatting - feel free to edit)
~JN, ab_godder
Solution 3 (Modulo 6)
Let the number of cent coins be
, the number of
cent coins be
, and the number of
cent coins be
. We get the Diophantine equation
and we wish to find the largest possible value of
Construct the following table of
,
, and
There are only possible residues for
, they are:
,
,
,
,
, and
.
We can obtain any value that is
because we have
cent coins.
We can obtain values that equal
by using one
cent coin, one
cent coin, and as many
cent coins needed. The smallest value that equals
we can obtain is
. Therefore, the largest value that equals
we cannot obtain is
![]()
We can obtain values that equal
by using two
cent coins, and as many
cent coins as needed. The smallest value that equals
we can obtain is
. Therefore, the largest value that equals
we cannot obtain is
![]()
We can obtain values that equal
by using one
cent coin, and as many
cent coins as needed. The smallest value that equals
we can obtain is
. Therefore, the largest value that equals
we cannot obtain is
![]()
We can obtain values that equal
by using one
cent coin, and as many
cent coins as needed. The smallest value that equals
we can obtain is
. Therefore, the largest value that equals
we cannot obtain is
![]()
We can obtain values that equal
by using two
cent coins, one
cent coin, and as many
cent coins as needed. The smallest value that equals
we can obtain is
. Therefore, the largest value that equals
we cannot obtain is
![]()
Hence, the largest value in cents we cannot obtain using ,
, and
cent coins is
,
.
Solution 4
We claim that the largest number that cannot be obtained using ,
, and
cent coins is
.
Let's first focus on the combination of ,
. As both of them are even numbers, we cannot obtain any odd numbers from these two but requires
to sum up to an odd number. Notice that by Chicken McNugget Theorem, the largest even number cannot be obtained by
,
is
. Add this with
, we can easily verify that
cannot be obtained by
,
, and
as it needs at least one odd number, with the remaining part cannot be represented by
and
.
Let's show that any number greater than can be obtained. First, any even numbers greater than
can be obtained by
and
by the Chicken McNugget Theorem. Next, any odd number greater than
can be obtained by adding one
with some
s and
s, which is also shown by the Chicken McNugget Theorem. This completes the proof. So the answer is
~ZZZIIIVVV
Solution 4 (apply Chicken McNugget Theorem twice)
First considering the two terms
Again applying the two variable formula for the terms in brackets we see that
so the given expression 6a+10b+15c produces all numbers from 30 and 29 is the largest number that could not be produced,so the answer is
- Note: Chicken McNugget Theorem: any positive integer N= (a-1)(b-1)+t ( a,b co-prime, t>=0) can always be represented as N = aP+ bQ ( p,q are non-negative integer)
Video Solution 1 by OmegaLearn
Video Solution 2
~Steven Chen, www.professorchenedu.com
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.