Zahlentheorie - Zahlenspielerei

Neue Frage »

osd Auf diesen Beitrag antworten »
Zahlentheorie - Zahlenspielerei
Ein echt überraschendes Ergebnis für ein lustiges Problem:

Gegeben: beliebige Zahl, z.B. in Dezimalschreibweise 62502

Nun darf man zwischen die Ziffern ein oder mehrere + setzen, zum Beispiel
6+250+2 = 258
Und so weiter:
25+8 = 33
Und:
3+3 = 6
(also so lange bis eine Ziffer übrigbleibt).

Behauptung (und dafür scheint es auch einen Beweis zu geben):
Egal wie groß die ursprüngliche Zahl ist, gilt Folgendes:
Nach einer FÜR ALLE MÖGLICHEN Zahlen FIXEN Anzahl von Schritten S bleibt eine Ziffer übrig. Das heißt: egal wie groß die Ausgangszahl ist, wenn man die Pluszeichen geschickt setzt, ist man nach maximal S Schritten fertig.

Einfach ist Folgendes (diesmal Zahl in Binärschreibweise):
11111
Dann setzt man einfach ein Plus zwischen die vorletzte und letzte 1 und bekommt
100000
Dann ein Plus zwischen die 1 und die 0 und man bekommt
1
Für diese speziellen Zahlen (nur 1en in Binärschreibweise) ist man also immer nach zwei Schritten fertig, egal wie groß die Zahl ist.

Doch wie löst man das allgemeine Problem?
bbp Auf diesen Beitrag antworten »
RE: Zahlentheorie - Zahlenspielerei
meine zahl INPUT hat n ziffern
für n>=3 gilt : 9*n<10^(n-1)
(9*n ist die maximale quersumme für eine zahl mit n ziffern. diese quersumme hat mind. eine ziffer weniger als die zahl INPUT, da 10^(n-1) das infimum der zahlen mit n ziffern ist.). d.h. wir können die quersumme der zahl nehmen, bis sie nur noch 2 ziffern hat (unsere quersumme ist ja jetzt kleiner als 10^(3-1)=100). den rest kannst du noch machen (im schlimmsten fall bruteforce, sind ja nur noch endlich fälle).
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »