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

closed as off-topic by le gâteau au fromage, Tomás, martini, Adam Hughes, Mathmo123 Aug 6 at 18:18

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – le gâteau au fromage, Tomás, Mathmo123
If this question can be reworded to fit the rules in the help center, please edit the question.

See solution in this entry: math.stackexchange.com/questions/654877/… –  Tom Collinge Feb 4 at 7:39

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

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

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

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