Get Help

Turn on suggestions

Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

Showing results for

- Community
- :
- PTC Mathcad
- :
- PTC Mathcad
- :
- Making change for a dollar.

Options

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Mute
- Printer Friendly Page

Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

Showing results for

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Notify Moderator

07-04-2003
03:00 AM

07-04-2003
03:00 AM

Making change for a dollar.

My mother was posed a question that read roughly as "How many ways are there to make change for a dollar?" The only coins are the penny, nickel, dime, and quarter. Others working with her used the good old pencil and paper approach and tried listing all combinations. Here is a much simpler way that can avoid a lot of the work. It is based on a computer science technique known as "linear programming."

At each step, keep track of how many ways there are to make change for each amount up to 100. (100 cents to a dollar).

Start with the quarter.

0 : 1

25 : 1

50 : 1

75 : 1

100 : 1

Now, go through with the dime. For each entry above, add that quantity to monetary amount 10 cents greater. (Ie, that larger quantity can be obtained in the same number of ways as the entry being considered by just adding a dime.) It is important to start with "0" cents and work your way up.

0 : 1

10 : 1

20 : 1

25 : 1

30 : 1

35 : 1

40 : 1

45 : 1

50 : 2

55 : 1

60 : 2

65 : 1

70 : 2

75 : 2

80 : 2

85 : 2

90 : 2

95 : 2

100 : 3

What this means is that there is 1 way to get 40 with dimes and quarters, two ways to get 60, and three ways to get 100. Now, we do nickels.

0 : 1

5 : 1

10 : 2

15 : 2

20 : 3

25 : 4

30 : 5

35 : 6

40 : 7

45 : 8

50 : 10

55 : 11

60 : 13

65 : 14

70 : 16

75 : 18

80 : 20

85 : 22

90 : 24

95 : 26

100 : 29

Note that the numbers are building up rapidly. The next step would be to do the same to pennies. Luckily, this isn't actually necessary. The number of ways to reach 100 is the sum of all of those (since any way you can reach, say, 45, can be made into a unique combination of 100 by adding 55 pennies.) Thus, in general, you can find out the solution for ANY number 1-100 by adding up the numbers less or equal to it.

1 + 1 + 2 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 10 + 11 + 13 + 14 + 16 + 18 + 20 + 22 + 24 + 26 + 29 = 242

Thus, there are 242 combinations. I did tremendously less work than I would have enumerating all combinations. I have used this technique to treat quantities as high as a million dollars (using a computer of course). This would have been impossible had I tried listing all combinations.

Craig

At each step, keep track of how many ways there are to make change for each amount up to 100. (100 cents to a dollar).

Start with the quarter.

0 : 1

25 : 1

50 : 1

75 : 1

100 : 1

Now, go through with the dime. For each entry above, add that quantity to monetary amount 10 cents greater. (Ie, that larger quantity can be obtained in the same number of ways as the entry being considered by just adding a dime.) It is important to start with "0" cents and work your way up.

0 : 1

10 : 1

20 : 1

25 : 1

30 : 1

35 : 1

40 : 1

45 : 1

50 : 2

55 : 1

60 : 2

65 : 1

70 : 2

75 : 2

80 : 2

85 : 2

90 : 2

95 : 2

100 : 3

What this means is that there is 1 way to get 40 with dimes and quarters, two ways to get 60, and three ways to get 100. Now, we do nickels.

0 : 1

5 : 1

10 : 2

15 : 2

20 : 3

25 : 4

30 : 5

35 : 6

40 : 7

45 : 8

50 : 10

55 : 11

60 : 13

65 : 14

70 : 16

75 : 18

80 : 20

85 : 22

90 : 24

95 : 26

100 : 29

Note that the numbers are building up rapidly. The next step would be to do the same to pennies. Luckily, this isn't actually necessary. The number of ways to reach 100 is the sum of all of those (since any way you can reach, say, 45, can be made into a unique combination of 100 by adding 55 pennies.) Thus, in general, you can find out the solution for ANY number 1-100 by adding up the numbers less or equal to it.

1 + 1 + 2 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 10 + 11 + 13 + 14 + 16 + 18 + 20 + 22 + 24 + 26 + 29 = 242

Thus, there are 242 combinations. I did tremendously less work than I would have enumerating all combinations. I have used this technique to treat quantities as high as a million dollars (using a computer of course). This would have been impossible had I tried listing all combinations.

Craig

Labels:

3 REPLIES 3

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Notify Moderator

07-04-2003
03:00 AM

07-04-2003
03:00 AM

Making change for a dollar.

�Change� problems are classic in combinatorial mathematics. Using this generating polynomial,

.

we find that the coefficient of x^{100} is indeed 242. The coefficient of x^{53} is 49, so there are 49 ways to make 53cents using pennies, nickels, dimes and quarters. Using MathCad or StudyWorks we can collect the coefficients of the polynomial.

May I suggest a wonderful little book:__Mathematics of Choice__ by Ivan Niven. The book is part of The Mathematical Association of America, New Mathematical Library.

https://enterprise.maa.org/ecomtpro/Timssnet/products/TNT_products.cfm

PKA

.

we find that the coefficient of x

May I suggest a wonderful little book:

https://enterprise.maa.org/ecomtpro/Timssnet/products/TNT_products.cfm

PKA

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Notify Moderator

07-04-2003
03:00 AM

07-04-2003
03:00 AM

Making change for a dollar.

I have seen the polynomial before. However, it is really just a fancy way of rewriting the original problem. Expanding it is also no easier to calculate than the original problem. Substituting a "sufficiently large" value for x is even worse. I see no way the use of such a polynomial can aid in computation by humans or by computers. A closed form solution, however, would be interesting to see. Tests suggest such a formula probably exists. For powers of ten, an obvious pattern emerges after the first vew powers.

The simple method illustrated initially takes O(r n) steps, where "r" is the number of coins and "n" is the number of cents for which change is sought. Moreover, the results for all amounts of change up to n can be obtained at the same time at no additional cost.

If "x" is replaced by a constant with "b" bits (or digits), and multiplication is performed, O(r n b log(n b)) is a fair estimate.

Expanding the polynomial (using convolution and FFT) would be about O(r n log n). Retrieving only the coefficient needed would take O(r n) as well, but the constant would be a bit larger.

Note: O(n^2), for example, means that the time required to compute grows no faster than the square of the size of the input. If the input doubles, the time required might quadruple.

The nice part about a closed form solution is that the output may be calculated very quickly.

Craig

The simple method illustrated initially takes O(r n) steps, where "r" is the number of coins and "n" is the number of cents for which change is sought. Moreover, the results for all amounts of change up to n can be obtained at the same time at no additional cost.

If "x" is replaced by a constant with "b" bits (or digits), and multiplication is performed, O(r n b log(n b)) is a fair estimate.

Expanding the polynomial (using convolution and FFT) would be about O(r n log n). Retrieving only the coefficient needed would take O(r n) as well, but the constant would be a bit larger.

Note: O(n^2), for example, means that the time required to compute grows no faster than the square of the size of the input. If the input doubles, the time required might quadruple.

The nice part about a closed form solution is that the output may be calculated very quickly.

Craig

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Notify Moderator

07-22-2004
03:00 AM

07-22-2004
03:00 AM

Making change for a dollar.

is that book that good, dr. alford?

do u think "what is calculus about" by ww sawyer is good?

do u think "what is calculus about" by ww sawyer is good?