We will learn branching-method problems with additional conditions, such as “one type is more numerous than the other” and “you can use no more than a certain number of items in total.”
Organize the Conditions Before Solving
As more conditions are added, the number of answers decreases greatly. First list the conditions, then solve the problem using the basic method.
Example Problem
Make exactly 200 yen using 50-yen and 10-yen coins. Find all the ways in which the total number of coins used is no more than 8.
Solution: 50x + 10y = 200 (x: 50-yen coins, y: 10-yen coins), x + y ≦ 8
Try substituting x in order from 0.
x = 0: 10y = 200 → y = 20, total 20 coins → not allowed
x = 1: 10y = 150 → y = 15, total 16 coins → not allowed
x = 2: 10y = 100 → y = 10, total 12 coins → not allowed
x = 3: 10y = 50 → y = 5, total 8 coins → OK ✓
x = 4: 10y = 0 → y = 0, total 4 coins → OK ✓
Answer: 2 ways: (three 50-yen coins, five 10-yen coins) and (four 50-yen coins, zero 10-yen coins)
Make exactly 200 yen using 50-yen and 10-yen coins. Find all the ways in which the total number of coins used is no more than 8.
Solution: 50x + 10y = 200 (x: 50-yen coins, y: 10-yen coins), x + y ≦ 8
Try substituting x in order from 0.
x = 0: 10y = 200 → y = 20, total 20 coins → not allowed
x = 1: 10y = 150 → y = 15, total 16 coins → not allowed
x = 2: 10y = 100 → y = 10, total 12 coins → not allowed
x = 3: 10y = 50 → y = 5, total 8 coins → OK ✓
x = 4: 10y = 0 → y = 0, total 4 coins → OK ✓
Answer: 2 ways: (three 50-yen coins, five 10-yen coins) and (four 50-yen coins, zero 10-yen coins)
The Condition “Use at Least One Coin”
When the condition says, “You must use at least one of each coin,” consider x ≧ 1 and y ≧ 1. Find all the answers using the basic method, then remove those that do not follow the rules.
Key Points
- Write additional conditions in forms such as “x + y ≦ ○” or “x ≧ 1.”
- First find all the answers using the basic method, then remove those that do not meet the conditions.
- Making a table makes it easier to check whether each answer meets the conditions.
Practice Problems
- Find all the ways to make exactly 20 yen using 5-yen and 2-yen stamps when the total number of stamps is no more than 6.
- Find all the ways to make 700 yen using 100-yen and 50-yen coins when at least two 100-yen coins are used.
- Apples cost 120 yen each and mandarins cost 80 yen each. Find all combinations of apples and mandarins that total exactly 1,000 yen.
Answers and Explanations
- Answer: Two ways: (two 5-yen stamps, five 2-yen stamps) and (four 5-yen stamps, zero 2-yen stamps)
Explanation: 5x + 2y = 20 and x + y ≦ 6 (x and y are nonnegative integers). x = 0: 2y = 20 → y = 10, total 10 stamps → does not meet the condition. x = 1: 2y = 15 → not divisible. x = 2: 2y = 10 → y = 5, total 7 stamps → does not meet the condition (7 > 6). x = 3: 2y = 5 → not divisible. x = 4: 2y = 0 → y = 0, total 4 stamps✓. x = 5 or more: 5 × 5 = 25 > 20 → impossible. Answer: one combination, (x,y) = (4,0). Check: 5 × 4 + 2 × 0 = 20✓, 4 + 0 = 4 ≦ 6✓ - Answer: (two 100-yen coins, six 50-yen coins), (three 100-yen coins, two 50-yen coins), (four 100-yen coins, zero 50-yen coins), and (two 100-yen coins, six 50-yen coins); since seven or more 100-yen coins are impossible, there are 3 ways
Explanation: 100x + 50y = 700 and x ≧ 2 (x and y are nonnegative integers). x = 2: 50y = 500 → y = 10✓. x = 3: 50y = 400 → y = 8✓. x = 4: 50y = 300 → y = 6✓. x = 5: 50y = 200 → y = 4✓. x = 6: 50y = 100 → y = 2✓. x = 7: 50y = 0 → y = 0✓. x = 8: 100 × 8 = 800 > 700 → impossible. Answer: 6 combinations, (2,10), (3,8), (4,6), (5,4), (6,2), and (7,0). - Answer: Searching for integer solutions, (zero apples, 12.5 mandarins) and (five apples, 2.5 mandarins) are not allowed because they are not integers. Integer solutions: (zero apples, 12.5 mandarins is not allowed)
Explanation: 120x + 80y = 1,000 (x and y are nonnegative integers). Divide both sides by 40: 3x + 2y = 25. y = 0: 3x = 25 → not divisible. y = 1: 3x = 23 → not divisible. y = 2: 3x = 21 → x = 7✓. y = 3: 3x = 19 → not divisible. y = 4: 3x = 17 → not divisible. y = 5: 3x = 15 → x = 5✓. y = 8: 3x = 9 → x = 3✓. y = 11: 3x = 3 → x = 1✓. Answer: 4 combinations, (x,y) = (7,2), (5,5), (3,8), and (1,11).