Collatz Problem ed

Ein mathematisches Problem.... ungelöst?

Meine eigenen Gedanken dazu, damit ich sie mir nicht jedes Mal neu ausdenke

Problem ed

Man fängt mit einer natürlichen Zahl n an und berechnet dann

$  n / 2  $ , falls n gerade

$  3n + 1  $ , falls n ungerade

und das rekursiv.

Die Behauptung ist, dass man über diese Verkettung von jeder natürlichen Zahl aus zur 1 kommt.

Inverses Problem ed

Problem ed

Man kann eine Menge \( M_C \) definieren als diejenigen Zahlen, bei denen der "inverse" Graph von der 1 aus vorbei kommt:

• also zuerst \( 1 \in M_C \)
• für jede Zahl \( n \in M_C \) ist auch \( 2n \in M_C \) (Regel 1)
• ist \( n \equiv 4 \, (\text{mod } 6) \quad (n - 1) / 3 \in M_C \) (Regel 2)

Die Frage ist dann, ob \( M_C = \mathbb{N} \)

Definitionen ed

Ein Ast geht von einer Zahl (dem Keim) aus und folgt dann nur durch Regel (1).

Der Hauptast des Graphs ist der Ast mit der 1 als Keim. Mit den durch ihn erzeugten Keimen sieht er so aus:

$ 
 \begin{array}{llll}
   1 \rightarrow 2 \rightarrow &4 \rightarrow 8 \rightarrow &16 \rightarrow 32 \rightarrow &64 \rightarrow \dots\\
                               &1                           &5                             &21
 \end{array}
$ 

Gedanken ed

Gedanke 0 ed

Ein Keim ist ungerade

Folgt aus der ursprünglichen Problemstellung, dass eine gerade Zahl immer halbiert wird (also kein Keim sein kann).

Gedanke 1 ed

Ein Ast besteht aus dem Keim und allen seinen 2er-Potenzen

Geht direkt aus der Regel (1) hervor.

Somit muss nur gezeigt werden, dass jede ungerade Zahl als Keim auftritt.

Gedanke 2 ed

Ist ein Keim durch 3 teilbar, so erzeugt dessen Ast keine neuen Keime

Ist der Keim durch 3 teilbar, so sind auch alle Elemente n des Astes durch 3 teilbar und damit kann n+1 nicht durch 3 teilbar sein.

Gedanke 3 ed

Erzeugt ein Element eines Astes einen Keim, so erzeugt das übernächste Element einen weiteren Keim

Ein Keim n wird von einem Ast-Element der Form \( 3n + 1 \) erzeugt. Das übernächste Ast-Element ist dann \( 4 (3n + 1) = 12n + 4 = 3 (4n + 1) + 1 \) . Somit ist der neue Keim von der Form \( 4n +1 \) (das Ast-Element dazwischen erzeugt keinen Keim!)

Insbesondere sind die von einem Ast erzeugten Keime dann durch den ersten Keim und dessen durch die Regel \( n \mapsto 4n + 1 \) Kette gegeben.

Gedanke 4 ed

Ein Keim erzeugt nicht selbst einen Keim

Ein Keim n ist ungerade. Dann kann er nicht von der Form \( n = 3m +1 \) mit einer ungeraden Zahl m sein.

Gedanke 5 ed

Äste können sich nicht überschneiden

Hätten zwei Äste ein Element gemeinsam (nicht der Keim...), so hätte dieses Element 2 verschiedene Wege zur 1 und das widerspricht dem "positiven" Problem.

Damit muss die Abbildung vom Graphen in die natürlichen Zahlen nicht nur surjektiv, sondern sogar bijektiv sein! (außer 1,2,4)

Gedanke 6 ed

Die Keime Modulo 6

Keim \( m = 6n + r \) , dann ist der nächste \( m' = 4m + 1 = 24n + 4r + 1 \, \Rightarrow r' = 4r + 1 \)

Als Liste:

$ 
 \begin{array}{c|cccccc}
   r  &0 &1 &2 &3 &4 &5\\
   \hline
   r' &1 &5 &3 &1 &5 &3
 \end{array}
$ 

Gedanken zu Schleifen ed

Jede Schleife ist durch ein Element eindeutig bestimmt

Folgt aus der Eindeutigkeit des "positiven" Problems.

• damit kann es nur eine Schleife durch die 1 geben: 4,2,1
• somit widerlegt jede andere Schleife die Behauptung.
• eine andere Schleife kann nicht mit dem Graphen durch die 1 verbunden sein

Die Behauptung verlangt somit, dass der Graph mit seiner einzigen Schleife \( \mathbb{Z} \) als Fundamentalgruppe besitzt.

Wenn die Endbedingung auf die 2 geändert wird und die 1 aus der Menge genommen wird, so wird die Gruppe trivialisiert.