Branching Method ③ Paying Without Receiving Change
Paying exactly, or making sure that you do not receive change, is a common situation in daily life. This is a typical use of the branching method, with rules about the number of coins that can be used.
Branching Method in Daily Life
When the types and numbers of coins in your wallet are fixed, let us think of ways to pay exactly.
Example Problem
There are three 100-yen coins, four 50-yen coins, and five 10-yen coins in a wallet. How many ways are there to pay exactly 350 yen using these coins?
Solution: 100a + 50b + 10c = 350 (a ≦ 3, b ≦ 4, c ≦ 5)
Consider the cases in order, starting with the coins of the greatest value.
a = 3 (300 yen): 50b + 10c = 50 → b = 0, c = 5 ✓ / b = 1, c = 0 ✓
a = 2 (200 yen): 50b + 10c = 150 → b = 2, c = 5 ✓ / b = 3, c = 0 ✓
a = 1 (100 yen): 50b + 10c = 250 → b = 4, c = 5 ✓
a = 0: 50b + 10c = 350 → impossible because there are only four 50-yen coins
Answer: 5 ways: (3, 0, 5), (3, 1, 0), (2, 2, 5), (2, 3, 0), and (1, 4, 5)
There are three 100-yen coins, four 50-yen coins, and five 10-yen coins in a wallet. How many ways are there to pay exactly 350 yen using these coins?
Solution: 100a + 50b + 10c = 350 (a ≦ 3, b ≦ 4, c ≦ 5)
Consider the cases in order, starting with the coins of the greatest value.
a = 3 (300 yen): 50b + 10c = 50 → b = 0, c = 5 ✓ / b = 1, c = 0 ✓
a = 2 (200 yen): 50b + 10c = 150 → b = 2, c = 5 ✓ / b = 3, c = 0 ✓
a = 1 (100 yen): 50b + 10c = 250 → b = 4, c = 5 ✓
a = 0: 50b + 10c = 350 → impossible because there are only four 50-yen coins
Answer: 5 ways: (3, 0, 5), (3, 1, 0), (2, 2, 5), (2, 3, 0), and (1, 4, 5)
Key Points
- Considering cases from the coins with the greatest value helps reduce omissions.
- Be sure to follow the upper limit on the number of each type of coin you have.
- Record the answers you find in a table as you work to prevent calculation errors.
- You are often asked, “How many ways?” Be sure to count the number of answers you find at the end.
Practice Problems
- You have six 10-yen coins and eight 5-yen coins. How many ways are there to pay exactly 50 yen?
- Find all the ways to make exactly 120 yen using 50-yen and 10-yen coins. Assume that you may use any number of either coin.
- You are buying cakes costing 150 yen each and cookies costing 80 yen each. You want to buy as many as possible while keeping the total at no more than 1,000 yen. Think of combinations whose total price is exactly how many yen.
Answers and Explanations
- Answer: 3 ways
Explanation: Let x be the number of 10-yen coins (0 ≦ x ≦ 6) and y the number of 5-yen coins (0 ≦ y ≦ 8). 10x + 5y = 50 → 2x + y = 10. x = 0: y = 10 → impossible because y ≦ 8. x = 1: y = 8 → y ≦ 8✓. x = 2: y = 6✓. x = 3: y = 4✓. x = 4: y = 2✓. x = 5: y = 0✓. x = 6: y = 10 − 12 = −2 → impossible. Answer: (1,8), (2,6), (3,4), (4,2), and (5,0), for 5 ways. - Answer: 3 ways: (zero 50-yen coins and twelve 10-yen coins), (one 50-yen coin and seven 10-yen coins), and (two 50-yen coins and two 10-yen coins)
Explanation: 50x + 10y = 120 (x and y are nonnegative integers). x = 0: 10y = 120 → y = 12✓. x = 1: 10y = 70 → y = 7✓. x = 2: 10y = 20 → y = 2✓. x = 3: 50 × 3 = 150 > 120 → impossible. Answer: (0,12), (1,7), and (2,2), for 3 ways. Check: 50 × 2 + 10 × 2 = 100 + 20 = 120✓ - Answer: Several exact totals are possible depending on the combination of cakes and cookies (for example, six cakes and zero cookies cost 900 yen)
Explanation: 150x + 80y ≦ 1,000 and 150x + 80y = ? (an exact total). For a total of exactly 1,000 yen: 150x + 80y = 1,000 → 15x + 8y = 100. y = 0: 15x = 100 → not divisible. y = 5: 15x = 60 → x = 4✓ (four cakes and five cookies, 600 + 400 = 1,000✓). y = 10: 15x = 20 → not divisible. y = 15 or more: 8 × 15 = 120 > 100 → impossible. There is a combination totaling exactly 1,000 yen: four cakes and five cookies. Total number of items = 9 (one example of the maximum number purchased).