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 "2023 AMC 12B Problems/Problem 16"
(→‎Solution)
Line 38: Line 38:
 
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
 
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
  
 +
==Solution 2==
 +
Arrange the positive integers into rows of 6, like this:
 +
<cmath>
 +
\begin{align}
 +
01, 02, 03, 04, 05, 06 \\
 +
07, 08, 09, 10, 11, 12 \\
 +
13, 14, 15, 16, 17, 18 \\
 +
19, 20, 21, 22, 23, 24 \\
 +
25, 26, 27, 28, 29, 30 \\
 +
31, 32, 33, 34, 35, 36 \\
 +
...
 +
\end{align}
 +
</cmath>
 +
 +
Observe that if any number can be made from a combination of 6s, 10s, and 15s, 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.
 +
 +
~JN
  
 
==See Also==
 
==See Also==
 
{{AMC12 box|year=2023|ab=B|num-b=15|num-a=17}}
 
{{AMC12 box|year=2023|ab=B|num-b=15|num-a=17}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 20:42, 15 November 2023

Problem

In the state of Coinland, coins have values $6,10,$ and $15$ cents. Suppose $x$ 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 $x?$

$\textbf{(A) }8\qquad\textbf{(B) }10\qquad\textbf{(C) }7\qquad\textbf{(D) }11\qquad\textbf{(E) }9$

Solution

This problem asks to find largest $x$ that cannot be written as \[ 6 a + 10 b + 15 c = x, \hspace{1cm} (1) \] where $a, b, c \in \Bbb Z_+$.

Denote by $r \in \left\{ 0, 1 \right\}$ the remainder of $x$ divided by 2. Modulo 2 on Equation (1), we get By using modulus $m \in \left\{ 2, 3, 5 \right\}$ on the equation above, we get $c \equiv r \pmod{2}$.

Following from Chicken McNugget's theorem, we have that any number that is no less than $(3-1)(5-1) = 8$ can be expressed in the form of $3a + 5b$ with $a, b \in \Bbb Z_+$.

Therefore, all even numbers that are at least equal to $2 \cdot 8 + 15 \cdot 0 = 16$ can be written in the form of Equation (1) with $a, b, c \in \Bbb Z_+$. All odd numbers that are at least equal to $2 \cdot 8 + 15 \cdot 1 = 31$ can be written in the form of Equation (1) with $a, b, c \in \Bbb Z_+$.

The above two cases jointly imply that all numbers that are at least 30 can be written in the form of Equation (1) with $a, b, c \in \Bbb Z_+$.

Next, we need to prove that 29 cannot be written in the form of Equation (1) with $a, b, c \in \Bbb Z_+$.

Because 29 is odd, we must have $c \equiv 1 \pmod{2}$. Because $a, b, c \in \Bbb Z_+$, we must have $c = 1$. Plugging this into Equation (1), we get $3 a + 5 b = 7$. However, this equation does not have non-negative integer solutions.

All analysis above jointly imply that the largest $x$ that has no non-negative integer solution to Equation (1) is 29. Therefore, the answer is $2 + 9 = \boxed{\textbf{(D) 11}}$.

~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)

Solution 2

Arrange the positive integers into rows of 6, like this: \begin{align} 01, 02, 03, 04, 05, 06 \\ 07, 08, 09, 10, 11, 12 \\ 13, 14, 15, 16, 17, 18 \\ 19, 20, 21, 22, 23, 24 \\ 25, 26, 27, 28, 29, 30 \\ 31, 32, 33, 34, 35, 36 \\ ... \end{align}

Observe that if any number can be made from a combination of 6s, 10s, and 15s, 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.

~JN

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2023_AMC_12B_Problems/Problem_16&oldid=203690"