2015 AMC 10A Problem 13
Claudia has 12 coins, each of which is a 5-cent coin or a 10-cent coin. There are exactly 17 different values that can be obtained as combinations of one or more of her coins. How many 10-cent coins does Claudia have?
Show solution without answering
Key insight
Count in nickels, with a dime worth 2. With at least one nickel, every amount up to the total can be made, so the total is 17 nickels.
Solution
Measure all money in nickels, so a -cent coin is unit and a -cent coin is units.
1. Try one choice to see the pattern. Say Claudia has dimes and nickels. Her total is units ( cents).
2. Which amounts can she make? Here is how to make each one:
- unit: one nickel. units: one dime. units: a dime and a nickel. units: two dimes.
- Keep going: an even amount up to uses only dimes, and an odd amount up to uses dimes plus one nickel.
- Past units all dimes are used, and the extra nickels fill in .
So she can make every amount from to units: different values. That matches.
3. The same reasoning works for any number of dimes , as long as there is at least one nickel: every amount from unit up to the total can be made. The total is units, so she can make exactly values.
4. Set , so .
5. (With no nickels at all, the dimes make only values, so that case does not give .)
The answer is .
Why this works
With coins worth and units and at least one , there are no gaps: the 's build even amounts, a single makes the odd ones, and the rest of the 's reach the top. So "how many values" just means "how big is the total". Spotting that there are no gaps turns a counting problem into one short equation.
Alternative approach
Check nearby choices. With dimes and nickels the total is cents, giving : values. With dimes and nickels the total is cents: values. Only dimes gives .
Concise solution
A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.
Say Claudia has dimes and nickels. Measure money in nickels: a dime is worth units, so her total is units.
Claim: if she has at least one nickel, every amount from unit up to the total is obtainable. To make units, use dimes and the rest in nickels; the number of nickels needed is at most when , and at most when (because ). So the obtainable values are exactly , which is distinct values.
Setting gives . (If she had no nickels, only values would be possible, not .)
The answer is .
Review in the AoPS books
- Introduction to Counting & Probability, Chapter 1: Counting Is Arithmetic
- Introduction to Number Theory, Chapter 1: Integers: The Basics
- Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques
- Introduction to Algebra, Chapter 20: Special Functions (§20.3)
Similar problems
Problem © Mathematical Association of America (MAA), American Mathematics Competitions. Reproduced for non-commercial educational use. Solution and commentary are original to this site.