Frank Morgan’s Math Chat – 293 manieren om wisselgeld te maken voor een dollar

April 19, 2001

Old Challenge (Joe Shipman). Larry King zei in zijn column in USA Today dat er 293 manieren zijn om een dollar terug te geven. Is dit juist? (Ga uit van alleen de huidige coupures.)

Antwoord. Ja, als je een één-dollar muntstuk meetelt als wisselgeld. Raymond Hettinger heeft alle 293 mogelijkheden opgesomd, als bijlage aan het eind van de kolom. Michael Caulfield telde de 292 mogelijkheden anders dan een één-dollar munt als volgt op:

Gezien het feit dat 1 halve dollar wordt gebruikt, zijn er 50 combinaties:
nog een halve dollar (1 manier)
2 kwartjes (1 manier)
1 kwartje met: 2 dubbeltjes (2 manieren), 1 dubbeltje (4), of 0 dubbeltjes (6).
0 kwartjes met: 5 dubbeltjes (1), 4 (3), 3 (5), 2 (7), 1 (9), of 0 (11).

Gezien het feit dat er geen halve dollars worden gebruikt, zijn er 242 combinaties:
4 kwartjes (1 weg)
3 kwartjes met: 2 dubbeltjes (2 manieren), 1 (4), of 0 (6).
2 kwartjes met: 5 dubbeltjes (1), 4 (3), 3 (5), 2 (7), 1 (9), of 0 (11).
1 kwartje met: 7 dubbeltjes (2), 6 (4), 5 (6), 4 (8), 3 (10), 2 (12), 1 (14), 0 (16)
0 kwartjes met: 10 dubbeltjes (1), 9 (3), 8 (5), 7 (7), 6 (9), 5 (11), 4 (13), 3 (15), 2 (17), 1 (19), 0 (21).

Torsten Sillke besprak hoe dergelijke berekeningen met genererende functies kunnen worden uitgevoerd. Zie Herbert’s Wilf’s “Lectures on Integer Partitions” (pagina 10) op http://www.math.upenn.edu/~wilfHet antwoord op ons probleem (293) is de coëfficiënt van x^100 in de reciproke van de volgende:

Al Zimmermann gaf de volgende tabel van het aantal manieren waarop je verschillende valuta-eenheden kunt inwisselen voor kleinere valuta-eenheden:

Zimmermann voegde daaraan toe: Ik heb biljetten van $2 toegestaan. Ik heb geen onderscheid gemaakt tussen $1 munten en $1 biljetten in wisselgeld. Ik heb daarover nagedacht en besloten dat als ik onderscheid zou maken, ik ook onderscheid zou moeten maken tussen de 50 verschillende kwartjes die nu worden uitgegeven. En dat wilde ik echt niet doen.

In navolging van Caulfield en Zimmermann en in weerwil van Larry King, zegt Walter Wright dat een dollarmunt niet kan worden beschouwd als wisselgeld voor een dollarbiljet: Webster’s New World Dictionary definieert wisselgeld als “een aantal munten of biljetten waarvan de totale waarde gelijk is aan een enkele grotere munt of biljet.”

Vraagwaardige wiskunde. Al Zimmermann rapporteert dat: “Ongeveer drie jaar geleden ging ik naar een Citibank ATM in midtown Manhattan om wat geld op te nemen. De machine weigerde mijn verzoek met de volgende boodschap:

Ik kan u geen $130 geven omdat ik alleen biljetten heb in de waarden $50 en $20. Kiest u alstublieft een ander bedrag.”

Natuurlijk is $130 = $50 + 4 x $20.

Lezers worden uitgenodigd meer voorbeelden van twijfelachtige wiskunde in te sturen.

Nieuwe uitdaging. Wat is het grootste positieve getal dat je kunt voorstellen met drie verschillende standaard wiskundige symbolen, zoals 8×9? Het kleinste?

Zend antwoorden, commentaar, en nieuwe vragen per e-mail naar [email protected], om in aanmerking te komen voor Flatland en andere boekprijzen. Winnende antwoorden zullen verschijnen in de volgende Math Chat. Math Chat verschijnt op de eerste en derde donderdag van elke maand. Prof. Morgan’s homepage is op www.williams.edu/Mathematics/fmorgan.

