Die Mathe-Redaktion - 23.09.2019 16:14 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt? im neuen Schwätz
ListenpunktWerde Mathe-Millionär!
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 564 Gäste und 15 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von viertel
Matroids Matheplanet Forum Index » Rätsel und Knobeleien (Knobelecke) » * Folgen mit ungeradziffrigen Zahlen
Druckversion
Druckversion
Antworten
Antworten
Autor
Kein bestimmter Bereich * Folgen mit ungeradziffrigen Zahlen
querin
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 12.01.2018
Mitteilungen: 202
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2019-06-08


Hallo,

eine "odd-Folge" wird auf folgende Weise erzeugt:


1) Wähle eine natürliche Zahl als Startwert, z.B. $a_1=1486$.

2) Verdopple diese Zahl $2\ a_1=2972$ und streiche alle geraden Ziffern, das ergibt die nächste Zahl der odd-Folge $a_2=97$.

3) Wiederhole Schritt 2) bis beim Verdoppeln eine Zahl mit ausschließlich geraden Ziffern entsteht; damit endet die Folge.

Beispiel: $a_1=1486, a_2=97, a_3=19, a_4=3$.
Der vierstellige Startwert 1486 erzeugt also eine odd-Folge der Länge 4.


Gesucht ist ein möglichst kleiner Startwert für eine odd-Folge der Länge 102.


Die Quersumme des Startwertes kann offen gepostet werden.

Viel Spaß smile



  Profil  Quote  Link auf diesen Beitrag Link
Dies ist eine Knobelaufgabe!
Der Themensteller hat bestimmt, dass Du Lösungen oder Beiträge zur Lösung direkt im Forum posten darfst.
Bei dieser Aufgabe kann ein öffentlicher Austausch über Lösungen, Lösungswege und Ansätze erfolgen. Hier musst Du keine private Nachricht schreiben!
Kornkreis
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 02.01.2012
Mitteilungen: 795
Aus: Chemnitz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2019-06-08


Handelt es sich hierbei um eine Programmieraufgabe?



  Profil  Quote  Link auf diesen Beitrag Link
querin
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 12.01.2018
Mitteilungen: 202
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2019-06-08


2019-06-08 15:52 - Kornkreis in Beitrag No. 1 schreibt:
Handelt es sich hierbei um eine Programmieraufgabe?

Nein, es geht schon um einen formalen Beweis.



  Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 1624
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2019-06-08


Interessantes Rätsel.

Ich weiß noch nicht, ob es wirklich optimal ist, aber es gibt einen Startwert mit Quersumme .





  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3180
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2019-06-08



Wahrscheinlich ist meine Zahl größer, jedenfalls ist die Quersumme 912. Das Prinzip scheint dann aber das gleiche zu sein. Einen Beweis habe ich auch noch nicht.




-----------------
~ to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
Aquilex
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 05.12.2011
Mitteilungen: 17
Aus: Gelnhausen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2019-06-08


Ich habe einen Startwert mit Quersumme 888, aber auch noch keinen Beweis.



  Profil  Quote  Link auf diesen Beitrag Link
querin
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 12.01.2018
Mitteilungen: 202
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2019-06-08


Schön, dass ihr mitmacht smile

@Aquilex
Ich habe die selbe Quersumme (und wohl auch den selben Startwert). Ich vermute(!), dass dieser Startwert optimal ist, lass' mich aber gern eines Besseren belehren wink

Aus meinem Beweis ergibt sich, dass alle Längen $10^n+2$ für $n\ge 2$ eine kleine Besonderheit haben, für die diese spezielle Form der Startwerte passt.




  Profil  Quote  Link auf diesen Beitrag Link
Aquilex
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 05.12.2011
Mitteilungen: 17
Aus: Gelnhausen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2019-06-08



Hier meine naiven Überlegungen. (Ich entnehme der Beschreibung, daß man das hier posten darf/soll.) Als strengen Beweis würde ich das persönlich nicht bezeichnen.

Zunächst ist klar, daß man bei jedem Schritt möglichst wenige Ziffern verlieren darf, damit die Ausgangszahl minimal ist.

