Question

You want to make n cents of postage using only 5-cent and 12-cent stamps. Find all of the positive integers n for which this is possible (you might need to investigate a lot of specific values of n before knowing the answer!). Then give a careful proof of your claim by strong mathematical induction.

Answer 1

To find the positive integers n for which it is possible to make n cents of postage using only 5-cent and 12-cent stamps, we can use the coin change problem technique. By creating a table and filling it in with the minimum number of coins required to make each value, we can determine the valid solutions.

Step-by-step explanation:

To determine the positive integers n for which it is possible to make n cents of postage using only 5-cent and 12-cent stamps, we can use a technique called the coin change problem. We start by creating a table with rows representing the different denominations (5 cents and 12 cents) and columns representing the values from 0 to n. We then fill in the table by finding the minimum number of coins required to make each value from 0 to n.

For example, for n = 0, we would need 0 coins. For n = 1, we would need 1 coin of value 5 cents. For n = 2, we can use 2 coins of 1 cent each. For n = 3, we would need 2 coins of 2 cents each. And so on.

We continue filling in the table until we reach n cents. Any value of n for which the table shows that it is possible to make that amount of postage using only 5-cent and 12-cent stamps is considered a valid solution. The table can also help us identify patterns and generalize the possible values of n.

Answer 2

To find all positive integers n for which it is possible to make n cents using 5-cent and 12-cent stamps, we can use strong mathematical induction. The base case is n = 5, and we can show that for any k ≥ 5, it is possible to make (k+1) cents using the stamps. Therefore, the set of positive integers for which this is possible is {5, 6, 7, 8, ...}.

Step-by-step explanation:

To find all the positive integers n for which it is possible to make n cents of postage using only 5-cent and 12-cent stamps, we need to determine if there is a solution for each value of n. Here's how we can do it:

1. If n is less than 5, there is no way to achieve n cents using only 5-cent and 12-cent stamps.
2. For n ≥ 5, we can use strong mathematical induction to prove that it is possible to make n cents using only 5-cent and 12-cent stamps.
3. Base Case: For n = 5, we can use one 5-cent stamp.
4. Inductive Step: Assume that it is possible to make k cents using only 5-cent and 12-cent stamps, where k > 5. We need to show that it is also possible to make (k+1) cents.
5. To do this, we can consider two cases:
   1. Case 1: Using one 5-cent stamp and making (k-4) cents using the remaining stamps. Since (k-4) ≥ 5 and we have already shown it is possible to make (k-4) cents, we can add one more 5-cent stamp to make (k+1) cents.
6. Case 2: Using one 12-cent stamp and making (k-11) cents using the remaining stamps. Since (k-11) ≥ 5 and we have already shown it is possible to make (k-11) cents, we can add one more 12-cent stamp to make (k+1) cents.

Since we have shown that it is possible to make (k+1) cents for any k ≥ 5, we can conclude that it is possible to make any positive integer n ≥ 5 using only 5-cent and 12-cent stamps.

Therefore, the set of positive integers for which it is possible to make n cents using only 5-cent and 12-cent stamps is {5, 6, 7, 8, ...}.