---

Lösung der 5.    vom 12.03.2001

---

Vorbemerkung von  Peter Becker

Es gibt 67001 Möglichkeiten - 

Wenn man die alle von Hand ausprobieren würde, und für jeden Fall 5 Sekunden veranschlagt, bräuchte man 93 Stunden, bei einer täglichen Konzentrationsfähigkeit von 10 Stunden also 10 Tage. Das geht gerade noch innerhalb der Einsendefrist. 
Für eine Probe reichts allerdings nicht mehr.
(Und das Geld reicht auch nicht zum Bezahlen des Psychiaters.)

mit ein wenig Überlegung kann der Aufwand aber reduziert werden
LuckyAnnette löste die Aufgaben auf diese Art:

Es gibt insgesamt 67001 Möglichkeiten, die 2000 DM mit 2, 3 und 5-Markstücken zu bezahlen.

Mein Gedankenansatz war es, die Gesetzmäßigkeiten rauszufinden, mit denen die  Anzahl der Möglichkeiten sinken, wenn immer mehr 5 DM Stücke verwendet werden.

1) kein 5-Mark Stück, also 2000 DM mit 2 u./o. 3 DM- Stücken darstellen
* da 2000 eine gerade Zahl ist, können nur gerade Anzahl an 3  DM-Stücken  verwendet werden und zwar genau 0 bis zu 666 Stück ( 666*3=1998).
Der Restbetrag wird dann jeweils mit 2 DM- Stücken bezahlt.
Möglichkeiten also ohne 5 DM-Stücke : 334

2) ein 5-Mark-Stück, Restbetrag 1995
* da ungerade Zahl, mindestens 1 bis maximal 665 (665*3= 1995) 3  DM-Stücke
Möglichkeíten also :333

3) zwei 5-Mark-Stücke, Rest 1990
* gerade, 0 - 662 3-DM-Stücke, 
332 Möglichkeiten

4) drei 5er , Rest 1985
* ungerade, mind. 1 bis maximal 661 3er ( 1983), 
331 Möglichkeiten

5) vier 5er : 1980, 0-660 3er, 
331 Möglichkeiten

6) fünf 5er :1975, 1-657 3er, 
329 Möglichkeiten

7) sechs 5er :1970 DM, 0-656 3er, 
329 Möglichkeiten

usw.....

400) dreihundertneunundneunzig 5-er: 1995  1 3er,
1 Möglichkeit

401) vierhundert 5er : 2000 DM  und 0 3er
 1 Möglichkeit

Dabei stellte sich schnell das Muster heraus, 
das sich alle 30 DM-Schritte wiederholt, da 30 das kleinste gemeinsame Vielfache von 2, 3 und 5 ist.

Zum Schluss brauchte ich nur noch die errechneten Möglichkeiten
alle addieren um auf die 67001 Möglichkeiten zu kommen.

Wer es genau wissen will:

  334 + 333 + 332 + 331 + 331 + 329 + 329 + 328 + 327 + 326 