(1) Ist \(a_1=m\cdot 10^n-1\), so ist \(2a_1=2m\cdot 10^n-2\), was mit einer ungeraden Ziffer beginnt, die von 999...9998 gefolgt wird, d.h. es fällt lediglich die 8 weg, und \(a_2\) ist wieder von gleicher Form. Wenn \(2m>10\), bleibt die Ziffernzahl nach Streichen der schließenden 8 sogar gleich.

(2) Ist \(a_1=m\cdot 10^n-5\), so ist \(a_2=2m\cdot 10^n-10\), d.h. von der Form u99..990 (u: ungerade Ziffer), d.h. es fällt nur die 0 weg. \(a_2\) ist also von der Form (1).

(3) Ist \(a_1=m\cdot 10^n-25\), so ist \(2a_1=2m\cdot 10^n-50\), d.h. \(a_2=u99...95\) (Form (2)) und \(a_3=u99...9\), also Form (1).

(4) Ist \(a_1=m\cdot 10^n-125\), so ist \(2a_1=2m\cdot 10^n-250\), d.h. \(a_2=u99...75\) (Form (3)), \(a_3=u99...95\) (Form (2)) und \(a_4\) von Form (1).

(5) Ist \(a_1=m\cdot 10^n-5^4\), so ist \(2a_1=2m\cdot 10^n-1250\), d.h. \(u99..8750\), und es müssen u.U. zwei Ziffern gestrichen werden.

Da Form (4) die kleinste Startzahl liefert, bei der alle Folgenglieder außer den letzten beiden in diesem System bleiben, dürfte die gesuchte Startzahl von dieser Form sein.
Als kleinste Startzahl mit Folgenlänge 102 fand ich so \(a_1=5\cdot 10^{99}-125\).


[Die Antwort wurde nach Beitrag No.5 begonnen.]



  Profil  Quote  Link auf diesen Beitrag Link
querin
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 12.01.2018
Mitteilungen: 202
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2019-06-09


Sehr gut Aquilex, damit ist für die Länge 102 die Katze aus dem Sack!

Aber wie du selbst schreibst sind deine Überlegungen wohl kein ganz strenger Beweis. Insbesondere geht die erwähnte "kleine Besonderheit" der Länge 102 nicht ein. Welcher minimale Startwert würde sich bei deinem Vorgehen für die Länge 101 ergeben?

Die Ideen hinter den Startwerten von Nuramon und gonz würden mich auch sehr interssieren. Vielleicht zeigen sie einen Weg zu noch kleineren Startwerten?

LG smile




  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3180
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2019-06-09




Dies ist meine Überlegung in reinschrift, soweit ich inzwischen war. Ich hatte mich gestern auch irgendwie vertüddelt...

Meine Überlegungen wurden zunächst von einem Programm inspiriert, das für kleine Werte von n ( genauer: bis n=11 ) die optimalen Folgen durch brute force ermittelt hat. Dabei stellt sich heraus, dass hier Lösungen der Form

u9...975

dominieren. Es ist klar, dass eine Folge von 9er Ziffern sich regeneriert und nur am Ende jeweils eine Ziffer verliert, während vorne jeweils ein Übertrag von 1 entsteht, der sich auf die Nachfolger des Prefix u auswirkt. Das hat Aquilex sehr schön in den Regeln (1)..(3) ausgeführt.

Für den Wert u ergibt sich, solange noch eine 9-er Kette folgt, also ein Übertrag generiert wird, folgende Abfolge:

(keine Ziffer) - 1 - 3 - 7 - 15 - 31 - 63=>3

das heißt längerfristig der Zyklus 3 - 7 - 15 - 31 - 3 usw

Ich beginne also mit einer Kette der Form

a(1) = 9.(x-fach).975
a(2) = 19.(x-fach).95
a(3) = 39.(x-fach).9

Damit habe ich dann 4-er Zyklen, es ist

(A) a(3+4z) = 39. ( x-4z fach).9
(B) a(4+4z) = 79. ( x-4z-1 fach).9
(C) a(5+4z) = 159.( x-4z-2 fach).9
(D) a(6+4z) = 31. ( x-4z-3 fach).9

Nun muss ich am Ende noch den Ausstieg zum Endglied 102 hin finden, dazu ist zu betrachten, wie sich das Prefix entwickelt, wenn kein Übertrag mehr erfolgt.

