Frank Morgan’s Math Chat – 293 Ways to Make Change for a Dollar

April 19, 2001

Old Challenge (Joe Shipman). Larry King powiedział w swojej kolumnie w USA Today, że są 293 sposoby na zrobienie reszty za dolara. Czy to prawda? (Przyjmijmy, że tylko obecnie bite nominały.)

Odpowiedź. Tak, jeśli liczyć monetę jednodolarową w reszcie. Raymond Hettinger wyliczył wszystkie 293 możliwości, załączone na końcu kolumny. Michael Caulfield podliczył 292 możliwości inne niż moneta jednodolarowa w następujący sposób:

Przy założeniu, że 1 półdolarówka zostanie użyta, istnieje 50 kombinacji:
kolejne pół dolara (1 sposób)
2 ćwiartki (1 sposób)
1 ćwiartka z: 2 dziesięciocentówkami (2 sposoby), 1 dziesięciocentówką (4), lub 0 dziesięciocentówkami (6).
0 ćwiartek z: 5 dziesięciocentówkami (1), 4 (3), 3 (5), 2 (7), 1 (9), lub 0 (11).

Przy założeniu, że żadne półdolarówki nie będą używane, istnieją 242 kombinacje:
4 ćwiartki (1 sposób)
3 ćwiartki z: 2 dziesięciocentówkami (2 sposoby), 1 (4), lub 0 (6).
2 ćwiartki z: 5 dziesięciocentówek (1), 4 (3), 3 (5), 2 (7), 1 (9), lub 0 (11).
1 ćwiartka z: 7 dziesięciocentówek (2), 6 (4), 5 (6), 4 (8), 3 (10), 2 (12), 1 (14), 0 (16)
0 ćwiartek z: 10 dziesięciocentówek (1), 9 (3), 8 (5), 7 (7), 6 (9), 5 (11), 4 (13), 3 (15), 2 (17), 1 (19), 0 (21).

Torsten Sillke omówił, jak takie obliczenia można wykonać za pomocą funkcji generujących. Zobacz Herbert’s Wilf’s „Lectures on Integer Partitions” (strona 10) pod adresem http://www.math.upenn.edu/~wilf Odpowiedzią na nasz problem (293) jest współczynnik x^100 w odwrotności następującej zależności:

Al Zimmermann dostarczył następującą tabelę liczb sposobów, na jakie można wymienić różne jednostki waluty na mniejsze jednostki waluty:

Zimmermann dodał: Dopuściłem banknoty 2 dolarowe. Nie rozróżniałem monet i banknotów $1 w reszcie. Zastanawiałem się nad tym i zdecydowałem, że jeśli robię rozróżnienie, to powinienem również rozróżnić 50 różnych ćwierćdolarówek, które są obecnie emitowane. A ja naprawdę nie chciałem tego robić.

Podążając za Caulfieldem i Zimmermannem oraz polemizując z Larrym Kingiem, Walter Wright twierdzi, że moneta dolarowa nie może być uznana za zmianę dla banknotu dolarowego: Webster’s New World Dictionary definiuje zmianę jako „liczbę monet lub banknotów, których łączna wartość jest równa pojedynczej większej monecie lub banknotowi.”

Kwestionowana matematyka. Al Zimmermann donosi, że: „Jakieś trzy lata temu poszedłem do bankomatu Citibanku w centrum Manhattanu, aby wypłacić trochę gotówki. Maszyna odrzuciła moją prośbę z następującą wiadomością:

Nie mogę dać panu 130 dolarów, ponieważ mam tylko banknoty w nominałach 50 i 20 dolarów. Proszę wybrać inną kwotę.”

Oczywiście $130 = $50 + 4 x $20.

Czytelników zapraszamy do nadsyłania kolejnych przykładów wątpliwej matematyki.

Nowe wyzwanie. Jaka jest największa liczba dodatnia, którą można przedstawić za pomocą trzech różnych standardowych symboli matematycznych, takich jak 8×9? Najmniejsza?

Przesyłaj odpowiedzi, komentarze i nowe pytania pocztą elektroniczną na adres [email protected], aby kwalifikować się do Flatlandii i innych nagród książkowych. Zwycięskie odpowiedzi pojawią się w następnym Math Chat. Math Chat pojawia się w pierwszy i trzeci czwartek każdego miesiąca. Strona domowa prof. Morgana jest pod adresem www.williams.edu/Mathematics/fmorgan.

THE MATH CHAT BOOK, w tym $ 1000 Math Chat Book QUEST, pytania i odpowiedzi, a lista przeszłych zwycięzców wyzwanie, jest teraz dostępny z MAA (800-331-1622).

Lista Raymonda Hettingera z 293 sposobów robienia reszty za dolara:

1 : 0 0 0 0 0 100 (0 dolarów, 0 półdolarówek, 0 ćwiartek, 0 dziesięciocentówek, 0
nicków, 100 groszy)
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