Hallo folgender Sachverhalt ist gegeben, vll. fällt euch was dazu ein, das mir helfen könnte: gegeben ist eine beliebige natürliche Zahl a (größer 1) und eine natürliche Zahl b (größer 1): Man erhält die Zahl c, indem man die Reihenfolge der Ziffern von a umdreht. (also wird aus a=123456 c=654321) 1. Berechne c/b 2. Wenn c/b eine natürliche Zahl dann: Ende; wenn c/b keine natürliche Zahl, dann: multipliziere a mit 2 und bestimme c neu gehe zu 1. Beweise, dass es sich nicht um eine Endlosschleife handelt (d.h. irgendwann ist der Quotient c/b eine natürliche Zahl). Frank
Ist keine endlosschleife. Beweis: Sei A = 309 Sei B = 3 Es folgt: C = 903 und 903 geteilt durch 3 ist eine natürliche Zahl, nämlich 301. Das gilt selbstverständlich nicht für jede beliebige Zahlenkombination A, B: Sei C eine Primzahl, zB. 17, also abgeleitet von A = 71 Dann gehts schonmal nicht
A und B sind natürlich zwei belibige natürliche Zahlen, die aber bestimmt sind. Das ganze muss also für alle möglichen A und B stimmen. Du hast aber recht, es stimmt nicht immer. Was ist mit folgender Anpassung? Man multipliziert A nicht immer mit 2, sondern mit irgendeiner Zahl, so wie man möchte. Also: gegeben ist eine beliebige natürliche Zahl a (größer 1) und eine natürliche Zahl b (größer 1): Man erhält die Zahl c, indem man die Reihenfolge der Ziffern von a umdreht. (also wird aus a=123456 c=654321) 1. Berechne c/b 2. Wenn c/b eine natürliche Zahl dann: Ende; wenn c/b keine natürliche Zahl, dann: multipliziere a mit irgendeiner beliebigen natürlichen Zahl und bestimme c neu gehe zu 1. Beweise, dass es sich nicht um eine Endlosschleife handelt (d.h. irgendwann ist der Quotient c/b eine natürliche Zahl). Frank
> A und B sind natürlich zwei belibige > natürliche Zahlen, die aber bestimmt sind. Entweder sie sind beliebig oder sie sind bestimmt. > Das ganze muss also für alle möglichen A und B stimmen. Tut es nicht, wie ich oben demonstriert habe. Das funktioniert übrigens nicht nur wenn A -> C eine Primzahl ist. > Was ist mit folgender Anpassung? > Man multipliziert A nicht immer mit 2, sondern mit > irgendeiner Zahl, so wie man möchte. nicht immer? wurde sie denn vorher mit 2 multipliziert? Das stand in deinem originalbeitrag nicht Generell kann man die Umwandlung A -> C ignorieren und gleich fragen "für welche natürlichen Zahlen (größer 1) gilt C/B = natürliche Zahl?" Nachzulesen in jedem Grundkurs Mathe - Buch Achja mir fällt noch ein: C ist nicht in jedem Falle > 1 für die Zahl A = 10 ergibt sich genau C = 1 Das tut aber nichts zur Sache, denn 1 / (zahl größer 1) ist nie natürlich.
Witzige Fragestellung, wie kommt man darauf? Der Beweis von Sumynona ist keiner ;) Was heißt bei der modifizierten Variante "beliebige natürliche zahl", mit der man a multiplizierten soll? Zufallszahl? Dann wirds schwierig... Ansonsten fällt mir gerade keine mathematische Beschreibung zur Umkehrung der Ziffern ein, deswegen finde ich auch keinen Beweis.
Teilbarkeit: c/b nat. <=> b | c <=> Ex. q nat.: qb=c Parität: c gerade <=> Ex. d nat.: 2d = c c ungerade <=> Ex. d nat.: 2d+1 = c c ungerade => 2c gerade und von der Form 4d+2 = c
Wenn man geschickt multiplizieren darf statt mit immer nur mit Zwei und die Ziffernumkehr ersteinmal außer Acht lässt, so multipliziert man einfach mit b und das Ergebnis wird dann von b geteilt. Nur wie bekommt man diesen "geschickten" Faktor durch die Umkehrung der Reihenfolge der Ziffern geschleust? Die Ziffernumkehrung ist ja offensichtlich nicht mit der Multiplikation verträglich...
Das geht jetzt schon richtig tief in die Zahlentheorie. Bedenke bitte auch dass das Dezimalsystem ziemlich unkompatibel zur Natur ist... Prinzipiell würd ich sagen, man kann nicht voraussagen, ob eine Zahl C durch B teilbar ist, wenn sie aus (A*X) berechnet wird, die Aussage stellt aber eher ne These als einen Beweis dar ;-)
Ist zwar schon eine Weile her, aber ich versuche es mal: Im Grunde sucht man nur ein gemeinsames Vielfaches von a und b. Und das existiert zu allen natürlichen Zahlen. Fertig. (Das Vertauschen der Ziffernreihenfolge nennt sich Permutation. Die tut aber nichts zur Sache, da es eine bijektive Abbildung ist. In der Aufgabenstellung trägt sie nur zur Verwirrung des Kandidaten bei, mehr nicht.)
Nachtrag: Es muss ja nicht unbedingt das kleinste gemeinsame Vielfache sein. Der Rest tut es auch, denn es gibt unendlich viele davon...
Bobby wrote: > (Das Vertauschen der Ziffernreihenfolge nennt sich Permutation. > Die tut aber nichts zur Sache, da es eine bijektive Abbildung ist. > In der Aufgabenstellung trägt sie nur zur Verwirrung des Kandidaten bei, > mehr nicht.) Da bin ich nicht ganz einverstanden. Die Fragestellung würde ich nämlich so aufffassen. Sei X eine Primzahl und n beliebig aus N Ist dann Permutation( n * Permutation(X) ) ebenfalls eine Primzahl?
Dass es zu zwei natürlichen Zahlen unendlich viele Vielfache gibt streitest Du aber nicht ab. Und irgendwann findet der Algorithmus die passende Zahl. Das hat mit Prim garnichts zu tun.
Zur ursprünglichen Fragestellung (mit konstantem Faktor 2):
Es gibt Zahlenkombinationen, für die die Schleife abbricht, bspw. a=2
und b=2, und solche, für die sie nicht abbricht, bspw. a=2, b=3.
Ein Beweis, dass die Schleife immer abbricht oder immer endlos ist, kann
also nicht erbracht werden.
Die Schleife ist mindestens dann endlos, wenn
10|b (1)
oder
3|b und nicht 3|a (2)
oder
11|b und nicht 11|a (3)
Beweis:
zu (1): das umgedrehte a kann nie mit einer 0 enden.
zu (2): Der Dreierrest r3 von a ändert sich durch Umdrehen nicht.
zu (3): Der Elferrest r11 von a bleibt beim Umdrehen entweder gleich
(ungerade Stellenzahl) oder wird zu 11-r11 (gerade Stellenzahl).
c ist also nur dann durch 11 teilbar, wenn auch a es ist.
Vermutung: Alle anderen Fälle führen zum Schleifenabbruch. Der Beweis
ist aber sicher nicht ganz leicht ;-)
Vage Begründung: Nur bei der Division durch 3, 10 und 11 stehen die
Reste von a und c in einer einfachen Beziehung zueinander. Für alle
anderen Zahlen ist die Beziehung so kompliziert, der Divisionsrest
irgendwann einmal jeden Wert in [0,b-1] annehmen wird (also auch 0),
wenn man die Schleife nur lange genug laufen lässt. Ein Beweis ist das
natürlich nicht.
Für manche Zahlenkombinationen läuft die Schleife erstaunlioch oft
durch, bis sie abbricht. So wird bspw. für a=2 und b=865 die Schleife
11709mal durchlaufen, bis das dabei enstehende 3525stellige c endlich
durch b teilbar ist.
Bobby wrote: > Dass es zu zwei natürlichen Zahlen unendlich viele Vielfache gibt > streitest Du aber nicht ab. Und irgendwann findet der Algorithmus die > passende Zahl. Das hat mit Prim garnichts zu tun. Kannst du das beweisen? Genau darum geht es ja: Kannst du einen Beweis anführen, dass sich immer irgendwann eine passende Zahl ergibt? Und ja, ich denke schon dass das mit Primzahlen zu tun hat. Letztenendes geht es um Teilbarkeit bzw. Nicht-Teilbarkeit. Die 'Formel' die ich angegeben habe, ist nichts anderes als der Algorithmus in einer mathematischen Form (wobei der Begriff Permutation noch mathematisch eingefangen werden müsste). Kannst du die mathematische Form beweisen, hast du auch bewiesen dass der Algorithmus anhält. Beweisen! Nicht vermuten, nicht glauben, nicht denken - sondern bewiesen.
> Beweisen! Nicht vermuten, nicht glauben, nicht denken - sondern > bewiesen. Wie recht du hast... Bin mir nicht sicher ob man hier von einer Permutation sprechen kann. Mindestens kann man aber nicht behaupten, dass die Permutation hier nur zum Verwirren da ist und keine Rolle spielt, weil sie bijektiv sei. Was passiert denn mit dem Fall, dass hinten eine Null steht? Schon ist's dahin mit der schönen Bijektivität. Die Schwierigkeit ist hier wirklich, die Reihenfolgenvertauschung mathematisch zu fassen. Ich versuch mal: Bestehe a aus den n Ziffern a_n,a_{n-1},...,a_1,a_0. Dann ist a = a_n * 10^n + a_{n-1} * 10^{n-1} + ... + a_1 * 10^1 + a_0 * 10^0 und c = a_0 * 10^n + a_1 * 10^{n-1} + ... + a_{n-1} * 10^1 + a_{n} * 10^0
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.