HET MATH CHAT BOEK, inclusief een $1000 Math Chat Book QUEST, vragen en antwoorden, en een lijst van winnaars van de vorige uitdaging, is nu verkrijgbaar bij de MAA (800-331-1622).

Raymond Hettinger’s lijst van de 293 manieren om wisselgeld te maken voor een dollar:

1 : 0 0 0 0 100 (0 dollars, 0 halve dollars, 0 kwartjes, 0 dubbeltjes, 0
nikkels, 100 centen)
2 : 0 0 0 0 1 95
3 : 0 0 0 0 2 90
4 : 0 0 0 0 3 85
5 : 0 0 0 0 4 80
6 : 0 0 0 0 5 75
7 : 0 0 0 0 6 70
8 : 0 0 0 0 7 65
9 : 0 0 0 0 8 60
10 : 0 0 0 0 9 55
11 : 0 0 0 0 10 50
12 : 0 0 0 0 11 45
13 : 0 0 0 0 12 40
14 : 0 0 0 0 13 35
15 : 0 0 0 0 14 30
16 : 0 0 0 0 15 25
17 : 0 0 0 0 16 20
18 : 0 0 0 0 17 15
19 : 0 0 0 0 18 10
20 : 0 0 0 0 19 5
21 : 0 0 0 0 20 0
22 : 0 0 0 1 0 90
23 : 0 0 0 1 1 85
24 : 0 0 0 1 2 80
25 : 0 0 0 1 3 75
26 : 0 0 0 1 4 70
27 : 0 0 0 1 5 65
28 : 0 0 0 1 6 60
29 : 0 0 0 1 7 55
30 : 0 0 0 1 8 50
31 : 0 0 0 1 9 45
32 : 0 0 0 1 10 40
33 : 0 0 0 1 11 35
34 : 0 0 0 1 12 30
35 : 0 0 0 1 13 25
36 : 0 0 0 1 14 20
37 : 0 0 0 1 15 15
38 : 0 0 0 1 16 10
39 : 0 0 0 1 17 5
40 : 0 0 0 1 18 0
41 : 0 0 0 2 0 80
42 : 0 0 0 2 1 75
43 : 0 0 0 2 2 70
44 : 0 0 0 2 3 65
45 : 0 0 0 2 4 60
46 : 0 0 0 2 5 55
47 : 0 0 0 2 6 50
48 : 0 0 0 2 7 45
49 : 0 0 0 2 8 40
50 : 0 0 0 2 9 35
51 : 0 0 0 2 10 30
52 : 0 0 0 2 11 25
53 : 0 0 0 2 12 20
54 : 0 0 0 2 13 15
55 : 0 0 0 2 14 10
56 : 0 0 0 2 15 5
57 : 0 0 0 2 16 0
58 : 0 0 0 3 0 70
59 : 0 0 0 3 1 65
60 : 0 0 0 3 2 60
61 : 0 0 0 3 3 55
62 : 0 0 0 3 4 50
63 : 0 0 0 3 5 45
64 : 0 0 0 3 6 40
65 : 0 0 0 3 7 35
66 : 0 0 0 3 8 30
67 : 0 0 0 3 9 25
68 : 0 0 0 3 10 20
69 : 0 0 0 3 11 15
70 : 0 0 0 3 12 10
71 : 0 0 0 3 13 5
72 : 0 0 0 3 14 0
73 : 0 0 0 4 0 60
74 : 0 0 0 4 1 55
75 : 0 0 0 4 2 50
76 : 0 0 0 4 3 45
77 : 0 0 0 4 4 40
78 : 0 0 0 4 5 35
79 : 0 0 0 4 6 30
80 : 0 0 0 4 7 25
81 : 0 0 0 4 8 20
82 : 0 0 0 4 9 15
83 : 0 0 0 4 10 10
84 : 0 0 0 4 11 5
85 : 0 0 0 4 12 0
86 : 0 0 0 5 0 50
87 : 0 0 0 5 1 45
88 : 0 0 0 5 2 40
89 : 0 0 0 5 3 35
90 : 0 0 0 5 4 30
91 : 0 0 0 5 5 25
92 : 0 0 0 5 6 20
93 : 0 0 0 5 7 15
94 : 0 0 0 5 8 10
95 : 0 0 0 5 9 5
96 : 0 0 0 5 10 0
97 : 0 0 0 6 0 40
98 : 0 0 0 6 1 35
99 : 0 0 0 6 2 30
100 : 0 0 0 6 3 25
101 : 0 0 0 6 4 20
102 : 0 0 0 6 5 15
103 : 0 0 0 6 6 10
104 : 0 0 0 6 7 5
105 : 0 0 0 6 8 0
106 : 0 0 0 7 0 30
107 : 0 0 0 7 1 25
108 : 0 0 0 7 2 20
109 : 0 0 0 7 3 15
110 : 0 0 0 7 4 10
111 : 0 0 0 7 5 5
112 : 0 0 0 7 6 0
113 : 0 0 0 8 0 20
114 : 0 0 0 8 1 15
115 : 0 0 0 8 2 10
116 : 0 0 0 8 3 5
117 : 0 0 0 8 4 0
118 : 0 0 0 9 0 10
119 : 0 0 0 9 1 5
120 : 0 0 0 9 2 0
121 : 0 0 0 10 0 0
122 : 0 0 1 0 0 75
123 : 0 0 1 0 1 70
124 : 0 0 1 0 2 65
125 : 0 0 1 0 3 60
126 : 0 0 1 0 4 55
127 : 0 0 1 0 5 50
128 : 0 0 1 0 6 45
129 : 0 0 1 0 7 40
130 : 0 0 1 0 8 35
131 : 0 0 1 0 9 30
132 : 0 0 1 0 10 25
133 : 0 0 1 0 11 20
134 : 0 0 1 0 12 15
135 : 0 0 1 0 13 10
136 : 0 0 1 0 14 5
137 : 0 0 1 0 15 0
138 : 0 0 1 1 0 65
139 : 0 0 1 1 1 60
140 : 0 0 1 1 2 55
141 : 0 0 1 1 3 50
142 : 0 0 1 1 4 45
143 : 0 0 1 1 5 40
144 : 0 0 1 1 6 35
145 : 0 0 1 1 7 30
146 : 0 0 1 1 8 25
147 : 0 0 1 1 9 20
148 : 0 0 1 1 10 15
149 : 0 0 1 1 11 10
150 : 0 0 1 1 12 5
151 : 0 0 1 1 13 0
152 : 0 0 1 2 0 55
153 : 0 0 1 2 1 50
154 : 0 0 1 2 2 45
155 : 0 0 1 2 3 40
156 : 0 0 1 2 4 35
157 : 0 0 1 2 5 30
158 : 0 0 1 2 6 25
159 : 0 0 1 2 7 20
160 : 0 0 1 2 8 15
161 : 0 0 1 2 9 10
162 : 0 0 1 2 10 5
163 : 0 0 1 2 11 0
164 : 0 0 1 3 0 45
165 : 0 0 1 3 1 40
166 : 0 0 1 3 2 35
167 : 0 0 1 3 3 30
168 : 0 0 1 3 4 25
169 : 0 0 1 3 5 20
170 : 0 0 1 3 6 15
171 : 0 0 1 3 7 10
172 : 0 0 1 3 8 5
173 : 0 0 1 3 9 0
174 : 0 0 1 4 0 35
175 : 0 0 1 4 1 30
176 : 0 0 1 4 2 25
177 : 0 0 1 4 3 20
178 : 0 0 1 4 4 15
179 : 0 0 1 4 5 10
180 : 0 0 1 4 6 5
181 : 0 0 1 4 7 0
182 : 0 0 1 5 0 25
183 : 0 0 1 5 1 20
184 : 0 0 1 5 2 15
185 : 0 0 1 5 3 10
186 : 0 0 1 5 4 5
187 : 0 0 1 5 5 0
188 : 0 0 1 6 0 15
189 : 0 0 1 6 1 10
190 : 0 0 1 6 2 5
191 : 0 0 1 6 3 0
192 : 0 0 1 7 0 5
193 : 0 0 1 7 1 0
194 : 0 0 2 0 0 50
195 : 0 0 2 0 1 45
196 : 0 0 2 0 2 40
197 : 0 0 2 0 3 35
198 : 0 0 2 0 4 30
199 : 0 0 2 0 5 25
200 : 0 0 2 0 6 20
201 : 0 0 2 0 7 15
202 : 0 0 2 0 8 10
203 : 0 0 2 0 9 5
204 : 0 0 2 0 10 0
205 : 0 0 2 1 0 40
206 : 0 0 2 1 1 35
207 : 0 0 2 1 2 30
208 : 0 0 2 1 3 25
209 : 0 0 2 1 4 20
210 : 0 0 2 1 5 15
211 : 0 0 2 1 6 10
212 : 0 0 2 1 7 5
213 : 0 0 2 1 8 0
214 : 0 0 2 2 0 30
215 : 0 0 2 2 1 25
216 : 0 0 2 2 2 20
217 : 0 0 2 2 3 15
218 : 0 0 2 2 4 10
219 : 0 0 2 2 5 5
220 : 0 0 2 2 6 0
221 : 0 0 2 3 0 20
222 : 0 0 2 3 1 15
223 : 0 0 2 3 2 10
224 : 0 0 2 3 3 5
225 : 0 0 2 3 4 0
226 : 0 0 2 4 0 10
227 : 0 0 2 4 1 5
228 : 0 0 2 4 2 0
229 : 0 0 2 5 0 0
230 : 0 0 3 0 0 25
231 : 0 0 3 0 1 20
232 : 0 0 3 0 2 15
233 : 0 0 3 0 3 10
234 : 0 0 3 0 4 5
235 : 0 0 3 0 5 0
236 : 0 0 3 1 0 15
237 : 0 0 3 1 1 10
238 : 0 0 3 1 2 5
239 : 0 0 3 1 3 0
240 : 0 0 3 2 0 5
241 : 0 0 3 2 1 0
242 : 0 0 4 0 0 0
243 : 0 1 0 0 0 50
244 : 0 1 0 0 1 45
245 : 0 1 0 0 2 40
246 : 0 1 0 0 3 35
247 : 0 1 0 0 4 30
248 : 0 1 0 0 5 25
249 : 0 1 0 0 6 20
250 : 0 1 0 0 7 15
251 : 0 1 0 0 8 10
252 : 0 1 0 0 9 5
253 : 0 1 0 0 10 0
254 : 0 1 0 1 0 40
255 : 0 1 0 1 1 35
256 : 0 1 0 1 2 30
257 : 0 1 0 1 3 25
258 : 0 1 0 1 4 20
259 : 0 1 0 1 5 15
260 : 0 1 0 1 6 10
261 : 0 1 0 1 7 5
262 : 0 1 0 1 8 0
263 : 0 1 0 2 0 30
264 : 0 1 0 2 1 25
265 : 0 1 0 2 2 20
266 : 0 1 0 2 3 15
267 : 0 1 0 2 4 10
268 : 0 1 0 2 5 5
269 : 0 1 0 2 6 0
270 : 0 1 0 3 0 20
271 : 0 1 0 3 1 15
272 : 0 1 0 3 2 10
273 : 0 1 0 3 3 5
274 : 0 1 0 3 4 0
275 : 0 1 0 4 0 10
276 : 0 1 0 4 1 5
277 : 0 1 0 4 2 0
278 : 0 1 0 5 0 0
279 : 0 1 1 0 0 25
280 : 0 1 1 0 1 20
281 : 0 1 1 0 2 15
282 : 0 1 1 0 3 10
283 : 0 1 1 0 4 5
284 : 0 1 1 0 5 0
285 : 0 1 1 1 0 15
286 : 0 1 1 1 1 10
287 : 0 1 1 1 2 5
288 : 0 1 1 1 3 0
289 : 0 1 1 2 0 5
290 : 0 1 1 2 1 0
291 : 0 1 2 0 0 0
292 : 0 2 0 0 0 0
293 : 1 0 0 0 0 0