+ 326 + 324 + 324 + 323 + 322 + 321 + 321 + 319 + 319 + 318 
+ 317 + 316 + 316 + 314 + 314 + 313 + 312 + 311 + 311 + 309 
+ 309 + 308 + 307 + 306 + 306 + 304 + 304 + 303 + 302 + 301 
+ 301 + 299 + 299 + 298 + 297 + 296 + 296 + 294 + 294 + 293 
+ 292 + 291 + 291 + 289 + 289 + 288 + 287 + 286 + 286 + 284 
+ 284 + 283 + 282 + 281 + 281 + 279 + 279 + 278 + 277 + 276 
+ 276 + 274 + 274 + 273 + 272 + 271 + 271 + 269 + 269 + 268 
+ 267 + 266 + 266 + 264 + 264 + 263 + 262 + 261 + 261 + 259 
+ 259 + 258 + 257 + 256 + 256 + 254 + 254 + 253 + 252 + 251 
+ 251 + 249 + 249 + 248 + 247 + 246 + 246 + 244 + 244 + 243 
+ 242 + 241 + 241 + 239 + 239 + 238 + 237 + 236 + 236 + 234 
+ 234 + 233 + 232 + 231 + 231 + 229 + 229 + 228 + 227 + 226 
+ 226 + 224 + 224 + 223 + 222 + 221 + 221 + 219 + 219 + 218 
+ 217 + 216 + 216 + 214 + 214 + 213 + 212 + 211 + 211 + 209 
+ 209 + 208 + 207 + 206 + 206 + 204 + 204 + 203 + 202 + 201 
+ 201 + 199 + 199 + 198 + 297 + 196 + 196 + 194 + 194 + 193 
+ 192 + 191 + 191 + 189 + 189 + 188 + 187 + 186 + 186 + 184 
+ 184 + 183 + 182 + 181 + 181 + 179 + 179 + 178 + 177 + 176 
+ 176 + 174 + 174 + 173 + 172 + 171 + 171 + 169 + 169 + 168 
+ 167 + 166 + 166 + 164 + 164 + 163 + 162 + 161 + 161 + 159 
+ 159 + 158 + 157 + 156 + 156 + 154 + 154 + 153 + 152 + 151 
+ 151 + 149 + 149 + 148 + 147 + 146 + 146 + 144 + 144 + 143 
+ 142 + 141 + 141 + 139 + 139 + 138 + 137 + 136 + 136 + 134 
+ 134 + 133 + 132 + 131 + 131 + 129 + 129 + 128 + 127 + 126 
+ 126 + 124 + 124 + 123 + 122 + 121 + 121 + 119 + 119 + 118 
+ 117 + 116 + 116 + 114 + 114 + 113 + 112 + 111 + 111 + 109 
+ 109 + 108 + 107 + 106 + 106 + 104 + 104 + 103 + 102 + 101 
+ 101 +  99 +  99 +  98 +  97 +  96 +  96 +  94 +  94 +  93 
+  92 +  91 +  91 +  89 +  89 +  88 +  87 +  86 +  86 +  84 
+  84 +  83 +  82 +  81 +  81 +  79 +  79 +  78 +  77 +  76 
+  76 +  74 +  74 +  73 +  72 +  71 +  71 +  69 +  69 +  68 
+  67 +  66 +  66 +  64 +  64 +  63 +  62 +  61 +  61 +  59 
+  59 +  58 +  57 +  56 +  56 +  54 +  54 +  53 +  52 +  51 
+  51 +  49 +  49 +  48 +  47 +  46 +  46 +  44 +  44 +  43 
+  42 +  41 +  41 +  39 +  39 +  38 +  37 +  36 +  36 +  34 
+  34 +  33 +  32 +  31 +  31 +  29 +  29 +  28 +  27 +  26 
+  26 +  24 +  24 +  23 +  22 +  21 +  21 +  19 +  19 +  18 
+  17 +  16 +  16 +  14 +  14 +  13 +  12 +  11 +  11 +   9 
+   9 +   8 +   7 +   6 +   6 +   4 +   4 +   3 +   2 +   1 
+   1 = 67001

Horst Reblitz: hat durch einige Überlegungen die Schreibarbeit reduzieren können:

Ich hab mir keine großen Gedanken über eine mögliche Universalformel gemacht, sondern mir ein paar Beispiele zu den 7 Kombinationsmöglichkeiten von den 3 verschiedenen Münzen überlegt und daraus mit einfachen Summenformeln die Anzahl berechnet:

Nur 5er: 1 
Nur 2er: 1
Nur 3er: 0
5er und 2er: 199 [10er Schritte: 2000/10-1]
5er und 3er: 133 [15er Schritte: 2000/15]
2er und 3er: 333 [6er Schritte: 2000/6]
2er und 3er und 5er: 26733+39601 
[aus der 2er und 3er mit Ersetzung 2+3=5: 
Summe(0,3,6..399) + Summe(1,3,5..397)]

ergibt zusammen 67001 Möglichkeiten.

Oliver Gronau leitet eine Formel her:

Im folgenden wird die Schreibweise 

( Anzahl 2 DM / Anzahl 3 DM / Anzahl 5 DM ) verwendet.