Fall (A): Aus 3 wird dann unmittelbar 6 und damit ist das Ende der Folge erreicht. Damit das funktionert, muß 3+4z = 102 sein, was nicht aufgeht.

Fall (B): Aus 7 wird 14=>1 und daraus 2 und das Kettenende ist erreicht. Es muss also 4+4z+1=102 sein, was ebenfalls nicht geht.

Fall (C): Aus 15 wird 30=>3 und daraus 6, womit das Kettenende erreicht ist. Die Bedingung lautet hier also 5+4z+1 = 102 => 4z=96 => z=24

Das heisst die Folge läßt sich konstruieren als

a(1) = 9..(4*24+2 fach)..975
a(2) = 19..(4*24+2 fach)..95
a(3) = 39..(4*24+2 fach)..9
a(4) = 79..(4*24+1 fach)..9
a(5) = 159..(4*24 fach)..9
a(5+4*24) = a(101)=15
a(5+4*24+1) = a(102)=31

Damit ist die Quersumme 9*98 + 7 + 5 = 894






-----------------
~ to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
Aquilex
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 05.12.2011
Mitteilungen: 17
Aus: Gelnhausen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, eingetragen 2019-06-09


@ querin
Für Länge 101 hätte ich 1e99 - 125 zu bieten,
für 100: 2e98 - 125,
für 103: 5e100 - 125.
Da sich für 1002 der Startwert 5e999 - 125 findet und für 10002 der Startwert 5e9999 - 125, zeichnet sich die Besonderheit ab, die du vermutlich meinst. Ich bin auf den Beweis gespannt.

@ gonz
Ich hatte auch mit brute-force begonnen und festgestellt, daß die optimalen Folgen jeweils mit den oben beschrieben u9_9875, u9_975, u9_95, u9_9 loslegen und dann bis drei vor Schluß in u9_9 bleiben. 9_9 steht für Neunerketten beliebiger Länge.
Das Ausprobieren für die Riesenzahlen überließ ich dann Mathematica.
Tatsächlich kann man wohl von der von dir beschriebenen zyklischen Folge der u ausgehen 3-7-15-31, aber dann am Anfang die ersten drei nach meinen oben beschriebenen Formen (2) bis (4) ändern, die eine Verkleinerung der Startzahl bringen. Hier ergeben sich für u die Abfolgen 4-9-1-3, die stets bei 3 in den anderen Zyklus überzugehen scheinen.
Vielleicht kann man daraus den Beweis basteln.
Aber beweist man damit, daß es nicht noch bessere Wege geben kann?

In meiner Darstellung oben fehlt noch die Feststellung, daß kein Folgenglied mehr Ziffern haben kann als der Vorgänger, denn durch die Verdopplung, die ja u.U. eine Stelle mehr bringt, ist mindestens die Einerstelle gerade und fällt dann weg.

Schöne Grüße
Aquilex



[Die Antwort wurde vor Beitrag No.1 begonnen.]



  Profil  Quote  Link auf diesen Beitrag Link
Aquilex
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 05.12.2011
Mitteilungen: 17
Aus: Gelnhausen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2019-06-09


Ich habe noch ein wenig über die Sache nachgedacht.

Der Zyklus 3-7-15-31 für die Startziffern ist leicht nachzurechnen. (Im folgenden stelle 9_9 immer eine beliebig lange Kette von Neunen dar.)

Aus Startziffer 3 wird 7, denn \(39\_9 = 4\cdot10^n-1\), und \(2\cdot(4\cdot10^n-1) = 8\cdot10^n-2 = 79\_98\). Streichen der 8: \(79\_9 = 8\cdot10^{n-1}-1\)
D.h. für die Startziffer gilt \(2\cdot(3+1)-1=7\).
Analog \(2\cdot(7+1)-1=15\) und \(2\cdot(15+1)-1=31\).
Dann \(2\cdot(31+1)-1=63\); und Streichen der geraden 6 ergibt wieder eine führende 3.

Im Schritt auf 15 bleibt die Ziffernzahl gleich, dafür nimmt sie im letzten Schritt um 2 ab, sonst um 1, d.h. pro 4er-Zyklus werden 4 Ziffern gestrichen.

Alle anderen Ziffern u münden per \(u \rightarrow 2(u+1)-1 = 2u+1\) und Streichen gerader Ziffern bald in diesen Zyklus:
1 → 3
2 → 5 → 1 → 3
4 → 9 → 1 → 3
4<u<10 → 1 → 3

