Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Describe the set of all possible dollar amounts that can be formed using only four and five dollar bills, and argue about the correctness of your answer using mathematical induction. Hint: Your solution should be in the form of a set. For example, the solution $€\{4, 5, 8, 9, 10, 12, ...\}$ implies you can represent dollar amounts $4, 5, 8, 9, 10$, and all integral amount greater than $12$.

share|improve this question
    
See solution in this entry: math.stackexchange.com/questions/654877/… –  Tom Collinge Feb 4 at 7:39
add comment

3 Answers 3

Any number multiple of $4$ can be easily formed i.e., $4,8,12,16,20\cdots$

For $m=4n+1=4(n-1)+5\implies $ we need $n\ge1\implies m\ge5$ i.e., $5,9,13,17\cdots$

For $m=4n+2=4(n-2)+5\cdot2\implies $ we need $n\ge2\implies m\ge10$ i.e., $10,14,18,22\cdots$

For $m=4n+3=4(n-3)+5\cdot3\implies $ we need $n\ge3\implies m\ge15$ i.e., $15,19,23,27\cdots$

The numbers those can not be formed are $1,2,3,6,7,11$

share|improve this answer
add comment

The Frobenius Coin problem with n = 2, gcd(4,5) = 1 . The number of non-representable dollar amounts is (4 - 1)*(5 - 1)/2 = 6 .

Link: http://en.wikipedia.org/wiki/Coin_problem

share|improve this answer
add comment

Since $8$ is possible, $12$ is possible. Use $4$ and then do $12-4$

Since $8$ is possible, $13$ is possible. Use $5$ and then do $13-5$

Since $9$ is possible, $14$ is possible. Use $5$ and then do $14-5$

Since $10$ is possible, $15$ is possible. Use $5$ and then do $15-5$

After $15$ you can always get one of $12$, $13$, $14$, $15$ by using just $4$ repeatedly.

You can use induction as follows: Suppose all values $\ge 12$ and up to $n>15$ is possible. Then $n+1$ is possible since $n+1 - 4$ is between $12$ and $n$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.