Um auf die Zahl zu kommen konstruiert man alle Möglichkeiten wie folgt:

Zuerst legt man die 2000 nur mit 2 DM- und 3 DM-Stücken.
Man beginnt mit 1000 x 2 DM   und  0 x 3 DM. (1000 / 0 / 0)
Dann nimmt man immer 6 DM von den 2- DM-Stücken weg 
und legt 6 DM in 3-DM-Stücken dazu.

( 1000 /  0  / 0 )
(  997 /  2  / 0 )
(  994 /  4  / 0 )
   .
   .
   .
(   1  / 666 / 0 )

oder allgemein :
(wenn "n" die Anzahl angibt wie viel Paare 3 DM-Stücke vorhanden sind)

( 1000 - 3 * n  /  2 * n  /  0 ) mit n = 0 .. 333


Nun kann man aus jedem dieser Tupel alle machbaren bilden, indem man immer ein 2 DM-Stück und ein 3-DM Stück gleichzeitig wegnimmt, und dafür ein 5 DM-Stück dazulegt.

Die entstehenden Tupel sind alle verschieden, da die Ausgangstupel alle verschieden sind, und die Differenz zwischen 2- und 3-DM-Stücken konstant bleibt.
z.B. werden aus ( 997 / 2 / 0 ) nacheinander 
( 996 / 1 / 1 ) und ( 995 / 0 / 2 ).

Aus ( 1000 / 0 / 0 ) können 0 weitere Tupel erzeugt werden --> Insgesamt: 1

Aus (  997 / 2 / 0 ) können 2 weitere Tupel erzeugt werden --> Insgesamt: 3

   .
   .
   .
Aus ( 1  / 666 / 0 ) kann 1 weiteres Tupel erzeugt werden ---> Insgesamt: 2


Oder allgemein:
Aus ( 1000 - 3 * n   /   2 * n   /   0 ) 
können zusätzlich 
min( 1000-3*n ; 2*n ) Tupel erzeugt werden

Insgesamt:  
min( 1000 - 3 * n ; 2 * n ) + 1


Bis  n = 200 ist der Term 2 * n kleiner-gleich 1000 - 3 * n
über n = 200 d.h. bis n = 333 ist 1000 - 3 * n    kleiner

Daraus ergibt sich folgende Formel:


Diese kann sogar schriftlich vereinfacht werden, aber das Endresultat ist in jedem Fall: 

X = 67001

Lösung und Script von Jörg Wiegels

Die Anzahl der Möglichkeiten a(n), auf wie viele verschiedene Weisen eine Zahl n (Betrag) als Summe bestimmter anderer Zahlen (Münzen) dargestellt werden kann, lässt ich rekursiv ermitteln.

Es seien M die Menge der verschiedenen erlaubten Münzwerte sowie k und m mögliche Elemente daraus.
Wenn man von einer Summendarstellung für n den Summanden mit dem höchsten Wert m weg lässt, erhält man eine Darstellung für n-m mit höchstem Wert nicht größer als m.
Die Anzahl der Möglichkeiten a(n,m) für m<n, bei denen der höchste Wert nicht größer als m ist, ist also die Summe aller Anzahlen a(n-k,k) mit k<=m, wobei im Falle k=n als Summand 1 bzw. 0 zu addieren ist, je nachdem, ob es eine Münze mit dem Wert k gibt oder nicht.

Bei n=2000 und M={2,3,5} erhält man so das Ergebnis a(2000) = a(2000,5) = 67001.
Im folgenden Formular berechnet ein JavaScript-Programm die Anzahlen für alle höchstens 4-stelligen Zahlen nach diesem Algorithmus:

Für die Werte der Folge a(n) gibt es eine Näherungsformel:
a(n) ~ n2/60+n/6+1

Antwort

Es gibt 67001 Möglichkeiten, 2000 DM mit 2-, 3- und 5-DM-Stücken zu bezahlen.

 

 [ aktuelle Aufgabe ]  [ zur 5. zurück ]  [ zur Hall of FAME ]    

?     ?        ?    ?