Die optimale Startzahl scheint, wie oben dargestellt, die Form \(a_1=k\cdot10^n-125\) zu haben. Wegen \(2\cdot a_1 = 2k\cdot 10^n-250 = u9\_9750 \Rightarrow a_2=2k\cdot 10^{n-1}-25\). Ist 2k-1=3, beginnt also \(a_2\) mit 3, so ist k=2 klar, d.h. \(a_1\) beginnt mit 1.
Analog folgt aus 2k-1=1, daß k=1, d.h. für den Vorgänger ist u=9.
2k-1=9 -> k=5, d.h. u=4.
Das erklärt die abweichenden Startziffern der ersten drei Folgenglieder.

Weiter wäre nun noch zu zeigen, daß alle Zahlen, die nicht die Form \(k\cdot10^n-5^m\) mit \(0\le m<4\) haben und insbesondere kleiner sind, im Nachfolger mehr als 1 Ziffer verlieren und unter diesem ungünstigen Verlust gerader Ziffern außerdem alsbald in die Form u9_9 mit u=3, u=7, u=15 oder u=31 übergehen. Aber dazu habe ich jetzt keine Muße mehr.



  Profil  Quote  Link auf diesen Beitrag Link
querin
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 12.01.2018
Mitteilungen: 202
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, vom Themenstarter, eingetragen 2019-06-10


Lösung:
$a_1=5\cdot 10^{99}-125$ erzeugt eine odd-Folge der Länge 102.

Allgemein gilt für eine vorgegebene Länge $L\ge 5$:
Es gibt einen höchstens (L-1)-stelligen Startwert für eine odd-Folge der Länge L.
Wenn L nicht durch 4 teilbar ist gibt es sogar einen (L-2)-stelligen Startwert für eine odd-Folge der Länge L.


Beweis (im Wesentlichen reine Schreibarbeit):
Ich verwende im Folgenden die Abkürzung $(m,k,j)$ für $m\cdot 10^k-j$

Betrachte zunächst den Startwert $(4,k,1)$. Dieser führt auf den Zyklus
$a_1=(4,k,1),\ a_2=(8,k-1,1),\ a_3=(16,k-1,1),\ a_4=(32,k-2,1),\ a_5=(4,k-4,1)$.
$a_5$ hat die gleiche Form wie $a_1$ aber um vier Stellen weniger, es gilt $a_{4j+1}=(4,k-4j,1)$ für $0\le 4j\le k$.

Nun folgt die Untersuchung der Startwerte $(1,k,125)$, $(2,k,125)$ und $(5,k,125)$.

$a_1=(1,k,125),\ a_2=(2,k-1,25),\ a_3=(4,k-2,5),\ a_4=(8,k-3,1)$
Hier mündet die Folge in den Viererzyklus und es gilt $a_{4j}=(8,k-4j+1,1)$ für $4\le 4j\le k+1$.
Fallunterscheidungen modulo 4:
Für $k=4t$ ist $a_{4t}=(8,1,1)$, die Folge endet mit $79, 15, 3$. Länge $4t+2$.
Für $k=4t+1$ ist $a_{4t}=(8,2,1)$, die Folge endet mit $799, 159, 31$. Länge $4t+2$.
Für $k=4t+2$ ist $a_{4t}=(8,3,1)$, die Folge endet mit $7999, 1599, 319, 3$. Länge $4t+3$.
Für $k=4t+3$ ist $a_{4t+4}=(8,0,1)$, die Folge endet mit $7, 1$. Länge $4t+5$

$a_1=(2,k,125),\ a_2=(4,k-1,25),\ a_3=(8,k-2,5),\ a_4=(16,k-3,1)$
Hier mündet die Folge in den Viererzyklus und es gilt $a_{4j}=(16,k-4j+1,1)$ für $4\le 4j\le k+1$.
Fallunterscheidungen modulo 4:
Für $k=4t$ ist $a_{4t}=(16,1,1)$, die Folge endet mit $159, 31$. Länge $4t+1$
Für $k=4t+1$ ist $a_{4t}=(16,2,1)$, die Folge endet mit $1599, 319, 3$. Länge $4t+2$
Für $k=4t+2$ ist $a_{4t}=(16,3,1)$, die Folge endet mit $15999, 3199, 39, 7, 1$. Länge $4t+4$
Für $k=4t+3$ ist $a_{4t+4}=(16,0,1)$, die Folge endet mit $15, 3$. Länge $4t+5$

