Branching Method ① Finding All Combinations
The branching method is used for problems that ask you to find all combinations without missing any. It is named this way because once one answer is found, more answers appear one after another, like sweet potatoes connected to a vine.
Basic Method
Find all the solutions to “ax + by = c” (a, b, and c are fixed numbers, and x and y are nonnegative integers).
- ① Substitute one number, such as x, in order from 0.
- ② Check whether the remaining expression can be calculated exactly.
- ③ Check whether the other number, y, is a nonnegative integer.
- ④ Put all the combinations you find into a table.
Example Problem
Find all the ways to pay exactly 31 yen using combinations of 5-yen and 3-yen coins. (You may use zero or more of either coin.)
Solution: 5x + 3y = 31 (x: number of 5-yen coins, y: number of 3-yen coins)
Try substituting x in order from 0.
x = 0: 3y = 31 → not divisible
x = 1: 3y = 26 → not divisible
x = 2: 3y = 21 → y = 7 ✓
x = 3: 3y = 16 → not divisible
x = 4: 3y = 11 → not divisible
x = 5: 3y = 6 → y = 2 ✓
x = 6: 3y = 1 → not divisible
x = 7: 5 × 7 = 35, which exceeds 31, so stop
Answer: There are 2 ways: (x, y) = (2, 7) and (5, 2)
Find all the ways to pay exactly 31 yen using combinations of 5-yen and 3-yen coins. (You may use zero or more of either coin.)
Solution: 5x + 3y = 31 (x: number of 5-yen coins, y: number of 3-yen coins)
Try substituting x in order from 0.
x = 0: 3y = 31 → not divisible
x = 1: 3y = 26 → not divisible
x = 2: 3y = 21 → y = 7 ✓
x = 3: 3y = 16 → not divisible
x = 4: 3y = 11 → not divisible
x = 5: 3y = 6 → y = 2 ✓
x = 6: 3y = 1 → not divisible
x = 7: 5 × 7 = 35, which exceeds 31, so stop
Answer: There are 2 ways: (x, y) = (2, 7) and (5, 2)
Key Points
- Increase one number by 1 each time, starting from 0.
- Carefully check one by one whether the result is divisible by 3 or by 2.
- Once the total exceeds the target amount, increasing the number further will not work, so stop there.
- Always put the answers you find into a table to avoid overlooking any.
Practice Problems
- Find all the ways to make exactly 30 yen using combinations of 4-yen and 7-yen stamps.
- Find all the ways to make 21 yen using exactly three coins and only 10-yen and 1-yen coins.
- Find all pairs of nonnegative integers (x, y) such that x + 3y = 20.
Answers and Explanations
- Answer: One way: four 4-yen stamps and two 7-yen stamps
Explanation: 4x + 7y = 30 (x: number of 4-yen stamps, y: number of 7-yen stamps; both are nonnegative integers). Checking y = 0, 1, 2, 3, and 4 in order, the only integer solution is y = 2 and x = 4. Therefore, there is one way: four 4-yen stamps and two 7-yen stamps, and 4 × 4 + 7 × 2 = 30. - Answer: One way: two 10-yen coins and one 1-yen coin
Explanation: Let x be the number of 10-yen coins and y the number of 1-yen coins. Then 10x + y = 21 and x + y = 3. Substitute y = 3 − x: 10x + (3 − x) = 21. 9x = 18. x = 2. y = 3 − 2 = 1. Answer: two 10-yen coins and one 1-yen coin. Check: 10 × 2 + 1 × 1 = 21✓, 2 + 1 = 3 coins✓ - Answer: There are 7 ways: (x,y) = (20,0), (17,1), (14,2), (11,3), (8,4), (5,5), and (2,6)
Explanation: x + 3y = 20 (x and y are nonnegative integers). y = 0: x = 20✓. y = 1: x = 17✓. y = 2: x = 14✓. y = 3: x = 11✓. y = 4: x = 8✓. y = 5: x = 5✓. y = 6: x = 2✓. y = 7: x = 20 − 21 = −1, which is negative and therefore not allowed. Answer: 7 combinations.