Kaprekar

Neue Frage »

Leopold Auf diesen Beitrag antworten »
Kaprekar
Hier eine kleine Spielerei. Nichts Besonderes. Mancher mag es kennen. Gerne mache ich das, wenn ich mit Fünftkläßlern das schriftliche Subtrahieren übe.

Man beginnt mit einer vierstelligen natürlichen Zahl aus nicht lauter gleichen Ziffern und bildet daraus durch Vertauschen der Ziffern die größtmögliche und die kleinstmögliche Zahl. Diese beiden subtrahiert man (und ergänzt gegebenenfalls führende Nullen, um formal wieder Vierstelligkeit zu erhalten). Mit der Differenz wiederholt man das Verfahren. Und so weiter und so fort.
Huggy Auf diesen Beitrag antworten »
RE: Kaprekar
Ich hasse dieses Problem!!!

In meiner Schulzeit bin ich darauf gestoßen. Ein paar Versuche lassen einen vermuten, dass nach ein paar Iterationen immer die Differenz auftaucht, die sich dann wiederholt. Das sollte bewiesen werden. Aber es gab keine Lösung zum Nachschlagen. Wie beweist man das? Das Problem ist "sehr endlich". Aber unsere damaligen Arbeitsgeräte waren Tabellen und der Rechenschieber. Da war nichts mit "brute force".

Man muss natürlich nicht alle vierstelligen Zahlen mit nicht lauter gleichen Ziffern durchprobieren. Es genügt, die Zahlen zu testen mit Ziffern und nicht alle gleich. Auch die muss man nicht alle durchprobieren, denn wenn man eine testet, sind die der Größe nach geordneten Ziffernfolgen der jeweils auftretenden Differenzen bei der Iteration gleich miterledigt. Aber ohne Rechnerhilfe mutet man sich das nicht zu.

Als man das mit Rechnerhilfe beweisen konnte, ist mir irgendwann ein Muster aufgefallen. Es sei mit und . Dann zerfallen die Differenzen in in zwei Klassen:





Hat man das Muster erkannt, ist es kein Problem, das auch arithmetisch zu beweisen.

Zahlen der Klasse gibt es und solche der Klasse . Es genügt also, diese 30 Zahlen zu testen. Doch man kann es drehen und wenden wie man will, dass ist noch immer "brute force", wenn auch intelligentes brute force.

Weiter bin ich nie gekommen. Und jetzt wird mir Leopold oder jemand anders eine elegante mathematische Beweisführung präsentieren. Deshalb:

Ich hasse dieses Problem!!!
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Huggy
Es genügt also, diese 30 Zahlen zu testen. Doch man kann es drehen und wenden wie man will, dass ist noch immer "brute force", wenn auch intelligentes brute force.

Wenn man es auf so wenig Fälle schon runtergebracht hat, dann ist das doch bereits ein tolles Ergebnis, auch wenn die Lösung vielleicht nicht dem Ideal eines schönen Beweises genügt. Augenzwinkern

Und es muss wohl auch eher eine Hassliebe sein. Big Laugh
Huggy Auf diesen Beitrag antworten »

Zitat:
Original von HAL 9000
Und es muss wohl auch eher eine Hassliebe sein. Big Laugh

Das kann man so sagen. Ich liebe mathematische Probleme eingeschlossen diejenigen, die ich hasse.
HAL 9000 Auf diesen Beitrag antworten »

Hab gerade mal bei Wiki nachgeschaut. Da hat aber einer schön gemalt:

https://upload.wikimedia.org/wikipedia/c...owGraph6174.svg
Leopold Auf diesen Beitrag antworten »
RE: Kaprekar
Zitat:
Original von Huggy
Und jetzt wird mir Leopold oder jemand anders eine elegante mathematische Beweisführung präsentieren.


Schön wär's. Ich kenne es auch nur so, daß man zu Anfang die möglichen Pfade einschränkt, weiterverfolgt und schließlich durch Nachrechnen feststellt, daß alle in die Kaprekar-Zahl 6174 einmünden.

Da man eine Rekursion hat, die nur auf den unmittelbaren Vorgänger zugreift und auf einer endlichen Menge operiert, muß sich bei beliebigem Start eine Periode ergeben. Daß aber alle Pfade in dieselbe Periode münden und diese auch noch die Länge 1 hat, ist schon überraschend. Wenn man das Ganze mit einer anderen Stellenzahl, zum Beispiel fünf Stellen, durchführt, ist das durchaus nicht so. Und die spezielle Situation bei vier Stellen wäre dann sozusagen nur "Zufall".
 
 
Neue Frage »
Antworten »



Verwandte Themen