| Autor |
Beitrag |
    
sol@ti
Unregistrierter Gast
| | Veröffentlicht am Donnerstag, den 27. Juni, 2002 - 07:47: | 
|
Definition:
Eine natürliche Zahl heiße auf- bzw. absteigend geordnet, wenn ihre Ziffernfolge von links nach rechts auf- bzw. absteigend geordnet ist. Ziffernwiederholungen sind in beiden Fällen erlaubt. So ist z.B. 23347 aufsteigend, 963110 absteigend geordnet, 7 und 555555 sind definitionsgemäß sowohl auf- als auch absteigend geordnet.
Satz:
1.) Es gibt unendlich viele aufsteigend geordnete Zahlen, deren Quadrat aufsteigend geordnet ist.
2.) Es gibt nur endlich viele aufsteigend geordnete Zahlen, deren Quadrat absteigend geordnet ist.
Beweis:
"The proof is left to the reader"
|
sol@ti
Unregistrierter Gast
| | Veröffentlicht am Dienstag, den 02. Juli, 2002 - 10:49: |
|
Hinweis: Beweis 1.) mit Induktion, Beweis 2.) mit Inspiration (die ich bisher leider noch nicht in ausreichendem Maße hatte)!
|
;-)
Unregistrierter Gast
| | Veröffentlicht am Dienstag, den 02. Juli, 2002 - 17:55: |
|
Inspiration, Intuition...
Am einfachsten wäre es, sich Beispiele zu konstruieren |
Carmichael (carmichael)
Erfahrenes Mitglied
Benutzername: carmichael
Nummer des Beitrags: 143
Registriert: 02-2001
| | Veröffentlicht am Mittwoch, den 03. Juli, 2002 - 13:57: |
|
Hi,
zu 1) Dieser Teil ist noch recht einfach; es gilt nämlich: '33....34^2 = 1111..15....56'.
der Beweis dazu: (3*(10^n-1)/9+1)^2 = (10^2n-1)/9 + 4* (10^n-1)/9 + 1;
Das liefert offensichtlich unendlich viele aufsteigende Zahlen, deren Quadrat wieder aufsteigend ist.
zu 2) Bin ich auch auf nicht viel gekommen. Problem liegt bei den Überbeträgen beim Quadrieren; man kann von der Ziffernfolge der Zahl fast nicht auf die vom Quadrat der Zahl schließen, außer ganz hinten.
Denn: a^2 MOD 10^n = (a MOD 10^n)^2 MOD 10^n;
(MOD die modulo-funktion, die ist ja eigentlich nur in der Informatik üblich ist.)
Wir müssen also nur ein n finden, sodass das Quadrat aller n-stelligen aufsteigenden Zahlen in den letzten n Stellen nicht absteigend ist. Dann sind alle >=n stelligen Zahlen erschlagen.
Für diese Radikalmethode ist wohl ein PC erforderlich; ich denke es funktioniert mit n>=10, hab es es den PC aber noch nicht nachrechnen lassen. (um Rechenaufwand einzusparen arbeitet man sich am besten Schritt für Schritt vor, n=2,n=3,n=4...)
MfG Carmichael |
sol@ti
Unregistrierter Gast
| | Veröffentlicht am Mittwoch, den 03. Juli, 2002 - 17:32: |
|
Hi Carmichael, freut mich, dass du mitmachst!
Ja 1.) war sicher der einfachere Teil (z.B. 33...35 und 33...37 geht auch). Und bei 2.) bist du bereits weiter gekommen als ich. Ich habe meinen Rechenknecht auf die Suche geschickt und wir können von folgenden Ergebnissen ausgehen:
1(²=1) , 2(²=4), 3(²=9), 8(²=64), 9(²=81), 29(²=841), 88(²=7744) sind die einzigen aufsteigenden Zahlen mit absteigendem Quadrat bis 1 Mio., es wird wohl auch keine größeren mehr geben.
Dein MOD-Argument ist wahrscheinlich ein Schlüssel zum Beweis. Wieso denkst du, dass es für n>=10 funktionieren müsste? Wenn du ein mathematisches Argument dafür hast, würde mich das sehr interessieren! Dieser Suchraum wäre auch gerade noch im Bereich des Möglichen (mit PC). Übrigens hat das Quadrat der 6stelligen Zahl 138888(²=19289876544) noch 7 absteigende Ziffern hinten dran. Die Suche müsste also erst bei 7stelligen Zahlen beginnen.
Natürlich: Beweis ist Beweis. Aber wenn die größte aufsteigende Zahl mit absteigendem Quadrat tatsächlich 88 ist, sollte es da nicht eine elegantere Abschätzung geben als 'bis 10^10 alles durchsucht, nix gefunden'? Oder wie Philip J. Davis und Reuben Hersh bereits zynisch bemerkten: "Sollte es jemals zu einer Kraftprobe zwischen Mensch und Mathematik kommen, so werden die Menschen gut daran tun, die Computer abzustellen".
Viele Grüße
sol@ti
|
fireangel (fireangel)
Moderator
Benutzername: fireangel
Nummer des Beitrags: 122
Registriert: 10-2000
| | Veröffentlicht am Mittwoch, den 03. Juli, 2002 - 17:58: |
|
Hi,
auch auf die Gefahr hin, das ich jetzt begriffsstutzig wirke, könntest du, carmichael, deinen Beweis zu 1.) noch mal näher darlegen?
ich kann die Gleichung nicht wirklich nachvollziehen.
Dann die Frage an sol@ti:
ist das Problem überhaupt auf den reelen Zahlen definiert? Der Beweis von carmichael beinhaltet ja nicht abbrechende Dezimalzahlen (beim teilen durch neun).
Wenn ja, vernachlässigt ihr einfach den Nachkommateil? Und ist das in einem sauberen Beweis möglich?
Ich wäre mir da nicht sicher...
Aber ich lerne gern dazu.
Zu 2.) mach ich mir noch mal Gedanken.
Fireangel} |
sol@ti
Unregistrierter Gast
| | Veröffentlicht am Mittwoch, den 03. Juli, 2002 - 19:39: |
|
Hi Fireangel!
Nein, keine reellen Zahlen. Nur natürliche Zahlen. Carmichael meint das so geklammert:
(3*((10^n)-1)/9+1)^2 = ((10^(2n))-1)/9 + 4*((10^n)-1)/9 + 1 = 111...111 + 44...44 + 1 = 111...11155...556
Bin schon neugierig auf deine Überlegungen zu 2.)
sol@ti
|
fireangel (fireangel)
Moderator
Benutzername: fireangel
Nummer des Beitrags: 123
Registriert: 10-2000
| | Veröffentlicht am Mittwoch, den 03. Juli, 2002 - 19:45: |
|
Hi,
zu carmichaels Ansatz zu 2.):
es kann bis n=10 jedenfalls keine solche Zahl geben, braucht man nicht zu probieren, denn eine Zahl aus n Einsen erfüllt bis n=9 die Bedingung, das sie aufsteigend geordnet sei und die letzten n Ziffern ihres Quadrates absteigend geordnet sind.
Fireangel} |
fireangel (fireangel)
Moderator
Benutzername: fireangel
Nummer des Beitrags: 124
Registriert: 10-2000
| | Veröffentlicht am Mittwoch, den 03. Juli, 2002 - 19:58: |
|
hi,
ich hab nen anderen Ansatz:
ich betrachte nur die letzte Ziffer. Es sei:
Ao = Anfangsziffer der Originalzahl
Aq = Anfangsziffer des Quadrates
Eo und Eq = endsprechende Endziffern
für Eo = 1 wäre wegen OZ aufsteigend Ao = 1.
Damit wäre Aq immer 1, QZ nie absteigend.
für Eo = 2 wäre Eq = 4. Ao wäre 1 oder 2. Damit wäre Aq höchstens auch 4, eine absteigende QZ dürfte nur aus 4en bestehen, das geht nicht.
für Eo = 3 wäre Eq = 9. Jede Ziffer von QZ müsste 9 sein, das geht nicht.
für Eo = 5 wäre Eq = 5. Die vorletzte Ziffer wäre jedoch immer 2, damit QZ nicht absteigend.
Soweit bin ich bis jetzt. Mehr folgt gleich.
Fireangel |
Carmichael (carmichael)
Neues Mitglied
Benutzername: carmichael
Nummer des Beitrags: 1
Registriert: 02-2001
| | Veröffentlicht am Mittwoch, den 03. Juli, 2002 - 19:58: |
|
ja, genau, bei Einsen geht's nimmer und für n = 7 hab ich's mal ausprobiert gehabt, und da gibt's neben den 7 Einsern hintereinander nicht mehr allzu viele zulässige Fälle.
Das war der einzige Anhaltspunkt, dass bei n=10 alle zulässigen Fälle möglicherweise erschlagen sind.
Carmichael |
fireangel (fireangel)
Moderator
Benutzername: fireangel
Nummer des Beitrags: 126
Registriert: 10-2000
| | Veröffentlicht am Mittwoch, den 03. Juli, 2002 - 20:18: |
|
weiter:
Eo =4 damit Eq = 6. Aq muss größer/gleich 6 sein.
Ao kann nur 1,2,3,4 sein. Ist sie 1 oder 4, wäre Aq höchstens 2 (1 plus Übertrag von der vorletzten Stelle)
bleiben 2 oder 3. wenns 3 ist, dann darf es keinen Übertrag geben, den gibts aber immer, da nur noch 3 oder 4 als nächste Ziffern möglich sind.
bleibt 2. Dann wäre Aq = 4 plus Übertrag, der Übertrag kann höchstens 1 sein, wenn die zweite Ziffer eine 3 ist, dann wäre die dritte Stelle 8 plus übertrag, damit also 9. dann ist QZ nicht mehr absteigend.
Fireangel |
fireangel (fireangel)
Moderator
Benutzername: fireangel
Nummer des Beitrags: 127
Registriert: 10-2000
| | Veröffentlicht am Mittwoch, den 03. Juli, 2002 - 20:46: |
|
weiter:
Eo = 7, damit Eq = 9: heisst alle Ziffern in QZ 9.
die vorletzte Stelle wäre dann 4+2*a*b, würde also nie 9 erreichen.
Eo = 6, damit Eq = 6. Ao = 1,2,3,4,5 oder 6
Aq müsste über 6 liegen, das schliesst wieder 1,4,5,6 aus (siehe oben). bleiben 2,3.
Für 3 ist die Argumentation wie oben.
die zweite Stelle wäre ja 3+(2*6*zweite Ziffer)
das ist nur bei zweiteZiffer= 2 oder 3 größer als 6.
für den Fall zweite Ziffer= 2 müsste jede weitere Ziffer auch 2 sein, dass würde schon an dritter Stelle nicht mehr gehen.
für den Fall zweite Ziffer= 3 dürfte die nächste Stelle nur 2 oder 3 sein. In beiden Fällen wäre die dritte Stelle der QZ kleiner als die zweite.
Damit habe ich alle Eos von 1-7 ausgeschlossen.
Es bleiben 8 und 9.
Weiteres folgt.
Fireangel |
fireangel (fireangel)
Moderator
Benutzername: fireangel
Nummer des Beitrags: 128
Registriert: 10-2000
| | Veröffentlicht am Mittwoch, den 03. Juli, 2002 - 21:41: |
|
ich verallgemeinere das prinzip etwas:
eine Stelle der OZ hat höchstens auf die selbe Stelle oder davorliegende Einfluss. Betrachten wir also Eo = 8:
Eq wäre 4.
Damit müsste die zweite Stelle größer/gleich 4 sein: sie berechnet sich zu: 2*8*zweiteOZS.
Es kommen als zweiteOZS (OriginalZahlStelle) dementsprechend nur 2,3,5,7,8 in Frage.
Für 2 können wir folgendes sagen:
28 geht nicht, 228 geht nicht, 2228 geht nicht. Dann liegt der Fehler bereits ausserhalb des Einflusses weiterer Stellen.
Für 3 sagen wir:
weitere Stelle 3: 338 geht nicht, Fehler ausserhalb (siehe oben)
weitere Stelle 2: 238, 2238 22238 gehen nicht, dann Fehler ausserhalb.
Für 5: 58, 558 Schluss
458, 4458 Schluss;
3458, 33458 Schluss;
23458, 223458 Schluss;
123458, 1123458 Schluss;
358 Schluss,
258 Schluss,
158, 1158 Schluss.
Für 7:
78, 778 Schluss
678 Schluss
578 Schluss
478 Schluss
278 Schluss
178 Schluss
378, 3378 Schluss
2378 Schluss
1378, 11378 Schluss.
Für 8 wirds langwierig. 88 geht ja sogar.
Soweit erstmal, ich schau, ob ich ws besseres finde...
Fireangel
|
sol@ti
Unregistrierter Gast
| | Veröffentlicht am Donnerstag, den 04. Juli, 2002 - 12:29: |
|
Hi Fireangel,
die Untersuchung der Anfangs- und Endziffern war wieder mal eine deiner tollen Ideen!
Die "Verallgemeinerung des Prinzips" in deinem letzten Beitrag ist m.E. äquivalent mit Carmichaels MOD-Überlegung. Aber jetzt müssen wir nicht mehr schrittweise alle n-stelligen Zahlen überprüfen (wie Carmichael vorgeschlagen hat), sondern können rekursiv gezielt die möglichen n-stelligen Kandidaten aus einer bereits bekannten Menge von (n-1)-stelligen aufsteigenden Zahlen bestimmen. Ich versuche das formal darzustellen (in Blickrichtung Programmierung):
M1={8,9}
= mögliche Endziffern als Rekursionsanfang (1 bis 7 hast du ja bereits ausgeschlossen)
Mn+1={z*10n+m | m aus Mn , z = 1 bis Anfangsziffer von m , (z*10n+m)² mod 10n+1 ist absteigend}
= alle zulässigen (n+1)-stelligen aufsteigenden Zahlen, deren Quadrat mit (n+1) absteigenden Ziffern endet.
Bem.: M2={28,38,58,78,88,19,29,39,59,69,79,89}
Zu zeigen ist dann, dass es ein p gibt, sodass Mp={} (mit der Hoffnung p=10).
sol@ti
|
fireangel (fireangel)
Moderator
Benutzername: fireangel
Nummer des Beitrags: 129
Registriert: 10-2000
| | Veröffentlicht am Donnerstag, den 04. Juli, 2002 - 13:17: |
|
Hi,
genau. Und für einzelne Elemente ist das einfach:
19 => nix
29 => 229, 129 => 2229 => nix
39 => 339, 139 => 1139 => geht noch bis 1111139, dann nix;
59 => 359 => nix
69 => 569, 469 => 3569, 2569 => 33569,23569 =>nix
28 => 228 => nix
38 => 238 => 2238 => nix
58 => 458, 158 => 3458 => 23458 => 123458 => nix
78 => 378 => 1378 => nix
88 => 888, 788, 588, 388, 288
79 => 779, 479, 379, 279
89 => 889, 789, 689, 589, 389, 289, 189
Die letzteren bezeichnen dann auch das zu untersuchende M(3).
Fireangel |
fireangel (fireangel)
Moderator
Benutzername: fireangel
Nummer des Beitrags: 130
Registriert: 10-2000
| | Veröffentlicht am Donnerstag, den 04. Juli, 2002 - 13:39: |
|
weiter:
288 => nix
189 => nix
289 => 2289 => 22289 => nix
279 => nix
379 => 3379, 2379 => 23379, 13379 => nix
479 => 2479, 1479 => nix
779 => 4779 => 24779 => nix
689 => 3689 => 13689 => nix
589 => nix
588 => 4588, 2588 => nix
789 => 7789, 3789, 2789 => 33789, 47789 => 447789 => nix
788 => nix
889 => 8889, 7889, 6889, 3889, 2889, 1889
888 => 8888, 5888, 3888
Womit wir ein restliches M(4) hätten.
Fireangel |
fireangel (fireangel)
Moderator
Benutzername: fireangel
Nummer des Beitrags: 131
Registriert: 10-2000
| | Veröffentlicht am Donnerstag, den 04. Juli, 2002 - 13:51: |
|
weiter:
1889 => nix
2889 => nix
3889 => 33889, 23889 => 333889 => 1333889 => nix
3888 => 33888, 13888 => 133888 => nix
5888 => 25888 => nix
6889 => 36889 => nix
7889 => 77889, 37889, 27889 => 337889 => nix
8889 => 88889, 78889, 68889, 38889, 28889, 18889
8888 => 88888, 58888, 38888
M(5)
Fireangel |
fireangel (fireangel)
Moderator
Benutzername: fireangel
Nummer des Beitrags: 132
Registriert: 10-2000
| | Veröffentlicht am Donnerstag, den 04. Juli, 2002 - 14:13: |
|
weiter:
38888 => 138888 => nix
58888 => 258888 => nix
88888 => 888888, 388888 => 1388888, 8888888, 3888888 => NIX
18889 => nix
28889 => nix
38889 => 338889, 238889 => 3338889 => nix
68889 => nix
78889 => 378889 => nix
88889 => 888889, 788889, 388889, 288889
M(6) *heul*
288889 => nix
388889 => 3388889 => nix
788889 => 3788889 => nix
888889 => 8888889, 7888889, 3888889, 2888889
M(7) *verzweifel*
Fireangel |
fireangel (fireangel)
Moderator
Benutzername: fireangel
Nummer des Beitrags: 133
Registriert: 10-2000
| | Veröffentlicht am Donnerstag, den 04. Juli, 2002 - 14:22: |
|
2...9 => nix
3...9 => 33...9 => nix
7...9 => nix
8...9 => 88...9, 38...9
M(8)
3...9 => nix
8...9 => 88...9, 38...9
M(9)
3...9 => nix
8...9 => NIX
fertig. die höchste zu betrachtende Zahl war:
8.888.888.889, also zehnstellig, es gibt keine 10stellige Zahl, mit der es geht:
ALLE ANNAHMEN BEWIESEN
*erleichtert-in-den-Stuhl-fall*
Fireangel |
sol@ti
Unregistrierter Gast
| | Veröffentlicht am Donnerstag, den 04. Juli, 2002 - 18:51: |
|
Gratuliere, Fireangel, eine bemerkenswerte Lösung!
Ich bewundere immer wieder die Konsequenz, mit der du eine Idee, von der du überzeugt bist, bis zum Ende durchziehst. Bei M(6) *heul* und M(7) *verzweifel* befürchtete ich schon, dein Mut sei gebrochen. Aber weit gefehlt: mit neuem Elan zum Ziel! Großartig.
Außerdem ist jetzt klar, dass Carmichaels vollständige Suche bis 10^10 ebenfalls zum Ziel geführt hätte. Aber Fireangel hat eben einen O(log(n))-Algorithmus gefunden.
Danke für's Mitmachen!
sol@ti
|
fireangel (fireangel)
Moderator
Benutzername: fireangel
Nummer des Beitrags: 134
Registriert: 10-2000
| | Veröffentlicht am Donnerstag, den 04. Juli, 2002 - 20:11: |
|
Hi,
ich hab zu danken für die spannenden Rätsel. Wir finden hier scheints desöfteren so kleine und abgeschlossenen Zahlenbereiche mit besonderen Eigenschaften.
Was meinen Algorithmus betrifft, ich arbeite nur äusserst ungern mit CAS und zum Programmieren bin ich zu faul 
Deshalb muss immer eine altmodische Lösung herhalten, etwas, was ich mit nem Taschenrechner, nem Stift, nem Blatt Papier und ein bisschen Grips hinbekomme. Und da kommen dann solche Lösungen zustande.
Danke für die Formalisierung in deinem letzten Beitrag, hat es leichter gemacht, die Sache rüberzubringen...
CU
Fireangel
PS: Selbst meine Mathe-Profs sind an den PS-Zahlen erstaunt gescheitert ;) |
Carmichael (carmichael)
Neues Mitglied
Benutzername: carmichael
Nummer des Beitrags: 2
Registriert: 02-2001
| | Veröffentlicht am Donnerstag, den 04. Juli, 2002 - 20:27: |
|
auch von mir ein Lob an deine Lösung!
Da braucht's schon Ausdauer und natürlich auch Grips, um sowas durchzuziehen.
Besonders dein Ausschließen der Einerziffern von 1-7 hat mir gefallen, wo du die vorderste Stelle (der Zahl) ins Spiel bringst.
PS: eine Lösung mit Stift und Taschenrechner ist mir tausendmal lieber als eine mit dem PC.
MfG Carmichael |
|
