|
Question 1176883: Part a: Suppose you owe 10 dollars to a friend. Each week you pay your friend at least 1 dollar back. Sometimes however you might pay your friend back 2 dollars in a week and other times you might pay your friend 5 dollars in a week. How many different payment sequences are possible? Here are a couple possible sequences:
1-1-1-1-1-1-1-1-1-1 , 5-5 , 5-2-2-1 , 2-2-1-5 , etc…
Hint: Try to find a recursive function that answers this question for n-dollars and then use it on an n-value of 10.
Part b: Give another function to answer part a, but this time your function must NOT be recursive. Hint: Think about the counting theory we learned this term.
Answer by CPhill(1959)   (Show Source):
You can put this solution on YOUR website! Absolutely, let's break down this problem into parts.
**Part a: Recursive Function**
**1. Define the Recursive Function**
Let `f(n)` be the number of different payment sequences to pay back `n` dollars.
**2. Base Cases**
* `f(0) = 1` (If you owe 0 dollars, there's 1 way: do nothing.)
* `f(n) = 0` if `n < 0` (You can't pay back a negative amount.)
**3. Recursive Step**
To pay back `n` dollars, you can make the last payment 1, 2, or 5 dollars. So:
* `f(n) = f(n-1) + f(n-2) + f(n-5)`
**4. Calculate f(10)**
Let's compute the values iteratively:
* `f(0) = 1`
* `f(1) = f(0) = 1`
* `f(2) = f(1) + f(0) = 1 + 1 = 2`
* `f(3) = f(2) + f(1) = 2 + 1 = 3`
* `f(4) = f(3) + f(2) = 3 + 2 = 5`
* `f(5) = f(4) + f(3) + f(0) = 5 + 3 + 1 = 9`
* `f(6) = f(5) + f(4) + f(1) = 9 + 5 + 1 = 15`
* `f(7) = f(6) + f(5) + f(2) = 15 + 9 + 2 = 26`
* `f(8) = f(7) + f(6) + f(3) = 26 + 15 + 3 = 44`
* `f(9) = f(8) + f(7) + f(4) = 44 + 26 + 5 = 75`
* `f(10) = f(9) + f(8) + f(5) = 75 + 44 + 9 = 128`
**Answer (Part a):** There are 128 different payment sequences.
**Part b: Non-Recursive Function (Counting Theory)**
**1. Break Down the Problem**
We need to find the number of ways to express 10 as a sum of 1s, 2s, and 5s.
**2. Consider Possible Combinations**
We can systematically list the possible combinations:
* **Only 1s:** 10 ones (1 way)
* **Using 5s:**
* Two 5s (1 way)
* One 5:
* One 5, five 1s (1 way)
* One 5, two 2s, one 1 (number of ways to arrange them)
* **Using 2s (without 5s):**
* Five 2s (1 way)
* Four 2s, two 1s (number of ways to arrange them)
* Three 2s, four 1s (number of ways to arrange them)
* Two 2s, six 1s (number of ways to arrange them)
* One 2, eight 1s (number of ways to arrange them)
* Ten 1s (1 way)
**3. Use Combinations**
We'll use combinations to count the arrangements:
* **Two 5s:** 1 way
* **One 5:**
* One 5, five 1s: 6! / (5!1!) = 6 ways
* One 5, two 2s, one 1: 4! / (1!2!1!) = 12 ways
* **Only 2s:**
* Five 2s: 1 way
* Four 2s, two 1s: 6! / (4!2!) = 15 ways
* Three 2s, four 1s: 7! / (3!4!) = 35 ways
* Two 2s, six 1s: 8! / (2!6!) = 28 ways
* One 2, eight 1s: 9! / (1!8!) = 9 ways
* Ten 1s: 1 way
**4. Sum the Combinations**
1 + 6 + 12 + 1 + 15 + 35 + 28 + 9 + 1 = 128
**Answer (Part b):** There are 128 different payment sequences.
**Non-Recursive Function (Conceptual)**
More generally, you'd need to:
1. Enumerate all possible combinations of 1s, 2s, and 5s that sum to 10.
2. For each combination, use the multinomial coefficient formula to determine the number of distinct arrangements: `n! / (n1! * n2! * n3!)` where `n` is the total number of payments, and `n1`, `n2`, and `n3` are the numbers of 1s, 2s, and 5s, respectively.
3. Sum up the results from step 2.
|
|
|
| |
