Mathematik zum Wochenende – Lösung der Zusatzaufgabe

[Rolf B]

Hallo Gunnar,

in meinen ersten Überlegungen hatte ich die Endziffern 2 und 5 einfach rausgelassen, weil sie ja die 0 bilden. Und dann "abgekürzt" zu 9! mit Entfernen der 0. Das habe ich dann allerdings nicht mit diversen 9er Gruppen validiert, sonst wäre mir der Irrtum aufgefallen.

Lets try again.

Ich gucke mir erstmal in den Zahlen von 1-10 die Menge E1 = {1,3,4,6,7,8,9} an. Da ist kein Nullgenerator drin, das Produkt der Endziffern ist 36288, die Endziffer 8 ist dafür richtig.

Der nächste Blick geht auf die Zahlen 1-99, ohne die Zehner. Die Endzifferngruppe E1 ist darin zehnmal enthalten, und die folgenden Produkte bleiben pro Zehnergruppe übrig: 2⋅5, 12⋅15, 22⋅25, 32⋅35, 42⋅45, 52⋅55, 62⋅65, 72⋅75, 82⋅85, 92⋅95

Wenn ich mir diese Produkte anschaue, dann finde ich, dass sie alle auf genau eine Null enden, außer 72⋅75. Das liegt daran, dass eine Zahl, die auf 00 enden soll, zweimal den Primfaktor 5 braucht, also durch 25 teilbar sein muss, wofür nur 22⋅25 und 72⋅75 in Frage kommen. 22⋅25 selbst enthält den Faktor 2 nur einmal, aber beim Aufmultiplizieren kommt der Faktor 2 aus anderen Zahlen hinzu und die 5 generiert eine zusätzliche 0. Diese Teilprodukte lasse ich darum erstmal weg. Die Endziffern der übrigen Produkte sind 10, 80, 20, 90, 60, 30, 70 und 40, das führt zur signifikanten Endziffer 1⋅8⋅2⋅9⋅6⋅3⋅7⋅4=7256, also 6.

Acht hoch Zehn hat wegen der (jetzt aber wirklich) gezeigten 8-4-2-6 Periode der Achterpotenzen die Endziffer 4. Multipliziert mit der 6 von 7256 gibt das 24, das Produkt der Zahlen von 1-99, ohne die durch 10 teilbaren Zahlen, und ohne 22⋅25 und 72⋅75, hat die Endziffer 4.

Nun ein Blick auf die Zahlen 101-199. Hier gelten die gleichen Überlegungen, die Endziffer ist demnach ebenfalls 4.

Für die übrigen 18 Hundertergruppen bis zur 2000 gilt das genauso. Wegen der 4-6 Periode der Viererpotenzen gilt $$4^{20} \equiv 6 \pmod{10}$$.

Nun folgt der Blick auf 22⋅25 und 72⋅75. Je nach Hundertergruppe stecken da unterschiedlich viele Fünfen drin. Hier muss man also aufpassen.

Letztlich muss man jede 5 aus diesen Produkten eliminieren und gegen eine 2 aufrechnen. Solange der Faktor 10 drin ist, ist es einfach, aber wenn die 2 im einen Faktor steckt und die 5 im anderen... Ach pfeif drauf, ich hab da mal was programmiert. OHNE BigInt, natürlich. Das wäre ja gemogelt.

let p = 1;
let borrowed=0;
for (let i=0; i<20; i+=1) {
   let f = (50*i+11) * (20*i+5) * (25*i+18) * (4*i+3);   // Faktor 1000 gleich entfernen
   while (f % 10 == 0) f/=10;                            // Falls noch weitere Zehner drin sind
   while (f % 5 == 0) { f/=5; borrowed++; }
   while (f % 2 == 0) { f/=2; borrowed--; }
   p = (p%10000)*(f%10000);
   console.log(f + " - " + p);
}
console.log("borrowed: " + borrowed);

D.h. wenn ich nicht mehr durch 10 teilen kann, aber durch 5, dann tu ich das, und merke mir, dass ich mir irgendwoher eine 2 borgen muss. Finde ich eine 2, dann teile ich dadurch und zahle auf das "geborgt" Konto wieder ein.

Dumme Sache nur, am Ende bleibt das borrowed-Konto auf 12 stehen. D.h. wir müssen uns noch zwölfmal den Primfaktor 2 irgendwoher beschaffen. Da wir den Bereich 2001-2019 bisher ignoriert haben, ist das eine gute Quelle. 2002→1, 2004→2, 2006→1, 2008→3, 2012→2, 2014→1, 2016→3, 2018→1 - das sind 14, das reicht. Von 2000 und 2010 bleiben wir weg, die haben ihre eigenen 5en im Bauch, die es zu kompensieren gilt. Nach all der Kürzerei und Borgerei gibt das Script oben als letzten aufmultiplizierten Wert 8276419 aus, die Endziffer 9 für all die Mühe. Zusammen mit der Endziffer 6 aus dem vorherigen Schritt ergibt sich nun mit 9⋅6=54 die Endziffer 4 für alle Zahlen von 1-1999, die NICHT auf 0 enden.

Es bleiben 199 Zahlen von 1-1999 übrig. Diese enden auf 0 - sowas störendes, gleich zu $$10^{199}$$ ausklammern. Nun wissen wir von oben, dass 1-99 und 101-199, ohne die 22, 25, 72, 75 Endungen, jeweils zur Endziffer 4 führen. Und für die bösen Endungen haben wir das Script: 2483217, und zwei geborgte Zweien. Die bleiben erstmal offen.

Nun sind immer noch 19 Zahlen zu multiplizieren, die auf 0 enden (die 100er aus der Ursprungsfolge). Daraus klammern wir schnell $$10^{19}$$ aus und lassen den Rest vom Taschenrechner erledigen: 19! = 121645100408832000. Drei Nullen weg, und die 32 ist praktisch, die Zahl geht durch 4 und wir können unsere geborgten Zweien zurückzahlen. Übrig bleibt 30411275102208. Mal gucken ob es bei der 8 bleibt, oder ob noch was zu Borgen ist.

Was bleibt? Die 2000, und nochmal 19! geteilt durch 4096 (die 12 Zweien). Letzteres ergibt 29698510842000, endet also nicht auf 5 und produziert damit keinen neuen Kredit auf dem Zweierkonto.

Zusammenfassung der Endziffern: 4⋅7⋅8⋅2⋅2 = 896 - juhu, es kommt die 6 heraus, und diesmal hoffentlich ohne zu cheaten.

Rolf