$a_1=(5,k,125),\ a_2=(1,k,25),\ a_3=(2,k-1,5),\ a_4=(4,k-2,1)$
Hier mündet die Folge in den Viererzyklus und es gilt $a_{4j}=(4,k-4j+2,1)$ für $4\le 4j\le k+2$.
Fallunterscheidungen modulo 4:
Für $k=4t$ ist $a_{4t}=(4,2,1)$, die Folge endet mit $399, 79, 15, 3$. Länge $4t+3$
Für $k=4t+1$ ist $a_{4t}=(4,3,1)$, die Folge endet mit $3999, 799, 159, 3$. Länge $4t+3$
Für $k=4t+2$ ist $a_{4t+4}=(4,0,1)$, die Folge endet mit $3$. Länge $4t+4$
Für $k=4t+3$ ist $a_{4t+4}=(4,1,1)$, die Folge endet mit $39, 7, 1$. Länge $4t+6$

Daraus ergeben sich folgende kleinste Startwerte für die Länge L:
$L\equiv 0 \mod 4:\ a_1=2\cdot 10^{L-2}-125$
$L\equiv 1 \mod 4:\ a_1=1\cdot 10^{L-2}-125$
$L\equiv 2,\ 3 \mod 4:\ a_1=5\cdot 10^{L-3}-125$

Bemerkungen:
Auf die speziellen Formen der Startwerte bin ich durch Extrapolation der brute-force Lösungen bis $L=10$ gekommen.
Für die Viererreste 2 und 3 erhalte ich die im Verhältnis zu L kleinsten Startwerte (das ist die "kleine Besonderheit" von 102 bzw. 103).
Interessant wäre natürlich der Beweis, dass es keine kleineren Startwerte für $L\ge 5$ gibt.



//edit: Korrektur nach Hinweis von Aquilex



  Profil  Quote  Link auf diesen Beitrag Link
Aquilex
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 05.12.2011
Mitteilungen: 17
Aus: Gelnhausen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, eingetragen 2019-06-10


Hallo, querin,
das deckt sich ja mehr oder weniger mit meiner Darstellung, allerdings...

2019-06-10 19:28 - querin in Beitrag No. 12 schreibt:
...
Betrachte zunächst den Startwert $(4,k,1)$. Dieser führt auf den Zyklus
$a_1=(4,k,1),\ a_2=(8,k-1,1),\ a_3=(16,k-2,1),\ a_4=(32,k-3,1),\ a_5=(4,k-4,1)$.
...

... sollte es hier nicht $a_3=(16,k-1,1),\ a_4=(32,k-2,1),\ a_5=(4,k-4,1)$ heißen?


Schönen Gruß
Aquilex



  Profil  Quote  Link auf diesen Beitrag Link
querin
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 12.01.2018
Mitteilungen: 202
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, vom Themenstarter, eingetragen 2019-06-10


