"Natürliche Zahlen"-Lösung eines Bruchs

Neue Frage »

Neugierig17 Auf diesen Beitrag antworten »
RE: "Natürliche Zahlen"-Lösung eines Bruchs
Meine Frage:
Hallo zusammen,
ich bin mir bei Titel und Kategorie nicht ganz sicher, aber ich hoffe, trotzdem einige Lösungsansätze oder Ideen für mein Problem zu bekommen.

Seien . Für m gilt außerdem:
Sei S die Summe einer Sequenz aus m Nullen und n Einsen. Mithilfe der Sequenz wird eine Summe nach folgender Vorschrift gebildet. Die Sequenz wird von links nach rechts durchgegangen und bei jeder Eins wird die Summe um
(A1 = Anzahl aller Einsen rechts von dieser Eins, A2 = Anzahl aller Nullen und Einsen links von dieser Eins) erhöht.
Beispiele:
Aufgabe: Zeige, dass kein S (außer für m = 1 und n = 1) existiert, sodass


Meine Ideen:
Das kleinste S ist gegeben durch die Sequenz
,
das größte S durch die Sequenz

Daher bin ich auf eine andere Darstellungsart gekommen.

Dabei ist mir an Beispielen aufgefallen, dass usw.
Allerdings kann ich dies nicht nachweisen. Beispiele:




Vielleicht ist es einfacher zu beweisen, dass es (außer für m = 1 und n = 1) kein

gibt.

Korrektur aus zweitem Beitrag übernommen. Steffen
HAL 9000 Auf diesen Beitrag antworten »

Für ist die Voraussetzung

Zitat:
Original von Neugierig17

erfüllt:



.

Dumm nur, dass die Aussage für diese falsch ist:

Für Bitsequenz 1010 ergibt sich Wert , was exakt entspricht, also doch Teilbarkeit im Widerspruch zur Behauptung.


EDIT: Generell betrachtet ist für die Sequenz 1010...10 ein Gegenbeispiel, und erfüllt die obige Ungleichungsvoraussetzung!!!
 
 
Neugierig17 Auf diesen Beitrag antworten »

Hallo Hal,

da war ich wohl etwas unüberlegt.
Ich wusste ja, dass für m=n=1 das ganze eine Lösung in hat.
Für 10 ist für 01 ist .
Ich habe allerdings nicht daran gedacht, dass dies auch für die Wiederholung einer der beiden Sequenzen gilt.
Wie Du bereits richtig gesagt hast, gilt für m=n und die Sequenz 1010...10: . Außerdem gilt für die Sequenz 0101...01: .

Eine genauere Frage wäre also:
Existiert ein Weg zu zeigen, dass es keine Sequenz gibt, für die gilt, dass .
Genauso hilfreich wäre natürlich ein Gegenbeispiel.
HAL 9000 Auf diesen Beitrag antworten »

Ich hab nur noch festgestellt, dass im Fall die Bit-Sequenzen

110110...110
101101...101
011011...011

ebenfalls zu ganzzahligen Quotienten führen, und zwar den Quotientenwerten -5, -7, -10.

Allerdings erfüllen diese nicht deine obige Ungleichung, und außerdem ist da , was du vermutlich auch nicht willst. Augenzwinkern
Neugierig17 Auf diesen Beitrag antworten »

Nein, leider brauche ich Quotienten in den natürlichen Zahlen (ohne 0, 1, 2). Trotzdem Danke für deine Hilfe.
HAL 9000 Auf diesen Beitrag antworten »

Aus den obigen Schemata kann man folgende Behauptung ableiten:

Zitat:
Es seien sowie mit positiven ganzen Zahlen derart, dass .

Außerdem sei x eine beliebige Sequenz aus genau Nullen und Einsen. Dann erfüllt die Sequenz

(d.h. genau -mal hintereinander die 0-1-Sequenz wiederholt) die Eigenschaft, dass das gemäß deiner Vorschrift zugehörige die Eigenschaft hat.

Der Nachweis ist relativ leicht. Schwerer ist der Nachweis, dass es wohl nur die positiven -Paare und gibt, die erfüllen. Augenzwinkern

Und was sich nach Sichtung empirischen Datenmaterials wohl vermuten lässt: Gibt es für nicht solche , dann gilt für alle solche Sequenzen. Das ist der schwere Part des Nachweises.
Neugierig17 Auf diesen Beitrag antworten »

Sei f die Funktion, die eine Sequenz auf die der Regel entsprechenden Zahl abbildet.
Sei n = u*w, m=v*w und w-mal die Wiederholung der Sequenz x aus u Einsen und v Nullen, dann gilt für (wobei ):
Die Formel ensteht dadurch, dass ich für das erste x noch (w-1)*v Einsen rechts von sich stehen hat, das zweite x noch (w-2)*v Einsen und generell das i-te x noch (x-i)*v Einsen, d.h Außerdem stehen vor dem i-ten x noch (i-1)*(u+v) Nullen und Einsen, daher zusätzlich
d.h. es reicht das Ganze für w = 1 zu zeigen.

Für den zweiten Teil hab ich was gefunden. Es nennt sich Catalansche Vermutung (wurde bewiesen), dass es für für a,b,x,y > 1 nur die Lösung a=2, b=3, x=3, a=2 gibt.
Da a = 2 und b = 3 können wir die restlichen Fälle (x=0, x=1, y=0, y=1) schnell selbst durchprobieren und sehen, dass es insgesamt für nur vier Möglichkeiten gibt:
x=1,y=0: ,
x=1,y=1: ,
x=2,y=1: ,
x=3,y=2: .
Da und S positiv ist und das Ergebnis auch positiv sein soll, gibt es für mein Problem sogar nur eine einzige Lösung, nämlich m=n=1.
Es gibt also keine weiteren trivialen Lösungen für außer die Sequenzen 01 und 10 und deren Wiederholungen.

Das Problem ist und bleibt also der letzte (und schwerste) Schritt.
Formt man die Bedingung für m etwas um und setzt diese im Divisor ein, so ergibt sich für die Formel:

und für die Extremfälle:

Vielleicht krieg ich über diese Darstellungsversion noch was raus.
Aber nochmals Danke für deine Hilfen und Denkanstöße, Hal.
Neue Frage »
Antworten »



Verwandte Themen

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