Question

2. The official currency of the Kingdom of Mathemagiclandistan is Shrute-bucks. Shrute-bucks bills come in denominations of 3 and 5.

a.) What is the smallest amount of Shrute-bucks, n that can be made using Shrute-buck bills so that every amount greater than or equal to n can also be made using Shrute-buck bills?

b.) Use either the principle of mathematical induction or strong induction to prove your answer from a.)

Answer 1

a) 8 is the least possible amount that could be formed.
b) We can pick up a 3 and a 5 bill to form 8. That is the result hold for n=8. Now consider n=9, we add one to the previous combination. That one is absorbed into 5 and it turns 6. The amount 6 can be formed by using two 3 bills. So the new combination is 3+3+3. Hence the result hold for n=9 also.
Now assume the result for n, that is the amount is raisable. Then add one to it. It is either absorbed into a 5 or 3. If it is possible to absorb it into a 5, it turns 6 and then 6 is 3+3. Then the proof is over. If there is no any 5, we must have atleast three 3s out there (for n>9). Then one of the 3s absorb 1 and stay 4. Any other 3 can be decomposed into a 1 and a 2. The 1 thus formed is just added with 4 and turns 5. The 2 remained combines with an unbroken 3 to form a 5. That is, three 3s turned into two 5s in the combination when we perform the addition.
In both of these cases , we have an affordable decomposition. Hence the proof by induction.