Hallo Aquilex, vielen Dank für den Hinweis (ich hab's ausgebessert).

Ja, das deckt sich exakt mit deinen Werten für $L=100$ bis $L=103$. Das bestärkt mich ja in dem Glauben, dass es tatsächlich keine kleineren Startwerte gibt. Aber ich kann es nicht beweisen...

LG querin



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3180
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.15, eingetragen 2019-06-11


Ich glaube es könnte ungefähr so gehen:



Betrachten wir eine Stelle, an der "irgendwo in der Mitte" der Zahl eine Ziffer kleiner 9 steht. Da wir vorab alle geraden Ziffern entfernt haben, kann das nur eine 1,3,5 oder 7 sein.

Nun lassen wir den Fokus auf dieser Stelle ( dh wir wandern mit, wenn sie aufgrund von weiter rechts entfallenden Stellen ebenfalls nach rechts wandert). Sie kann dann von rechts beim verdoppeln jeweils nur einen Übertrag von 1 dazuaddiert bekommen. Nun erzeugt diese Stelle aber, auch wenn sie durch stehten Übertrag von rechts "am Leben erhalten wird", links mit einer gewissen Regelmäßigkeit einen Kollateralschaden:

eine "7" wird verdoppelt zur 14, damit verbleibt eine 4 auf unserer Position, die nur überlebt, wenn sie einen Übertrag bekommt (logisch) und damit zur "5" wird.

Eine "5" wird verdoppelt zur 10 und damit verbleibt mit Übertrag eine "1".

Damit werden die beiden Fälle "7" und "5" zu einem der folgenden Fälle, und es ist jetzt weiters:

Eine "3" wird verdoppelt und mit Erhalt eines Übertrag zur 7, es erfolgt aber kein Übertrag auf die links liegende Stelle, sodaß diese notwendig "stirbt",

Eine "1" wird verdoppelt und mit Erhalt eines Übertrag zur 3, es erfolgt aber kein Übertrag auf die links liegende Stelle, sodaß diese notwendig "stirbt",

Insgesamt stirbt damit in zwei von vier Runden eine Stelle ( nämlich die davorliegende). Das Verhalten ist also in diesem Fall deutlich schlechter als in einer reinen Folge von "9".

Und - es kann auf diese Art nie eine "9" entstehen, sodaß derartige "Stellen" in der Folge auch nie aussterben können, es sei denn, sie erhalten selber keinen Übertrag mehr von rechts. Damit könnte man glaube ich zeigen, dass alle Folgen, die "im Inneren" Ziffern ungleich 9 beinhalten, schlechter abschneiden.

( Ein formal ausgeführter Beweis ist das natürlich auch noch nicht, höchstens eine Beweisidee ).




-----------------
~ to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3180
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.16, eingetragen 2019-06-13


Noch einmal in geordneter:


Die Startfolge selber spielt eine gesonderte Rolle, da zunächst verdoppelt wird, bevor die geraden Ziffern entfernt werden. Deshalb kann man mit der "8" auf der drittletzten Stelle einiger Folgen eine Verbesserung erzielen. Dies ist für Folgeglieder n>1 nicht mehr der Fall, da sie mit der nächsten Runde entfallen. Hier ist es ausreichend, das Verhalten ungerader Ziffern zu betrachten.

Eine weitere Sonderrolle spielen die am Anfang der Folge entstehenden, zusätzlichen Ziffern.

Die letzte Ziffer der Folge wird hingegen immer entfallen, da sie durch die Verdoppelung gerade wird und keinen Übertrag von weiter rechts erhalten kann, eben da sie am Ende steht.

Betrachten wir nun also Ziffern in Folgegliedern n>1, die sich weder am Anfang noch am Ende der Folge befinden. Diese sind notwendig ungerade.

Wenn man den Werdegang einer Ziffer betrachtet, unabhängig davon, dass sie durch das Wegfallen von Ziffern weiter rechts selber nach rechts wandert, also ihre Stelle festhält, bis sie ggf. später selber gelöscht wird (weil sie keinen Übertrag erhalten hat, was spätestens passiert, wenn sie ganz rechts am Ende der Folge gelandet ist) - dann ergeben sich folgende beiden Zyklen:



Dabei ist der 9-er Zyklus völlig von den restlichen Ziffern getrennt. Eine "9" überlebt solange, bis sie keinen Übertrag erhält, und es kann auch keine 9 neu entstehen. In der Folge sind also nur die Überlebenden der 9er Stellen enthalten, die sich schon aus der Ausgangsfolge ergeben haben.

Für die anderen Ziffern gilt, dass sie in dem Zyklus 7-5-1-3-7... laufen, solange sie selber einen Übertrag erhalten. Dabei geben sie nur in der Hälfte der Zustände selber einen Übertrag ab, sodaß im Mittel jede zweite Runde eine Stelle links von ihnen mangels Übertrag entfällt, und damit ein zusätzlicher Faktor von mindestens 1/10 zu dem ohnehin am Ende der Folge entstehenden 1/10 hinzukommen.

(immer noch nicht sehr formal formuliert, aber ich denke einsichtig. Und mit Grafik * schmunzel)

Deshalb ist es ausreichend, sich auf 9-er Folgen zu beschränken, und deren Verbesserungen durch Veränderung am Ende ( das schon bekannte -5^3 ) und in der Anfangsziffer.

Dann in Abhängigkeit von n (zB mod 4) zu schauen, wie sich diese Werte für n->102 zu einem passenden Auslaufen der Folge nach dem Aufbrauchen aller 9-er Ziffern entwickeln.

Soweit für jetzt :)
Grüsse aus dem Harz

