{"id":3566,"date":"2023-11-23T07:38:06","date_gmt":"2023-11-23T12:38:06","guid":{"rendered":"https:\/\/sites.williams.edu\/Morgan\/?page_id=3566"},"modified":"2023-11-27T16:02:32","modified_gmt":"2023-11-27T21:02:32","slug":"293-ways-to-make-change-for-a-dollar","status":"publish","type":"page","link":"https:\/\/sites.williams.edu\/Morgan\/math-chat-archives\/293-ways-to-make-change-for-a-dollar\/","title":{"rendered":"293 Ways to Make Change for a Dollar"},"content":{"rendered":"

April 19, 2001<\/p>\n

 <\/p>\n

Old Challenge<\/b>\u00a0(Joe Shipman). Larry King said in his\u00a0USA Today<\/i>\u00a0column that there are 293 ways to make change for a dollar. Is this correct? (Assume only currently minted denominations.)<\/p>\n

Answer.<\/b>\u00a0Yes, if you count a one-dollar coin in change. Raymond Hettinger listed all 293 possibilities, appended at end of column. Michael Caulfield counted up the 292 possibilities other than a one-dollar coin as follows:<\/p>\n

Given that 1 half dollar will be used, there are 50 combinations:
\nanother half dollar (1 way)
\n2 quarters (1 way)
\n1 quarter with: 2 dimes (2 ways), 1 dime (4), or 0 dimes (6).
\n0 quarters with: 5 dimes (1), 4 (3), 3 (5), 2 (7), 1 (9), or 0 (11).<\/p>\n

 <\/p>\n

Given that no half dollars will be used, there are 242 combinations:
\n4 quarters (1 way)
\n3 quarters with: 2 dimes (2 ways), 1 (4), or 0 (6).
\n2 quarters with: 5 dimes (1), 4 (3), 3 (5), 2 (7), 1 (9), or 0 (11).
\n1 quarter with: 7 dimes (2), 6 (4), 5 (6), 4 (8), 3 (10), 2 (12), 1 (14), 0 (16)
\n0 quarters with: 10 dimes (1), 9 (3), 8 (5), 7 (7), 6 (9), 5 (11), 4 (13), 3 (15), 2 (17), 1 (19), 0 (21).<\/p>\n

 <\/p>\n

Torsten Sillke discussed how such computations can be accomplished with generating functions. See Herbert’s Wilf’s “Lectures on Integer Partitions” (page 10) at\u00a0http:\/\/www.math.upenn.edu\/~wilf<\/a>\u00a0The answer to our problem (293) is the coefficient of x^100 in the reciprocal of the following:<\/p>\n

(1-x)(1-x5<\/sup>)(1-x10<\/sup>)(1-x25<\/sup>)(1-x50<\/sup>)(1-x100<\/sup>)<\/p>\n

Al Zimmermann provided the following table of the numbers of ways you can exchange various units of currency for smaller units of currency:<\/p>\n

 <\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
Unit of Currency<\/td>\nNumber of Ways to Make Change<\/td>\n<\/tr>\n
1 cent<\/td>\n0<\/td>\n<\/tr>\n
5 cents<\/td>\n1<\/td>\n<\/tr>\n
10 cents<\/td>\n3<\/td>\n<\/tr>\n
25 cents<\/td>\n12<\/td>\n<\/tr>\n
50 cents<\/td>\n49<\/td>\n<\/tr>\n
$1<\/td>\n292<\/td>\n<\/tr>\n
$2<\/td>\n2,728<\/td>\n<\/tr>\n
$5<\/td>\n111,022<\/td>\n<\/tr>\n
$10<\/td>\n3,237,134<\/td>\n<\/tr>\n
$20<\/td>\n155,848,897<\/td>\n<\/tr>\n
$50<\/td>\n58,853,234,018<\/td>\n<\/tr>\n
$100<\/td>\n9,823,546,661,905<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

 <\/p>\n

Zimmermann added: I did allow $2 bills. I did not distinguish between $1 coins and $1 bills in change. I thought about that one and decided that if I did distinguish, then I should also distinguish among the 50 different quarters now being issued. And I really didn’t want to do that.<\/p>\n

Following Caulfield and Zimmermann and disputing Larry King, Walter Wright says that a dollar coin cannot be considered change for a dollar bill:\u00a0Webster’s New World Dictionary<\/i>\u00a0defines\u00a0change<\/i>\u00a0as “a number of coins or bills whose total value equals a single\u00a0larger<\/i>\u00a0coin or bill.”<\/p>\n

 <\/p>\n

Questionable Mathematics.\u00a0<\/b>Al Zimmermann reports that: “About three years ago I went to a Citibank ATM in midtown Manhattan to withdraw some cash. The machine rejected my request with the following message:<\/p>\n

I cannot give you $130 because I only have bills in $50 and $20 denominations. Please choose another amount.”<\/p>\n

Of course $130 = $50 + 4 x $20.<\/p>\n

Readers are invited to submit more examples of questionable mathematics.<\/p>\n

New Challenge.<\/b>\u00a0What is the largest positive number that you can represent with three, distinct standard mathematical symbols, such as 8×9? The smallest?<\/p>\n

 <\/p>\n

\n

Send answers, comments, and new questions by email to\u00a0Frank.Morgan@williams.edu,<\/a>\u00a0to be eligible for\u00a0Flatland\u00a0<\/i>and other book awards. Winning answers will appear in the next Math Chat. Math Chat appears on the first and third Thursdays of each month. Prof. Morgan’s homepage is at\u00a0www.williams.edu\/Mathematics\/fmorgan.<\/a><\/p>\n

THE MATH CHAT BOOK,<\/a>\u00a0including a $1000 Math Chat Book\u00a0QUEST,\u00a0<\/a>questions and answers, and a list of past challenge winners, is now available from the MAA (800-331-1622).<\/p>\n

\n

Raymond Hettinger’s list of the 293 ways to make change for a dollar:<\/p>\n

1 : 0 0 0 0 0 100 (0 dollars, 0 half-dollars, 0 quarters, 0 dimes, 0
\nnickels, 100 pennies)
\n2 : 0 0 0 0 1 95
\n3 : 0 0 0 0 2 90
\n4 : 0 0 0 0 3 85
\n5 : 0 0 0 0 4 80
\n6 : 0 0 0 0 5 75
\n7 : 0 0 0 0 6 70
\n8 : 0 0 0 0 7 65
\n9 : 0 0 0 0 8 60
\n10 : 0 0 0 0 9 55
\n11 : 0 0 0 0 10 50
\n12 : 0 0 0 0 11 45
\n13 : 0 0 0 0 12 40
\n14 : 0 0 0 0 13 35
\n15 : 0 0 0 0 14 30
\n16 : 0 0 0 0 15 25
\n17 : 0 0 0 0 16 20
\n18 : 0 0 0 0 17 15
\n19 : 0 0 0 0 18 10
\n20 : 0 0 0 0 19 5
\n21 : 0 0 0 0 20 0
\n22 : 0 0 0 1 0 90
\n23 : 0 0 0 1 1 85
\n24 : 0 0 0 1 2 80
\n25 : 0 0 0 1 3 75
\n26 : 0 0 0 1 4 70
\n27 : 0 0 0 1 5 65
\n28 : 0 0 0 1 6 60
\n29 : 0 0 0 1 7 55
\n30 : 0 0 0 1 8 50
\n31 : 0 0 0 1 9 45
\n32 : 0 0 0 1 10 40
\n33 : 0 0 0 1 11 35
\n34 : 0 0 0 1 12 30
\n35 : 0 0 0 1 13 25
\n36 : 0 0 0 1 14 20
\n37 : 0 0 0 1 15 15
\n38 : 0 0 0 1 16 10
\n39 : 0 0 0 1 17 5
\n40 : 0 0 0 1 18 0
\n41 : 0 0 0 2 0 80
\n42 : 0 0 0 2 1 75
\n43 : 0 0 0 2 2 70
\n44 : 0 0 0 2 3 65
\n45 : 0 0 0 2 4 60
\n46 : 0 0 0 2 5 55
\n47 : 0 0 0 2 6 50
\n48 : 0 0 0 2 7 45
\n49 : 0 0 0 2 8 40
\n50 : 0 0 0 2 9 35
\n51 : 0 0 0 2 10 30
\n52 : 0 0 0 2 11 25
\n53 : 0 0 0 2 12 20
\n54 : 0 0 0 2 13 15
\n55 : 0 0 0 2 14 10
\n56 : 0 0 0 2 15 5
\n57 : 0 0 0 2 16 0
\n58 : 0 0 0 3 0 70
\n59 : 0 0 0 3 1 65
\n60 : 0 0 0 3 2 60
\n61 : 0 0 0 3 3 55
\n62 : 0 0 0 3 4 50
\n63 : 0 0 0 3 5 45
\n64 : 0 0 0 3 6 40
\n65 : 0 0 0 3 7 35
\n66 : 0 0 0 3 8 30
\n67 : 0 0 0 3 9 25
\n68 : 0 0 0 3 10 20
\n69 : 0 0 0 3 11 15
\n70 : 0 0 0 3 12 10
\n71 : 0 0 0 3 13 5
\n72 : 0 0 0 3 14 0
\n73 : 0 0 0 4 0 60
\n74 : 0 0 0 4 1 55
\n75 : 0 0 0 4 2 50
\n76 : 0 0 0 4 3 45
\n77 : 0 0 0 4 4 40
\n78 : 0 0 0 4 5 35
\n79 : 0 0 0 4 6 30
\n80 : 0 0 0 4 7 25
\n81 : 0 0 0 4 8 20
\n82 : 0 0 0 4 9 15
\n83 : 0 0 0 4 10 10
\n84 : 0 0 0 4 11 5
\n85 : 0 0 0 4 12 0
\n86 : 0 0 0 5 0 50
\n87 : 0 0 0 5 1 45
\n88 : 0 0 0 5 2 40
\n89 : 0 0 0 5 3 35
\n90 : 0 0 0 5 4 30
\n91 : 0 0 0 5 5 25
\n92 : 0 0 0 5 6 20
\n93 : 0 0 0 5 7 15
\n94 : 0 0 0 5 8 10
\n95 : 0 0 0 5 9 5
\n96 : 0 0 0 5 10 0
\n97 : 0 0 0 6 0 40
\n98 : 0 0 0 6 1 35
\n99 : 0 0 0 6 2 30
\n100 : 0 0 0 6 3 25
\n101 : 0 0 0 6 4 20
\n102 : 0 0 0 6 5 15
\n103 : 0 0 0 6 6 10
\n104 : 0 0 0 6 7 5
\n105 : 0 0 0 6 8 0
\n106 : 0 0 0 7 0 30
\n107 : 0 0 0 7 1 25
\n108 : 0 0 0 7 2 20
\n109 : 0 0 0 7 3 15
\n110 : 0 0 0 7 4 10
\n111 : 0 0 0 7 5 5
\n112 : 0 0 0 7 6 0
\n113 : 0 0 0 8 0 20
\n114 : 0 0 0 8 1 15
\n115 : 0 0 0 8 2 10
\n116 : 0 0 0 8 3 5
\n117 : 0 0 0 8 4 0
\n118 : 0 0 0 9 0 10
\n119 : 0 0 0 9 1 5
\n120 : 0 0 0 9 2 0
\n121 : 0 0 0 10 0 0
\n122 : 0 0 1 0 0 75
\n123 : 0 0 1 0 1 70
\n124 : 0 0 1 0 2 65
\n125 : 0 0 1 0 3 60
\n126 : 0 0 1 0 4 55
\n127 : 0 0 1 0 5 50
\n128 : 0 0 1 0 6 45
\n129 : 0 0 1 0 7 40
\n130 : 0 0 1 0 8 35
\n131 : 0 0 1 0 9 30
\n132 : 0 0 1 0 10 25
\n133 : 0 0 1 0 11 20
\n134 : 0 0 1 0 12 15
\n135 : 0 0 1 0 13 10
\n136 : 0 0 1 0 14 5
\n137 : 0 0 1 0 15 0
\n138 : 0 0 1 1 0 65
\n139 : 0 0 1 1 1 60
\n140 : 0 0 1 1 2 55
\n141 : 0 0 1 1 3 50
\n142 : 0 0 1 1 4 45
\n143 : 0 0 1 1 5 40
\n144 : 0 0 1 1 6 35
\n145 : 0 0 1 1 7 30
\n146 : 0 0 1 1 8 25
\n147 : 0 0 1 1 9 20
\n148 : 0 0 1 1 10 15
\n149 : 0 0 1 1 11 10
\n150 : 0 0 1 1 12 5
\n151 : 0 0 1 1 13 0
\n152 : 0 0 1 2 0 55
\n153 : 0 0 1 2 1 50
\n154 : 0 0 1 2 2 45
\n155 : 0 0 1 2 3 40
\n156 : 0 0 1 2 4 35
\n157 : 0 0 1 2 5 30
\n158 : 0 0 1 2 6 25
\n159 : 0 0 1 2 7 20
\n160 : 0 0 1 2 8 15
\n161 : 0 0 1 2 9 10
\n162 : 0 0 1 2 10 5
\n163 : 0 0 1 2 11 0
\n164 : 0 0 1 3 0 45
\n165 : 0 0 1 3 1 40
\n166 : 0 0 1 3 2 35
\n167 : 0 0 1 3 3 30
\n168 : 0 0 1 3 4 25
\n169 : 0 0 1 3 5 20
\n170 : 0 0 1 3 6 15
\n171 : 0 0 1 3 7 10
\n172 : 0 0 1 3 8 5
\n173 : 0 0 1 3 9 0
\n174 : 0 0 1 4 0 35
\n175 : 0 0 1 4 1 30
\n176 : 0 0 1 4 2 25
\n177 : 0 0 1 4 3 20
\n178 : 0 0 1 4 4 15
\n179 : 0 0 1 4 5 10
\n180 : 0 0 1 4 6 5
\n181 : 0 0 1 4 7 0
\n182 : 0 0 1 5 0 25
\n183 : 0 0 1 5 1 20
\n184 : 0 0 1 5 2 15
\n185 : 0 0 1 5 3 10
\n186 : 0 0 1 5 4 5
\n187 : 0 0 1 5 5 0
\n188 : 0 0 1 6 0 15
\n189 : 0 0 1 6 1 10
\n190 : 0 0 1 6 2 5
\n191 : 0 0 1 6 3 0
\n192 : 0 0 1 7 0 5
\n193 : 0 0 1 7 1 0
\n194 : 0 0 2 0 0 50
\n195 : 0 0 2 0 1 45
\n196 : 0 0 2 0 2 40
\n197 : 0 0 2 0 3 35
\n198 : 0 0 2 0 4 30
\n199 : 0 0 2 0 5 25
\n200 : 0 0 2 0 6 20
\n201 : 0 0 2 0 7 15
\n202 : 0 0 2 0 8 10
\n203 : 0 0 2 0 9 5
\n204 : 0 0 2 0 10 0
\n205 : 0 0 2 1 0 40
\n206 : 0 0 2 1 1 35
\n207 : 0 0 2 1 2 30
\n208 : 0 0 2 1 3 25
\n209 : 0 0 2 1 4 20
\n210 : 0 0 2 1 5 15
\n211 : 0 0 2 1 6 10
\n212 : 0 0 2 1 7 5
\n213 : 0 0 2 1 8 0
\n214 : 0 0 2 2 0 30
\n215 : 0 0 2 2 1 25
\n216 : 0 0 2 2 2 20
\n217 : 0 0 2 2 3 15
\n218 : 0 0 2 2 4 10
\n219 : 0 0 2 2 5 5
\n220 : 0 0 2 2 6 0
\n221 : 0 0 2 3 0 20
\n222 : 0 0 2 3 1 15
\n223 : 0 0 2 3 2 10
\n224 : 0 0 2 3 3 5
\n225 : 0 0 2 3 4 0
\n226 : 0 0 2 4 0 10
\n227 : 0 0 2 4 1 5
\n228 : 0 0 2 4 2 0
\n229 : 0 0 2 5 0 0
\n230 : 0 0 3 0 0 25
\n231 : 0 0 3 0 1 20
\n232 : 0 0 3 0 2 15
\n233 : 0 0 3 0 3 10
\n234 : 0 0 3 0 4 5
\n235 : 0 0 3 0 5 0
\n236 : 0 0 3 1 0 15
\n237 : 0 0 3 1 1 10
\n238 : 0 0 3 1 2 5
\n239 : 0 0 3 1 3 0
\n240 : 0 0 3 2 0 5
\n241 : 0 0 3 2 1 0
\n242 : 0 0 4 0 0 0
\n243 : 0 1 0 0 0 50
\n244 : 0 1 0 0 1 45
\n245 : 0 1 0 0 2 40
\n246 : 0 1 0 0 3 35
\n247 : 0 1 0 0 4 30
\n248 : 0 1 0 0 5 25
\n249 : 0 1 0 0 6 20
\n250 : 0 1 0 0 7 15
\n251 : 0 1 0 0 8 10
\n252 : 0 1 0 0 9 5
\n253 : 0 1 0 0 10 0
\n254 : 0 1 0 1 0 40
\n255 : 0 1 0 1 1 35
\n256 : 0 1 0 1 2 30
\n257 : 0 1 0 1 3 25
\n258 : 0 1 0 1 4 20
\n259 : 0 1 0 1 5 15
\n260 : 0 1 0 1 6 10
\n261 : 0 1 0 1 7 5
\n262 : 0 1 0 1 8 0
\n263 : 0 1 0 2 0 30
\n264 : 0 1 0 2 1 25
\n265 : 0 1 0 2 2 20
\n266 : 0 1 0 2 3 15
\n267 : 0 1 0 2 4 10
\n268 : 0 1 0 2 5 5
\n269 : 0 1 0 2 6 0
\n270 : 0 1 0 3 0 20
\n271 : 0 1 0 3 1 15
\n272 : 0 1 0 3 2 10
\n273 : 0 1 0 3 3 5
\n274 : 0 1 0 3 4 0
\n275 : 0 1 0 4 0 10
\n276 : 0 1 0 4 1 5
\n277 : 0 1 0 4 2 0
\n278 : 0 1 0 5 0 0
\n279 : 0 1 1 0 0 25
\n280 : 0 1 1 0 1 20
\n281 : 0 1 1 0 2 15
\n282 : 0 1 1 0 3 10
\n283 : 0 1 1 0 4 5
\n284 : 0 1 1 0 5 0
\n285 : 0 1 1 1 0 15
\n286 : 0 1 1 1 1 10
\n287 : 0 1 1 1 2 5
\n288 : 0 1 1 1 3 0
\n289 : 0 1 1 2 0 5
\n290 : 0 1 1 2 1 0
\n291 : 0 1 2 0 0 0
\n292 : 0 2 0 0 0 0
\n293 : 1 0 0 0 0 0<\/p>\n

 <\/p>\n

\n

Copyright 2001, Frank Morgan.<\/p>\n","protected":false},"excerpt":{"rendered":"

April 19, 2001   Old Challenge\u00a0(Joe Shipman). Larry King said in his\u00a0USA Today\u00a0column that there are 293 ways to make change for a dollar. Is this correct? (Assume only currently minted denominations.) Answer.\u00a0Yes, if you count a one-dollar coin in change. Raymond Hettinger listed all 293 possibilities, appended at end of column. Michael Caulfield counted […]<\/p>\n","protected":false},"author":2965,"featured_media":0,"parent":3459,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"footnotes":""},"class_list":["post-3566","page","type-page","status-publish","hentry"],"acf":[],"_links":{"self":[{"href":"https:\/\/sites.williams.edu\/Morgan\/wp-json\/wp\/v2\/pages\/3566","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/sites.williams.edu\/Morgan\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/sites.williams.edu\/Morgan\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/sites.williams.edu\/Morgan\/wp-json\/wp\/v2\/users\/2965"}],"replies":[{"embeddable":true,"href":"https:\/\/sites.williams.edu\/Morgan\/wp-json\/wp\/v2\/comments?post=3566"}],"version-history":[{"count":3,"href":"https:\/\/sites.williams.edu\/Morgan\/wp-json\/wp\/v2\/pages\/3566\/revisions"}],"predecessor-version":[{"id":3791,"href":"https:\/\/sites.williams.edu\/Morgan\/wp-json\/wp\/v2\/pages\/3566\/revisions\/3791"}],"up":[{"embeddable":true,"href":"https:\/\/sites.williams.edu\/Morgan\/wp-json\/wp\/v2\/pages\/3459"}],"wp:attachment":[{"href":"https:\/\/sites.williams.edu\/Morgan\/wp-json\/wp\/v2\/media?parent=3566"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}