Gonz



-----------------
~ to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
querin
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 12.01.2018
Mitteilungen: 202
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.17, vom Themenstarter, eingetragen 2019-06-13


Hallo gonz,

das ist eine fundierte und schlüssige Argumentation (mit gut verständlicher Grafik!), warum "in der Mitte" nur 99...9 vorkommen kann. Der entscheidende Punkt ist wohl, dass durch das Verdoppeln keine 9 aus kleineren Ziffern erzeugt werden kann. Ob das schon ein gültiger formaler Beweis ist kann ich nicht beurteilen, mich hat es jedenfalls überzeugt.

Für den Beweis, dass die gefundenen Startwerte minimal sin, müsste man auch erklären welche Anfangsziffer optimal ist (1,4,9 abhängig von $L\mod 4$) oder warum gerade die Endziffern 875 die kleinsten Startwerte erzeugen?

Natürlich kann man das mit einem einfachen Schleifendurchlauf überprüfen. Aber ohne Computer sind tausende Fallunterscheidungen ähnlich elegant wie wenn man die Ungleichung $n^2-1000n+100000<0$ durch Einsetzen aller ganzen Zahlen von 0 bis 1000 lösen würde wink

Viele Grüße in den Harz
querin



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3180
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.18, eingetragen 2019-06-13


Die Sache mit der 875 am Ende ist recht einfach zu begründen.

Eine Folge mit n x Ziffer 9 am Ende verliert mit jedem Schritt lediglich die letzte Ziffer. Damit also eine andere Ziffernfolge genauso gut bzw. besser ist, darf sie auch nur die letzte Ziffer verlieren, die ja notwendig sowieso gerade ist und verloren geht.

Für die letzte Ziffer ist das optimalerweise die "5" ( kleinere Ziffern liefern keinen Übertrag ).

Für die vorletzte Ziffer muss es für das Überleben einer weiteren Runde reichen, die "5" und die "6" verändern sich jedoch im zweiten Schritt zu "1" bzw. "3" und liefern damit im Folgeschritt keinen Übertrag mehr, scheiden also aus. Genau die "7" ist ausreichend, da sie über "5" zwar nur "0" wird, in beiden Schritten aber Übertrag erzeugt und danach sowieso verschwinden würde, da dann die letzte Stelle der Ziffernfolge.

Die drittletzte Ziffer muss drei Runden lang nach vorne Übertrag liefern, das leistet genau die "8", die übergeht in "7" und dann in "5" und letztlich als "0" gelöscht wird.

Damit ist die Folge 875 für die letzten Stellen optimal.

Die viertletzte Ziffer kann damit nur noch "9" sein, da keine kleinere Ziffer über die nächsten vier Schritte einen Übertrag liefern kann.

Verbleibt, eine Fallunterscheidung für die Startziffern durchzuführen. Damit sollte sich dann insgesamt eure Lösung mit Quersumme 888 als optimal beweisen lassen.



-----------------
~ to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
querin
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 12.01.2018
Mitteilungen: 202
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.19, vom Themenstarter, eingetragen 2019-06-14


Hallo gonz,

das ist ein schöner Abschluss dieser Aufgabe, vielen Dank. Damit ist bewiesen, dass die gefundenen Startwerte tatsächlich minimal sind. Das ist mehr als ich zu Beginn beim Zusammenbasteln der Aufgabe zu hoffen wagte.

LG querin



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3180
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.20, eingetragen 2019-06-14


Na so ganz fertig sind wir damit noch nicht :)

Aber es geht voran...


-----------------
~ to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
querin hat die Antworten auf ihre/seine Frage gesehen.
Dies ist eine Knobelaufgabe!
Der Themensteller hat bestimmt, dass Du Lösungen oder Beiträge zur Lösung direkt im Forum posten darfst.
Bei dieser Aufgabe kann ein öffentlicher Austausch über Lösungen, Lösungswege und Ansätze erfolgen. Hier musst Du keine private Nachricht schreiben!
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2019 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]